Всем привет! В предыдущей части цикла статей мы поговорили о том, зачем вообще нужно функциональное программирование, а также обсудили понятие классов типов и разобрали базовые из них: Eq (эквивалентность) и Ord (сравнимость).

Сейчас я хочу пролить свет на два наводящих жуть на неподготовленного читателя слова: моноиды и полугруппы. Это математические понятия родом из общей алгебры. На самом деле всё не так уж и страшно. Если совсем упрощать, то оба термина относятся к объединению элементов множества. Я помогу разобраться с их формальными определениями, а также на практических примерах покажу, как и зачем их использовать.

Примечание

При чтении материалов про функциональное программирование традиционно возникает вопрос: «А мне это нужно?» В предыдущей статье я уже отвечал, что, скорее всего, нет. Потребность в использовании функциональщины вообще и библиотеки fp-ts в частности возникает в действительно сложных проектах с запутанной логикой и часто меняющимися бизнес-требованиями. Но ирония в том что каждый разработчик (даже junior) ежедневно имеет дело с моноидами и полугруппами, сам того не зная. Да-да, мы практически в каждой задаче что-то соединяем, складываем и перемножаем.

Ассоциативная бинарная операция

Под бинарной операцией обычно понимают математическую операцию, принимающую два аргумента и возвращающую один результат. Примеров масса. Два числа можно сложить, умножить, разделить или возвести в степень, взять логарифм одного по основанию другого. Продолжать можно очень долго.

Свойством ассоциативности обладает бинарная операция, если для любых a, b и c соблюдается условие:

( a\ \circ \ b) \ \circ \ c\ =\ ( a\ \circ \ c) \ \circ \ b

Да-да, от перестановки слагаемых (множителей) сумма (произведение) не меняется, все мы имели дело с Васиными и Петиными апельсинами ассоциативными бинарными операциями ещё в начальной школе. Только кружочек в формуле выше не обязательно обозначает сумму или произведение, здесь стоит смотреть шире. Это любая операция, в которой не меняется результат от перестановки порядка аргументов.

Класс типов Semigroup — полугруппа

Формально, полугруппа — это множество с заданной на нём ассоциативной бинарной операцией. Эту операцию в fp-ts называют конкатенацией (concat). Важно заострить внимание на том, что как аргументы a и b, так и результат c не должны «вылезать» за пределы множества (то есть они должны иметь один тип). Давайте посмотрим код. Класс типов Semigroup в fp-ts — это реализация интерфейса:

interface Semigroup<A> {
  readonly concat: (x: A, y: A) => A // эта операция должна быть ассоциативной
}

Простейшие полугруппы можно сходу реализовать:

import { Semigroup } from "fp-ts/Semigroup";

/** Полугруппа для умножения чисел */
const semigroupProduct: Semigroup<number> = {
  concat: (x, y) => x * y,
};

/** Полугруппа для сложения чисел */
const semigroupSum: Semigroup<number> = {
  concat: (x, y) => x + y,
};

/** Полугруппа для конкатенации строк */
const semigroupString: Semigroup<string> = {
  concat: (x, y) => x + y,
};

semigroupProduct.concat(3, 2); // 6
semigroupSum.concat(3, 2); // 5
semigroupString.concat("Hello ", "world!"); // "Hello world!"

Но не нужно. В библиотеке fp-ts есть готовые реализации полугрупп для распространённых типов.

import { SemigroupSum, SemigroupProduct } from "fp-ts/number";
import { Semigroup as SemigroupString } from "fp-ts/string";

SemigroupProduct.concat(3, 2); // 6
SemigroupSum.concat(3, 2); // 5
SemigroupString.concat('Hello ', 'world!'); // "Hello world!"

