вторник, 15 июня 2010 г.

Про моноиды (с примерами на 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

4 комментария:

ffog комментирует...

если еще не видели, интересное применение моноида
http://apfelmus.nfshost.com/articles/monoid-fingertree.html
http://hackage.haskell.org/packages/archive/fingertree/latest/doc/html/src/Data-FingerTree.html
http://scienceblogs.com/goodmath/2009/05/finally_finger_trees.php
http://v2matveev.blogspot.com/2010/03/data-structures-finger-tree-part-15.html

Pavel Samolisov комментирует...

Я видел, но все равно спасибо за ссылки.

enor комментирует...

Привет. Скажи пожалуйста, как у тебя на блоге реализована подсветка синтаксиса в коде?
Заранее благодарю.

Pavel Samolisov комментирует...

Здравствуйте. Я использую QuickHighlighter.

Отправить комментарий

Любой Ваш комментарий важен для меня, однако, помните, что действует предмодерация. Давайте уважать друг друга!