пятница, 18 октября 2013 г.

Монада и моноид: что это такое

Монада

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

В частности, к монадам относятся:

  • IO (монада строго последовательных вычислений): стратегия связывания — «сначала первое вычисление, затем второе»;
  • Maybe (монада вычислений с отсутствующими значениями): стратегия связывания — «если первое вычисление дало результат, то второе; иначе — отсутствие результата»;
  • List (монада вычислений с несколькими результатами): стратегия связывания — «все возможные результаты второго вычисления, примененного к каждому из вычисленных первым значений параметра»;
  • State (монада вычислений с переменной состояния): стратегия связывания — «начать второе вычисление с состоянием, измененным в результате первого»;
Вот тут описан хороший пример создания и использования монады Maybe.

Моноид

Моноид - это множество с заданной на нем ассоциативной бинарной операцией и нейтральным элементом. Примерами моноидов могут служить:

  • String с операцией конкатенации и значением "пустая строка";
  • Boolean с операцией && и значением true;
  • Boolean с операцией || и значением false;
  • Integer с операцией (+) и значением 0;
  • -Integer с операцией (*) и значением 1;

и т.д.

Определения, которые помогают глубже постигнуть суть моноида

Свойство ассоциативности


Операция \(\circ\) ассоциативна, когда \(\forall x,y,z  (x\circ{y})\circ{z}=x\circ(y\circ{z})\).

Операция сложения целых чисел - ассоциативна.
Например, вычисление выражения 1 + (2 + 3) даст такой же результат, как и вычисление выражения (1 + 2) + 3  число 6.

Операция деления на множестве вещественных чисел - не ассоциативна.
Например, вычисление выражения 4/(2/2) даст число 4, а (4/2)/2 - число 1.

Бинарная операция


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

Нейтральный элемент

Нейтральный элемент бинарной операции - это элемент, который оставляет любой другой элемент неизменным при применении к ним этой бинарной операции. Говоря более формально, пусть \((M, \circ)\) - множество \(M\) с определенной на нем бинарной операцией \(\circ\). Элемент \(e \in M\) называется нейтральным относительно \(\circ\), если \(x\circ{e}=e\circ{x}=x\) \( \forall x \in M\).

1. Определение монады (wiki)
2. Туториал по системе переписывания термов TermWare
3. Про моноиды с примерами на F#
4. Определение ассоциативности (wiki)
5. Определение ассоциативности (ru.math.wikia)
6. Бинарная операция (wiki)
7. Определение нейтрального элемента (ru.math.wikia)


Комментариев нет:

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