Примерами полугрупп могут быть такие операции как сложение и умножение натуральных чисел, слияние строк, соединение фрагментов HTML-кода для создания нового фрагмента разметки. По сути, это комбинирование двух элементов данных в один. Конечно, полугруппами могут быть не только числа и строки. Давайте рассмотрим более практичный пример, когда эта абстрактная концепция приносит пользу и удобство.

Классическая проблема, актуальная не только для Домклик и ипотечного бизнеса, но и вообще для многих сервисов, работающих с физическими лицами — это объединение профилей пользователей. Представим, что при регистрации мы требуем от пользователя минимальное количество информации о себе. Однако при подаче ипотечной заявки (конечно же, для приобретения квартиры мечты) клиент вводит больше данных. Бизнес-задача: «склеить» изначальные данные профиля пользователя с обновлёнными данными.

На «голом» Typescript код может быть таким:

Hidden text
// Профайл пользователя
type TProfile = {
  // может быть несколько заявок и объектов недвижимости для одобрения
  realEstateObjects: TRealEstate[];
  name: string;
  isVerificated: boolean;
  registeredAt: number | null;
  lastUpdatedAt: number;
};

const initialProfile: TProfile = {
  realEstateObjects: [],
  name: "Ваня Иванов",
  isVerificated: false,
  registeredAt: new Date("2023-07-01T08:03:53.438Z").getTime(),
  lastUpdatedAt: new Date("2023-07-01T08:03:53.438Z").getTime()
};

const loanApplicationProfile: TProfile = {
  realEstateObjects: [
    {
      id: 24242,
      area: 55.56,
      address: "Санкт-Петербург, ул. Красивых молдавских партизан, д.47, кв. 35"
    }
  ],
  name: "Иванов Иван Иванович",
  isVerificated: true,
  registeredAt: null,
  lastUpdatedAt: new Date("2023-07-02T11:17:03.438Z").getTime()
};

// логика объединения
const mergeProfiles = (
  firstProfile: TProfile,
  secondProfile: TProfile
): TProfile => {
  return {
    ...firstProfile,
    realEstateObjects: [
      ...firstProfile.realEstateObjects,
      ...secondProfile.realEstateObjects
    ],
    isVerificated: firstProfile.isVerificated || secondProfile.isVerificated,
    name: (() => {
      if (firstProfile.name.length >= secondProfile.name.length) {
        return firstProfile.name;
      }

      return secondProfile.name;
    })(),
    registeredAt: (() => {
      // уходим от "граблей" 0 || null => null
      if (firstProfile.registeredAt === 0 && secondProfile.registeredAt)
        return firstProfile.registeredAt;

      return firstProfile.registeredAt || secondProfile.registeredAt;
    })(),
    lastUpdatedAt: (() => {
      if (firstProfile.lastUpdatedAt >= secondProfile.lastUpdatedAt)
        return firstProfile.lastUpdatedAt;

      return secondProfile.lastUpdatedAt;
    })()
  };
};

const mergedProfile = mergeProfiles(initialProfile, loanApplicationProfile);

Довольно сложно и запутанно. В то же время применение композиции функций и класса типов Semigroup библиотеки fp-ts для таких случаев позволяет написать код изящнее и лаконичнее:

Hidden text
import { Semigroup, max, struct } from "fp-ts/Semigroup";
import { Ord as OrdNumber } from "fp-ts/number";
import { contramap } from "fp-ts/Ord";
import { SemigroupAny } from "fp-ts/boolean";
import { getMonoid } from "fp-ts/Array";

// Объект недвижимости
type TRealEstate = {
  id: number;
  area: number;
  address: string;
};

// Профайл пользователя
type TProfile = {
  // может быть несколько заявок и объектов недвижимости для одобрения
  realEstateObjects: TRealEstate[];
  name: string;
  isVerificated: boolean;
  registeredAt: number | null;
  lastUpdatedAt: number;
};

