Приветствую, Хабрахабр. Сегодня я хочу, в своём обычном стиле, устроить сообществу небольшой ликбез по структурам данных. Только на этот раз он будет гораздо более всеобъемлющ, а его применения и практичность — простираться далеко в самые разнообразные области программирования. Самые красивые применения, я, конечно же, покажу и опишу непосредственно в статье.
Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее
декартова дерева), умение читать простой код на C#, и желание применить полученные знания.
Итак, на повестке сегодняшнего дня —
моноиды и их основное применение для кеширования вычислений в деревьях.
Моноид как концепция
Представьте себе множество
чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его
M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если
a и
b — элементы множества, то
c =
a ⊗
b — тоже какой-то элемент этого множества.
Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+":
"John" ◦ "Doe" = "JohnDoe". Здесь множество
M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция
fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так,
fst(5, 2) = 5;
fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.
Далее мы на нашу операцию "⊗" накладываем ограничение
ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для
любых трёх объектов
a,
b и
c должно иметь место:
(a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции
fst, ибо:
fst(
fst(
a,
b),
c) =
a
fst(
a,
fst(
b,
c)) =
a
Цепочка применений
fst к последовательности в любом порядке всё равно выдаст её головной элемент.
И последнее, что мы потребуем: в множестве
M по отношению к операции должен существовать
нейтральный элемент, или
единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если
e — нейтральный элемент, то для любого
a из множества имеет место:
a ⊗
e =
e ⊗
a =
a
В примере со строками нейтральным элементом выступает пустая строка
"": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот
fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь
fst(e, a) = e всегда, и если
a ≠ e, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть
fst на множестве из одного элемента, но кому такая скука нужна? :)
Каждую такую тройку
<M, ⊗, e> мы и будем торжественно называть
моноидом. Зафиксируем это знание в коде:
public interface IMonoid<T> {
T Zero { get; }
T Append(T a, T b);
}
Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.
, 
— пересечение полуплоскостей, 
— алгоритм Форчуна) и некоторых тонкостях реализации (на языке C++).
Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. 
Недавно мне понадобилось написать 2-3-дерево и я начал искать информацию в русскоязычном интернете. К сожалению, ни на хабре, ни на других ресурсах я не смог найти достаточно полную информацию на русском языке. На всех ресурсах было одно и то же: свойства дерева, как вставляются ключи в дерево, поиск в дереве и иногда простой пример, как удаляется ключ из дерева; не было реализации. 
