Yet another введение в fp-ts. Часть 2. Моноиды и полугруппы

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

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

Примечание

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

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

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

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

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

Класс типов 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 код может быть таким:

// Профайл пользователя 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 для таких случаев позволяет написать код изящнее и лаконичнее:

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, при котором:

Да-да, математика из начальной школы здесь тоже работает. Если у Пети было 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, то код начинает выглядеть громоздко, а усложнение бизнес-требований становится нетривиальной задачей:

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, а также композицию функций, то реализация становится тривиальной:

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. Были рассмотрены относительно практические примеры применения обоих классов типов. Очень надеюсь что статья помогла вам понять на базовом уровне эти концепции функционального программирования. В этом цикле статей мы уже рассмотрели и ещё рассмотрим:

• Эквивалентность и сравнимость (классы типов Eq и Ord).

• Вычисления в контексте, функторы и монады (классы типов Option и Either).

• Работу с асинхронным кодом в рамках fp-ts (классы типов Task и TaskEither).

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