Приветствую, Хабрахабр. Сегодня я хочу, в своём обычном стиле, устроить сообществу небольшой ликбез по структурам данных. Только на этот раз он будет гораздо более всеобъемлющ, а его применения и практичность — простираться далеко в самые разнообразные области программирования. Самые красивые применения, я, конечно же, покажу и опишу непосредственно в статье.
Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее
декартова дерева), умение читать простой код на 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);
}
Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.
Все знают Wolfram|Alpha, и наверняка слышали о Wolfram Mathematica. К сожалению, поиск показал отсутствие постов об этой замечательной среде на хабре, и данной статьей хотелось бы открыть серию публикаций посвященных программированию на Mathematica. Для начала стоит сказать о возможностях и особенностях этой системы, которых ой как много, так что запаситесь терпением. Если хабражителей заинтересует этот математический пакет, то обязательно последуют другие статьи, более конкретные, обучающие работе со средой и внутренним языком.
Классические разделы, на которые чаще всего разбивается жёсткий диск для установки системы и хранения данных, имею ряд существенных недостатков. Их размер очень сложно изменять, они находятся в строгой последовательности и просто взять кусочек от первого раздела и добавить к последнему не получится, если между ними есть ещё разделы. Поэтому очень часто при начальном разбиении винчестера пользователи ломают себе голову — сколько места выделить под тот или иной раздел. И почти всегда в процессе использования системы приходят к выводу, что они сделали не правильный выбор.