const initialProfile: TProfile = {
  realEstateObjects: [],
  name: "Ваня Иванов",
  isVerificated: false,
  registeredAt: new Date("2023-07-01T08:03:53.438Z").getTime(),
  lastUpdatedAt: new Date("2023-07-01T08:03:53.438Z").getTime()
};

const loanApplicationProfile: TProfile = {
  realEstateObjects: [
    {
      id: 24242,
      area: 55.56,
      address: "Санкт-Петербург, ул. Красивых молдавских партизан, д.47, кв. 35"
    }
  ],
  name: "Иванов Иван Иванович",
  isVerificated: true,
  registeredAt: null,
  lastUpdatedAt: new Date("2023-07-02T11:17:03.438Z").getTime()
};

// Иногда готовых полугрупп из библиотеки бывает недостаточно
const EmptyDateSemigroup: Semigroup<number | null> = {
  concat: (x, y) => {
    if (x === 0 && y === null) return x;

    return x || y;
  }
};

// Собственно это весь код, который делает всю работу
const MergeProfilesSemigroup: Semigroup<TProfile> = struct({
  realEstateObjects: getMonoid<TRealEstate>(), // про моноиды ниже
  isVerificated: SemigroupAny, // boolean || boolean
  name: max(contramap((s: string) => s.length)(OrdNumber)), // самый длинный name
  lastUpdatedAt: max(OrdNumber), // самая поздняя дата
  registeredAt: EmptyDateSemigroup // между "null" и "не null" выберем "не null" 
});

const mergedProfile = MergeProfilesSemigroup.concat(
  initialProfile,
  loanApplicationProfile
);

Аналогичным образом мы можем гибко подстраивать логику объединения под изменяющиеся бизнес-требования (нужно только добавить поле в исходный объект и реализовать класс типов Semigroup для этого поля). Semigroup не является «серебряной пулей», и не для всех случаев объединения сущностей его применение будет удобным и лаконичным. Это зависит от структуры объекта объединения. С другой стороны, мы можем отобразить «неудобный» для реализации полугруппы объект как «удобный», но это повлечёт за собой написание шаблонного кода.

Класс типов Monoid — моноид

Моноид — это полугруппа с нейтральным элементом. Определение, хоть и краткое, но неочевидное для неподготовленного читателя. На самом деле всё просто. Во множестве вместе с ассоциативной бинарной операцией существует такой элемент x, при котором:

a\ \circ \ x\ =\ a

Да-да, математика из начальной школы здесь тоже работает. Если у Пети было 5 апельсинов, а Вася дал Пете 0 апельсинов, то в конечном счёте у Пети осталось так же 5 апельсинов. Для операции сложения чисел нейтральный элемент — это 0, для умножения — 1. Для конкатенации строк нейтральный элемент — пустая строка.

В библиотеке fp-ts класс типов Monoid определяется так:

interface Monoid<A> {
  readonly concat: (x: A, y: A) => A;
  readonly empty: A;
}

// или как наследование от Semigroup:
interface Monoid<A> extends Semigroup<A> {
  readonly empty: A
}

На основе этого определения простейшие моноиды реализуются так:

import { Monoid } from "fp-ts/Monoid";

const monoidString: Monoid<string> = {
  concat: (x, y) => x + y,
  empty: '',
}

const monoidSum: Monoid<number> = {
  concat: (x, y) => x + y,
  empty: 0,
}

const monoidMultiply: Monoid<number> = {
  concat: (x, y) => x * y,
  empty: 1,
}

monoidString.concat("Hello, ", "world!"); // => "Hello, world!"
monoidSum.concat(8, 2); // => 10
monoidMultiply.concat(8, 2); // => 16

Конечно же, библиотека fp-ts уже содержит эти и многие другие реализации:

import { MonoidSum, MonoidProduct } from 'fp-ts/number'
import { Monoid as MonoidString }  from 'fp-ts/string';

MonoidString.concat("Hello, ", "world!"); // => "Hello, world!"
MonoidSum.concat(8, 2); // => 10
MonoidProduct.concat(8, 2); // => 16

