Про моноиды (с примерами на F#)

Введение

Apocalips порадовал статьей, в которой четко и доходчиво объяснил что такое моноид применительно к алгебре над списками и теории категорий. В данной заметке представлен очень вольный перевод его статьи, снабженный примерами на F# (у Apocalips'a примеры на Scala).

Прежде всего рассмотрим обобщенное определение моноида:

1. type IMonoid<'T> =


2.    abstract member mempty : 'T


3.     abstract member mappend : 'T * 'T -> 'T

Другими словами, моноид заданного типа 'T - это объединение двух элементов: функции mappend: 'T -> 'T -> 'T и значения mempty: 'T. Для моноида должны выполняться следующие правила:

1. Функция mappend должна быть ассоциативна, т.е. mappend (x, mappend(y, z)) == mappend(mappend(x, y), z).
2. Значение mempty должно быть единицей функции mappend, другими словами: mappend(x, mempty) == mappend (mempty, x) == x



Примерами моноидов могут служить:
- String с операцией конкатенации и значением "пустая строка";
- Boolean с операцией && и значением true;
- Boolean с операцией || и значением false;
- Integer с операцией (+) и значением 0;
- Integer с операцией (*) и значением 1;
и т.д.

Для примера рассмотрим Integer-моноид для суммы:

1. type SumMonoid() =


2.     interface IMonoid<int> with


3.         member this.mempty = 0


4.         member this.mappend(a, b) = a + b

Моноид как алгебра над списками

Все знакомы с понятием односвязного списка - List<'T>. Данный список конструируется из пустого списка [] или из элемента типа 'T и другого списка List<'T>.

[] - пустое значение, оно не имеет аргументов и структуры и, фактически, эквивалентно значению () типа Unit. Оператор :: (cons) - конструктор, получает два аргумента и возвращает непустой список List<'T>, эквивалентный паре ('T, List<'T>) (голове и хвосту).

Важно, что моноид состоит из двух функций, одна из которых не имеет аргументов, а другая - имеет два аргумента, так же как и конструктор списка. Это не случайно, однако является темой другой статьи. Сейчас же обратим внимание на то, что, если у нас есть список List<'T> и моноид IMonoid<'T>, то мы можем редуцировать список к одиночному элементу 'T:

1. let reduce<'T> (monoid:IMonoid<'T>) (list:'T list) =


2.    let rec iter (res:'T) = function


3.         | []     -> res


4.         | h :: t -> iter (monoid.mappend (res, h)) t


5.     iter monoid.mempty list

Если расписать моноид как набор из функции и ее единицы, то получится следующая сигнатура:

1. let reduce<'T> (empty: 'T) (append: 'T -> 'T -> 'T) (list: 'T list)

Данная сигнатура очень похожа на сигнатуру функции правой свертки, foldRight, что опять же не случайно. Для сравнения - вот сигнатура функции foldRight:

1. let foldRight<'A, 'B> (empty: 'B) (append: 'A -> 'B -> 'B) (list: 'A list)

Фактически, реализация двух последних функций идентична. Т.е. моноид - просто абстракция, которая представляет аргументы, передаваемые в функцию fold. Ассоциативность моноида моделирует тот факт, что результаты правой и левой сверток будут равны. Правило единицы моделирует тот факт, что пустой список "не считается" (т.е. единица - результат свертки пустого списка).

Моноид как одно-объектная категория

Небольшое введение в теорию категорий. Категория включает в себя объекты (A, B, C и т.д.) и стрелки между этими объектами (A => B, B => C, C => A и т.д.). Можно рассматривать это как диаграмму или граф с объектами, в качестве узлов, и стрелками, в качестве направленных ребер (или дуг). Для каждой пары f: A => B и g: B => C существует композитная стрелка (f * g): A => C.

Рассмотрим пример: существует категория, в которой объектами являются типы данных F#, стрелками - функции F#, а композицией является простая суперпозиция функций.

Категория так же должна иметь единичную стрелку для каждого объекта, ведущую из объекта в него самого. Применительно к категории F#, данной стрелкой является функция id:

1. let id<'A> (a: 'A) = a

Таким образом, категория должна удовлетворять требованиям ассоциативности: ((f * g) * h == f * (g * h)) и иметь единицу: (f * id == f) для всех стрелок f, g, h.

Данные требования абсолютно идентичны правилам, которые выполняются для моноида. Можно рассматривать функцию mappend как композицию стрелок, а единичное значение - как единичную стрелку. Для моноида IMonoid<'T> стрелки ведут строго из значений типа 'T в значения типа 'T. Таким образом, тип 'T - единственный объект в категории, представляемой моноидом IMonoid<'T>.

Понравилось сообщение - подпишитесь на блог или читайте меня в twitter