Хорошо известно, что моноиды невероятно распространены в программировании. Они настолько вездесущи и настолько полезны, что я в качестве «хобби-проекта» работаю над системой, полностью основанной на их свойствах (распределенная агрегация данных). Чтобы система была полезной, мне нужны полезные моноиды :)
Я уже знаю о них:
- Числовая или матричная сумма
- Числовое или матричное произведение
- Минимум или максимум в общем порядке с верхним или нижним элементом (в более общем случае соединение или встреча в ограниченной решетке или, в более общем случае, продукт или побочный продукт в категории)
- Установить союз
- Объединение карт, где конфликтующие значения объединяются с помощью моноида
- Пересечение подмножеств конечного множества (или просто пересечение множеств, если мы говорим о полугруппах)
- Пересечение карт с ограниченным ключевым доменом (то же самое здесь)
- Слияние отсортированных последовательностей, возможно, с объединением значений, равных ключу, в другом моноиде/полугруппе.
- Ограниченное слияние отсортированных списков (то же, что и выше, но мы берем верхнее N результата)
- Декартово произведение двух моноидов или полугрупп
- Объединение списков
- Композиция эндоморфизмов.
Теперь давайте определим квазисвойство операции как свойство, которое выполняется до отношения эквивалентности. Например, конкатенация списков является квазикоммутативной, если мы считаем эквивалентными списки одинаковой длины или с идентичным содержимым вплоть до перестановки.
Вот некоторые квазимоноиды и квазикоммутативные моноиды и полугруппы:
- Любая (a+b = a или b, если считать все элементы множества носителей эквивалентными)
- Любой удовлетворяющий предикат (a + b = тот из a и b, который не равен нулю и удовлетворяет некоторому предикату P, если ни один не соответствует нулю; если мы считаем, что все элементы, удовлетворяющие P, эквивалентны)
- Ограниченная смесь случайных выборок (xs+ys = случайная выборка размера N из объединения xs и ys; если мы считаем, что любые две выборки с тем же распределением, что и весь набор данных, эквивалентны)
- Ограниченная смесь взвешенных случайных выборок
- Назовем это «топологическим слиянием»: учитывая два ациклических и непротиворечивых графа зависимостей, граф, который содержит все зависимости, указанные в обоих. Например, составьте «конкатенацию», которая может привести к любой перестановке, в которой элементы каждого списка следуют по порядку (скажем, 123+456=142356).
Какие другие существуют?
