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

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

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

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

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

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

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

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

Источник

4 ответа

Решение

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

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

  • конечные множества с объединением: если ~ изменено так, что не учитывается количество элементов (так что "aa" ~ "a"), то A*/~ является свободным коммутативным идемпотентным моноидом.

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

Фактор моноиды автоматически приходят с гомоморфизмом M -> M/~, который сюръективен.

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

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

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

Источник

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

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

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

Источник

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

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

Источник

Произвольная длина вычисления римской цифры. https://gist.github.com/4542999

Источник
Другие вопросы по тегам