Примеры моноидов/полугрупп в программировании

Хорошо известно, что моноиды потрясающе вездесущительны при программировании. Они настолько повсеместны и настолько полезны, что я, как "хобби-проект", работаю над системой, которая полностью основана на их свойствах (распределенная агрегация данных). Чтобы сделать систему полезной, мне нужны полезные моноиды:)

Я уже знаю об этом:

  • Числовая или матричная сумма
  • Числовой или матричный продукт
  • Минимальный или максимальный при общем порядке с верхним или нижним элементом (в более общем смысле, соединять или встречаться в ограниченной решетке или, что более важно, продукт или копродукт в категории)
  • Установить соединение
  • Соединение с картой, в котором конфликтующие значения объединяются с помощью моноида
  • Пересечение подмножеств конечного множества (или просто заданное пересечение, если говорить о полугруппах)
  • Пересечение карт с ограниченной ключевой областью (здесь же)
  • Объединение отсортированных последовательностей, возможно, с объединением значений, равных ключу, в другой моноидной/полугруппе
  • Ограниченное слияние отсортированных списков (аналогично выше, но мы берем верхний N результата)
  • Декартово произведение двух моноидов или полугрупп
  • Конкатенация списков
  • Состав эндоморфизма.

Теперь определим квази-свойство операции как свойство, которое выполняется с отношением эквивалентности. Например, конкатенация списка является квази-коммутативной, если мы рассматриваем списки равной длины или с одинаковым содержимым до перестановки, чтобы быть эквивалентным.

Вот некоторые квазимоноиды и квазикоммутативные моноиды и полугруппы:

  • Любой (a + b = a или b, если мы считаем все элементы набора носителей эквивалентными)
  • Любой удовлетворяющий предикат (a + b = один из a и b, который не является нулевым и удовлетворяет некоторому предикату P, если ни один из них не равен нулю, если мы рассмотрим все элементы, удовлетворяющие эквиваленту P)
  • Ограниченная смесь случайных выборок (xs + ys = случайная выборка размера N из конкатенации xs и ys, если мы рассматриваем любые два образца с тем же распределением, что и весь набор данных, чтобы быть эквивалентным)
  • Ограниченная смесь взвешенных случайных образцов
  • Позвольте называть его "топологическим слиянием": заданы два ацикличных и непротиворечивых графика зависимостей - график, содержащий все зависимости, указанные в обоих. Например, перечислите "конкатенацию", которая может вызвать любую перестановку, в которой элементы каждого списка следуют по порядку (скажем, 123 + 456 = 142356).

Какие другие существуют?

Ответы

Ответ 1

Quotient monoid - это еще один способ создания моноидов (квазимоноидов?): данный моноид M и отношение эквивалентности ~, совместимое с умножением, дает другое моноидом. Например:

  • конечные мультимножества с объединением: если A * - свободный моноид (списки с конкатенацией), ~ является "перестановкой" отношения, то A */~ является свободной коммутативной моноидом.

  • конечные множества с объединением: если ~ модифицировано, чтобы игнорировать подсчет элементов (так что "aa" ~ "a" ), то A */~ - свободный коммутативный идемпотентный моноид.

  • синтаксический моноид. Любой регулярный язык приводит к синтаксическому моноиду, который является отношением A * к "неразличимости по языку". Здесь - это реализация этой идеи пальцем. Например, язык {a 3n: n natural} имеет Z 3 как синтаксический моноид.

Котируемые моноиды автоматически приходят с гомоморфизмом M → M/~, сюръективным.

"Двойная" конструкция - субмоноиды. Они имеют гомоморфизм A → M, инъективный.

Еще одна конструкция на моноидах тензорный продукт.

Моноиды допускают экспонентацию путем возведения в квадрат в O (log n) и быстрого параллельного вычисления prefix sums. Также они используются в монаде Writer.

Ответ 2

Стандартная библиотека Haskell поочередно оценивается и атакуется за использование фактических математических терминов для своих классов типов. (По-моему, это хорошо, потому что без него я даже не знаю, что такое моноид!). В любом случае вы можете проверить http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html еще на несколько примеров:

  • дуал любого моноида является моноидом: если задано a + b, определите новую операцию ++ с a ++ b = b + a
  • соединение и дизъюнкция булевых
  • над монадией Maybe (aka "option" в Ocaml), первая и последняя. То есть, 
    first (Just a) b = Just a
first Nothing b = b
    и аналогично для последнего

Последний - это лишь верхушка айсберга целого семейства моноидов, связанных с монадами и стрелами, но я не могу обернуть вокруг себя (кроме простых монадических эндоморфизмов). Но поиск google в monads monoids появляется совсем немного.

Ответ 3

Действительно полезным примером коммутативного моноида является унификация в логике и языках ограничений. См. Раздел 2.8.2.2 "Концепции, методы и модели компьютерного программирования" для точного определения возможного алгоритма унификации.

Удачи вам! Я делаю что-то подобное с параллельным языком, используя моноиды для объединения подрезультатов из параллельных вычислений.