Примерами моноидов являются: конкатенация строк (строку можно рассматривать как коллекцию символов, во многих языках программирования это так и устроено), сложение или умножение чисел, объединение массивов и так далее. Реализация простой ассоциативной бинарной операции (конкатенации) и объявление нейтрального элемента позволяет довольно легко получить мощную функциональность, предназначенную для объединения коллекций элементов. То есть, в отличие от полугрупп (которые позволяют комбинировать только два элемента), моноиды дают возможность легко объединять множество элементов в один.

Рассмотрим практический пример. Одно из самых важных направлений деятельности Домклик — это выдача ипотечных кредитов в новостройках. Как правило, новостройки не возводятся в формате «один дом посреди поля», это целый жилой комплекс, то есть несколько домов. Задача: на основе их характеристик определить характеристики всего жилого комплекса. Наша команда разработки получает такое описание задачи:

  • Жилая площадь. Складывается из жилой площади всех домов, входящих в ЖК.

  • Коммерческая площадь. Здесь также суммируется коммерческая площадь всех новостроек в ЖК.

  • Максимальная этажность — этажность самого высокого дома.

  • Наличие кофейни и продуктового магазина. Если хотя бы в одном доме ЖК есть кофейня или продуктовый магазин, считаем, что он есть во всём ЖК.

Если реализовать такую задачу на чистом Typescript, то код начинает выглядеть громоздко, а усложнение бизнес-требований становится нетривиальной задачей:

Hidden text
type THouse = {
  livingArea: number;
  businessArea: number;
  apartmentsCount: number;
  commertialCount: number;
  floors: number;
  hasStore: boolean;
  hasCoffeeHouse: boolean;
};

const house1: THouse = {
  livingArea: 1240,
  businessArea: 400,
  apartmentsCount: 250,
  commertialCount: 7,
  floors: 16,
  hasCoffeeHouse: true,
  hasStore: false
};

const house2: THouse = {
  livingArea: 1750,
  businessArea: 440,
  apartmentsCount: 350,
  commertialCount: 10,
  floors: 25,
  hasCoffeeHouse: false,
  hasStore: false
};

const house3: THouse = {
  livingArea: 940,
  businessArea: 440,
  apartmentsCount: 180,
  commertialCount: 10,
  floors: 10,
  hasCoffeeHouse: false,
  hasStore: true
};

// логика выглядит как-то так
const mergeHouses = (houses: THouse[]): THouse =>
  houses.reduce(
    (acc, house) => {
      return {
        ...acc,
		// тут легко опечататься и сложить "жилую площадь" и "количество квартир"
  	    // ts это не подсветит
        livingArea: acc.livingArea + house.livingArea,
        businessArea: acc.businessArea + house.businessArea,
        apartmentsCount: acc.apartmentsCount + house.apartmentsCount,
        commertialCount: acc.commertialCount + house.commertialCount,
        hasCoffeeHouse: acc.hasCoffeeHouse || house.hasCoffeeHouse,
        hasStore: acc.hasStore || house.hasStore,
        floors: (() => {
          if (house.floors > acc.floors) return house.floors;

          return acc.floors;
        })()
      };
    },
    {
      livingArea: 0,
      businessArea: 0,
      apartmentsCount: 0,
      commertialCount: 0,
      hasCoffeeHouse: false,
      hasStore: false,
      floors: 0
    }
  );

const result = mergeHouses([house1, house2, house3]);

Но если применить класс типов Monoid из библиотеки fp-ts, а также композицию функций, то реализация становится тривиальной:

Hidden text
import { struct, max, concatAll } from "fp-ts/Monoid";
import { MonoidSum, Bounded as BoundedNum } from "fp-ts/number";
import { MonoidAny } from "fp-ts/boolean";

