Моноиды — одна из тех вещей, которые начали сводить меня с ума, как только я понял, что они означают и как ими можно владеть. Мое первое знакомство с ними произошло в рамках курса по дискретной математике в колледже, который имел дело с набором алгебраических структур. Курс представлял собой содержательное изложение их свойств и ничего более, я отчетливо помню, как пытался понять, зачем вообще нужно кольцо или полугруппа, особенно в программной инженерии. Встретившись [1] с ними сейчас, я обнаружил, что это очень интересная идея и что их можно найти повсюду, если поискать достаточно внимательно (вероятно, это неправда :)). Этот пост в основном является напоминанием самому себе попытаться найти общие шаблоны и структуры, которые можно извлечь из проблемной области, и больше работать с абстракциями функционального программирования. В идеале это означало бы лучше управляемый код, хорошо протестированный и DRY-ed.
Я указываю на Википедию [2] для формального определения моноида,
Предположим, что S — это множество и • — некоторая бинарная операция S × S → S, тогда S с • является моноидом, если он удовлетворяет следующим двум аксиомам:
Ассоциативность,
Для всех a, b и c в S уравнение (a • b) • c = a • (b • c) выполняется.
Элемент идентичности,
Существует элемент e в S такой, что для каждого элемента a в S уравнения e • a = a • e = a удерживать.
Вот краткая реализация моноида на питоне:
Сейчас я объясню, почему в этой реализации есть словарь store. Несмотря на это, все, что нужно понимать, это «ноль» и «foldOp».
«ноль» — это элемент идентичности, а «foldOp» — бинарный оператор из формального определения. Эта реализация предполагает, что foldOp является ассоциативным. foldOp — сокращение от операции fold, заимствованной из функционального программирования.
sumAggregator, который определен как моноид, является тривиальным примером того, как можно использовать моноид. Мотивация изучения этого тривиального приложения очень проста и очень поучительна для меня.
Учтите, что у вас был очень большой набор данных выборок из набора целых чисел, и давайте предположим, что вам нужно построить гистограмму частот указанных целых чисел. Естественным решением этой проблемы является использование spark или hadoop, если мы предположим, что размер набора данных составляет несколько терабайт.
Теперь проблема заключается в том, что если бы понятие гистограммы по своей сути не было моноидом, очень легко столкнуться с проблемами масштабирования в виде проблемы последнего редуктора. Следующий фрагмент кода служит примером:
В отличие от того, что обсуждалось в [1], эта реализация функции отображения и редукции не подходит для объединителей на стороне карты, которые используют последующие операции редукции в месте операции карты после завершения операции карты. Подобно тому, что обсуждалось в [1], следующий код пытается решить эту проблему:
Обратите внимание, что «хранилище», используемое в этих двух примерах, похоже на «хранилище», используемое в исходной реализации моноида, и используется примерно таким же образом.
Вывод здесь заключается в том, что первая версия выше, кажется, выполняет много расточительной работы, хотя на самом деле проблемная область легко поддается значительному увеличению временной сложности; первая версия масштабируется линейно по размеру ввода, в то время как вторая обеспечивает масштабирование усиления по размеру целочисленных ключей. Это связано с тем, что вычисление гистограммы достигается путем определения операции объединения как моноида над набором целых чисел, а также с учетом того, что операция объединения является как ассоциативной, так и коммутативной, в данном случае сложением по некоторому бину.
Таким образом, в контексте больших данных идентификация моноидов очень полезна при масштабировании больших наборов данных.
Однако более глубокое преимущество заключается в том, что идентификация моноида помогает организовать мой код. Самый простой пример, который я могу придумать в отношении проблем, над которыми я работаю, — это масштабирование моделей машинного обучения. Самыми простыми из них являются векторы встраивания слов, которые используются для фиксации некоторого понятия поведения, которое можно рассматривать как моноид, учитывая, что векторы действительных чисел ассоциативны и коммутативны по отношению к оператору поэлементного сложения. При этом я определил несколько аспектов этих вложений слов, которые используют преимущества того, как можно повторять код, вычисляющий, скажем, разность, произведения или временные затухания таких векторов.
Итак, в заключение, моноиды потрясающие, и я не могу перестать восхищаться ими :D
