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

65aac40c80662028672ff99e60794c83.jpg

Всем привет! В предыдущей части цикла статей мы поговорили о том, зачем вообще нужно функциональное программирование, а также обсудили понятие классов типов и разобрали базовые из них: 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 {
  readonly concat: (x: A, y: A) => A // эта операция должна быть ассоциативной
}

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

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

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

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

/** Полугруппа для конкатенации строк */
const semigroupString: Semigroup = {
  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 = {
  concat: (x, y) => {
    if (x === 0 && y === null) return x;

    return x || y;
  }
};

// Собственно это весь код, который делает всю работу
const MergeProfilesSemigroup: Semigroup = struct({
  realEstateObjects: getMonoid(), // про моноиды ниже
  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 {
  readonly concat: (x: A, y: A) => A;
  readonly empty: A;
}

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

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

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

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

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

const monoidMultiply: Monoid = {
  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

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

e3b55059f39ac3b29a886e6cc514ddb7.jpeg

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

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

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

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

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

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

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

© Habrahabr.ru