type THouse = {
  livingArea: number;
  businessArea: number;
  apartmentsCount: number;
  commertialCount: number;
  floors: number;
  hasStore: boolean;
  hasCoffeeHouse: boolean;
};

const house1: THouse = {
  livingArea: 1240,
  businessArea: 400,
  apartmentsCount: 250,
  commertialCount: 7,
  floors: 16,
  hasCoffeeHouse: true,
  hasStore: false
};

const house2: THouse = {
  livingArea: 1750,
  businessArea: 440,
  apartmentsCount: 350,
  commertialCount: 10,
  floors: 25,
  hasCoffeeHouse: false,
  hasStore: false
};

const house3: THouse = {
  livingArea: 940,
  businessArea: 440,
  apartmentsCount: 180,
  commertialCount: 10,
  floors: 10,
  hasCoffeeHouse: false,
  hasStore: true
};

// Вся логика здесь
const M = struct<THouse>({
  livingArea: MonoidSum, // площади суммируются
  businessArea: MonoidSum, // площади суммируются
  apartmentsCount: MonoidSum, // количество квартир суммируется
  commertialCount: MonoidSum, // количество коммерческой недвижимости суммируется
  hasCoffeeHouse: MonoidAny, // если где-то true, то всё true
  hasStore: MonoidAny, // если где-то true, то всё true
  floors: max(BoundedNum) // возвращается максимальное значение
});

// Этот хэлпер соединяет все моноиды
const result = concatAll(M)([house1, house2, house3]);

По сути, класс типов Monoid позволил нам упаковать эту логику всего в 9 строк лаконичного кода с сохранением типобезопасности. Не составит труда расширить функциональность объединения характеристик домов в жилом комплексе при изменении требований бизнес-заказчика. Класс типов Monoid применяют чаще, чем Semigroup, ведь, как было отмечено выше, каждый разработчик, даже сам того не осознавая, ежедневно имеет дело с моноидами.

Вместо заключения

В примерах выше я попытался провести ликбез по полугруппам (класс типов Semigroup) и моноидам (класс типов Monoid) библиотеки fp-ts. Были рассмотрены относительно практические примеры применения обоих классов типов. Очень надеюсь что статья помогла вам понять на базовом уровне эти концепции функционального программирования. В этом цикле статей мы уже рассмотрели и ещё рассмотрим:

Спасибо за внимание, оставайтесь на связи.

