Примеры моноидов / полугрупп в программировании - PullRequest
Новая
       52

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

26 голосов
/ 20 марта 2010

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

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

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

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

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

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

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

Ответы [ 4 ]

6 голосов
/ 21 марта 2010

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

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

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

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

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

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

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

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

5 голосов
/ 20 марта 2010

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

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

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

1 голос
/ 28 мая 2012

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

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

0 голосов
/ 16 января 2013

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

...