Comments 13
Это бинарный предикат, а не операция. Но, как всегда, мы можем решить эту проблему с помощью введения дополнительного уровня абстракции (похоже на то, как мы делали в прошлом примере с минимумом): надо сконструировать такой тип, чтобы обобщенная операция сравнения была определена на множестве этого типа.
Вы пропустили важный для понимания шаг. Перед тем как расширять тип и определять обобщенную операцию на нем — надо бы придумать как вообще операция сравнения должна выполняться на трех аргументах.
Насколько я понимаю, вы решили определить ее как проверку составного неравенства:
x < y < z < t = (x < y) && (y < z) && (z < t)
Спасибо, интересно.
для определения моноида нам надо задать 3 вещи:
множество, на котором определена наша операция
саму операцию, обладающую ассоциативностью
нейтральный элемент (из вышеопределенного множества)
Нейтральный элемент не надо задавать. После того как вы зафиксировали множество и операцию — нейтральный элемент либо есть, либо нет.
Вот придет к вам следователь и скажет — предъявите моноид, гражданин. И будет по списку проверять комплектность и исправность (соблюдение законов). Вы ему скажете — вот мое множество и операция, а нейтральный элемент — либо есть, либо нет. И он вас задержит до выяснения обстоятельств. А если вы ему предъявите всю троицу, да еще продемонстрируете соблюдение законов — тогда и вопросов к вам никаких не будет. Так что дело не в глаголах — задавать или предъявлять, а 3 составляющих моноида должны быть — и все тут. По закону положено.
Не надо приписывать мне нелепостей. Зачем же я буду говорить "нейтральный элемент либо есть, либо нет", если он у меня есть?
Вы неточно говорите о "комплектности" моноида. Нет там "троицы", "трёх составляющих". Есть двойка {множество, операция} и два требования: ассоциативность и наличие нейтрального элемента. Выполнение этих требований проверяется, а не "задаётся". "Задать нейтральный элемент операции" — примерно то же самое, что "задать ассоциативность операции", то есть бессмыслица.
И напрасно вы говорите, что дело не в глаголах. В математике дело и в глаголах тоже. И в существительных, и в прилагательных. Хотя, конечно, не только в них.
Надеюсь, вы не хотите, чтобы я комментировал ваши думы.
Теперь возьмем пример поинтереснее — бинарную операцию минимума на числовом множестве. Является ли она моноидом? Операция ассоциативна, множество задано. Единственная проблема — определение нейтрального элемента. Нам нужен такой элемент в нашем множестве, который был бы не меньше любого другого элемента. Если наше множество имеет точную верхнюю грань (например, тип uint8 имеет максимальное значение 255), то мы можем взять это значение в качестве нейтрального элемента нашего моноида. Но если у нас тип неограниченных целых чисел? Решение довольно простое — мы расширяем наш тип еще одним специальным значением (условно назовем его «плюс бесконечность») и зададим операцию так, чтобы выполнялись законы
Prelude> mconcat $ map Min ['a', 'b', 'c']
Min 'a'
Prelude> mconcat $ map Min ([] :: [Char])
HighInf
Я думал, что операция определена «на числовом множестве»? Наверно тоже моя дума. Хотя нет, всё нормально, ведь
Все как и ожидалось — минимум на пустом списке дает плюс бесконечность, на непустом — минимальный элемент.
Как всем хорошо известно, моноидом называется ассоциативная бинарная операция на заданном множестве, имеющая нейтральный элемент.
Думаю, стоит поправить. Моноид — это множество, на котором задана бинарная ассоциативная операция, а не сама операция (к тому же, операция не может иметь нейтральный элемент).
Что же касается сути статьи, а именно реализации полиадической функции сравнения — могу сказать лишь одно: желание реализовать такое возникает только у «лисперов», в силу определенных тенденций.
Нейтральный элемент — это как раз свойство бинарной операции, а не моноида, и он определяется как элемент a, такой что для любого допустимого x выполняется
a * x = x * a = x, где * - обсуждаемая операцияДля любой операции может существовать не больше одного нейтрального элемента, что очень легко доказывается:
пусть a и b - нейтральные элементы операции *
тогда a = a * b = bДля сложения нейтральный элемент — 0, для умножения — 1, а для минимума — плюс бесконечность, как бы лично вам не хотелось неопределенности или минус бесконечности.
Хотя о чем это я.
*MyMonoid> mconcat $ map Min [] HighInf
Я так понимаю вы хотите доказать, что минимальным элементом пустого множества является плюс бесконечность?
Ну как-бы
Prelude Data.Monoid> getSum $ mconcat $ map Sum []
0
Prelude Data.Monoid> getProduct $ mconcat $ map Product []
1С другой стороны я согласен, что вводить HighInf подобным способом — грубо и некрасиво, я бы использовал для этих целей maxBound.
Если мы хотим моноид, то нейтральный элемент должен быть нейтральным как справа, так и слева. Некоммутативность операции тут не может быть оправданием. В противном случае, мы не сможем получить нормальную ассоциативность:
если x * e ≠ e * x то (a * e) * b ≠ a * (e * b)а без ассоциативности моноид не получится никак.
Вы правы, что корректнее для пустого множества в качестве минимального элемента использовать неопределённость. И тут вместо введения искуственного нейтрального элемента стоит использовать то обстоятельство, что любую полугруппу можно превратить в моноид с помощью Maybe.
λ> getMin <$> foldMap (Just . Min) ([2,4,1,8,5] :: [Integer])
Just 1
λ> getMin <$> foldMap (Just . Min) ([] :: [Integer])
Nothingгде Min импортирован из Data.Semigroup.
Однако, когда мне нужно было на практике использовать моноид Min для неограниченного множества я ввёл для этого множества искусственные границы, то есть определил его экземпляром класса Bounded. Так существенно удобнее, чем таскать Maybe.
Ну и, наконец, Maybe (Min a) равен, с точностью до изоморфизма, типу Min a + Maximal. Так что преступления никакого автор не совершает. К тому же, спорное Maximal можно заменить на Undefined, это дело вкуса и стилистики.
Как я "<" моноидом делал