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