Комментарии (13)


  1. Vindicar
    06.07.2023 09:23
    +10

    Да-да, от перестановки слагаемых (множителей) сумма (произведение) не меняется, все мы имели дело с Васиными и Петиными апельсинами ассоциативными бинарными операциями ещё в начальной школе.

    Что-то вы уже в самом начале напутали. Ассоциативность - это не про порядок аргументов, это про порядок выполнения цепочки операций вида x ? y ? z ? ... Для ассоциативных операций (x ? y) ? z = x ? (y ? z). Порядок аргументов (перестановка мест слагаемых) - это коммутативность.

    Собственно, пример с контактенацией строк это показывает. Результат конкатенации зависит от порядка аргументов (операция не коммутативна), но не зависит от порядка выполнения конкатенаций в цепочке (операция ассоциативна).


    1. evgeniyrru Автор
      06.07.2023 09:23
      -1

      Да, вы совершенно правы, спасибо.

      Формальное определение и математическая формула, всё же, корректны. Пример, да, может вызывать споры, но моя цель была максимально упростить понимание для новичков. Если взяли Петины апельсины, сложили с Мишиными, а потом с Танечкиными, то их количество будет таким же, как если сложить сначала Танечкины и Петины апельсины, а потом к ним прибавить Мишины. Но по сути, это "от перестановки слагаемых сумма не меняется".


      1. funca
        06.07.2023 09:23
        +1

        В математике сложение одновременно и ассоциативно (можно расставлять скобки как угодно), и коммутативно (можно менять порядок аргументов местами). Конкатенация только ассоциативна. Поэтому отсылка к перестановке слагаемых для полугруп, по сути, мимо кассы и новичков может лишь сбивать с толку.

        В JavaScript есть врождённый порок - здесь "+" используется и как оператор сложения, когда речь идёт о числах, и как оператор конкатенации, когда речь идёт о строках. fp-ts в некоторой степени это исправляет, вводя разные имена для оператора конкатенации (Semigroup.concat) и сложения (Semiring.add).

        Ассоциативность можно наглядно показать на примере строк:

        concat ("foo", concat ("bar", "baz")) ==

        cancat (concat ("foo", "bar"), "baz") ==

        "foobarbaz"

        Но если переставить аргументы местами, то результат будет другим.


      1. EzikBro
        06.07.2023 09:23
        +4

        Пример может и правильный, но фраза совсем некорректная. Перестановка слагаемых - это не ассоциативность, а коммутативность, не стоит путать людей.


      1. code_panik
        06.07.2023 09:23
        +3

        Формальное определение и математическая формула, всё же, корректны.

        Операция ассоциативна, когда результат не зависит от расстановки скобок, и только. А в формуле выше ещё и элементы переставляются. Сейчас она выглядит как (a * b) * c = (a * c) * b. Похоже, просто опечатку пропустили, https://ru.wikipedia.org/wiki/Ассоциативность_(математика).


      1. NotSure
        06.07.2023 09:23

        Но по сути, это "от перестановки слагаемых сумма не меняется".

        Главное, не складывать числа с плавающей точкой)


      1. mikhanoid
        06.07.2023 09:23
        +2

        Математическая формула не корректна. У Вас написано (ab)c = (ac)b, а должно быть (ab)c = a(bc).


  1. dgoncharov
    06.07.2023 09:23
    +2

    в отличие от полугрупп (которые позволяют комбинировать только два элемента), моноиды дают возможность легко объединять множество элементов в один.

    Мог бы кто-нибудь объяснить, откуда это следует? Ассоциативная бинарная операция в полугруппах уже имеется. Что мешает применить ее несколько раз?


    1. Vindicar
      06.07.2023 09:23
      +1

      Ну я так подозреваю, имелось ввиду, что нейтральный(нулевой) элемент является удобной начальной точкой, с которой можно поочерёдно комбинировать остальные элементы множества. Ну а заодно это осмысленный результат для пустого множества.

      Хотя да, технически никто не запрещает взять первый попавшийся элемент множества в качестве начального, и комбинировать с ним остальные. Но такой подход не даёт ответа для пустого множества.


      1. mikhanoid
        06.07.2023 09:23

        Почему не даёт? Можно для пустого множества задать произвольный элемент. Другое дело, что это не позволит гомоморфизм между свободным моноидом списков и полугруппой установить. Но гомоморфность не всегда нужна.


    1. code_panik
      06.07.2023 09:23

      Возможно, речь идет об удобстве работы с ts. Не знаю ts, но моноиды от полугруппы по определению отличаются только нейтральным элементом. И в той, и в другой структуре задана именно бинарная операция, которая по определению всегда требует два аргумента.


    1. funca
      06.07.2023 09:23

      моноиды дают возможность легко объединять множество элементов в один.

      Скорее имелось ввиду, что модуль Monoid предоставляет утилиту concatAll(), которая делает сверку последовательности моноидов. Аналогичная функция есть и в модуле Semigroup, но требует дополнительный аргумент с начальным значением на случай если последовательность окажется пустой (Monoid в таком случае использует empty).


  1. code_panik
    06.07.2023 09:23
    +4

    В определении нейтрального элемента не хватает свойства перестановочности, если x - нейтральный, то x * a = a * x = a. Сейчас у нас элемент x является только правым нейтральным, https://ru.wikipedia.org/wiki/Нейтральный_элемент#Определение. Операция в полугруппе и моноиде не является коммутативной.