Какова идентичность типа?

Question

У меня есть следующий тип данных:

data Bull = Fools
  | Twoo
  deriving (Eq, Show)

и использовать Monoid для его реализации:

instance Monoid Bull where
  mempty = Fools
  mappend _ _ = Fools

Как вы видете, mempty Является ли функция тождества законами тождества:

*Main> x = Twoo
*Main> mappend mempty x == x

Какой будет личность Bull тип? Что такое личность Bool тип?

Answer 1

Краткий ответ: это зависит от mappend функция

Какой будет личность Bull тип? Что такое личность Bool тип?

Тип не имеет "присущей" идентичности, элемент идентичности существует только по отношению к двоичной функции (здесь mappend), как говорится в статье в Википедии:

В математике единичный элемент или нейтральный элемент - это особый тип элемента набора относительно бинарной операции над этим набором, который оставляет другие элементы неизменными при их объединении.

Так что это зависит от того, что операция mappend является.

В случае Bool если мы определим mappend = (&&) то элемент идентичности mempty = True, Но если мы выберем mappend = (||), затем mempty = False,

Ваш instance Moniod Bull неверно Поскольку он не может удовлетворить свойство:

mappend mempty x = x

Если мы выберем Fools как mempty = Fools, затем mappend Fools Twoo должно быть Twoo, И если мы выберем mempty = Twoo, затем mappend Twoo Twoo все еще нет Twoo,

Точка Monoid в том, что вы должны тщательно спроектировать бинарный оператор. Как документация на Haskell Monoid говорит, что оно должно удовлетворять следующим правилам:

mappend mempty x = x

mappend x mempty = x

mappend x (mappend y z) = mappend (mappend x y) z

mconcat = foldr mappend mempty

Эти правила не "изобретены" для Хаскелла: моноид является хорошо известной алгебраической структурой. Обычно в математике моноид обозначается как 3-кортеж. Например, (N, +, 0) с N установленным здесь (например, натуральными числами), + двоичной функцией и 0 единичным элементом.

Answer 2

Это отличный вопрос, с которым я уже несколько раз играл. Фактически, это было одно из первых применений вселенной, которое я когда-либо придумал, и я до сих пор думаю, что это изящное. Итак, позвольте мне показать вам!

Вот идея: мы собираемся использовать пакет юниверса, чтобы перечислить все возможные реализации mempty а также mappend, а затем проверьте, какие из них соответствуют законам. Во-первых, несколько шаблонов:

import Data.Universe
import Data.Universe.Instances.Reverse

data Bull = Fools | Twoo deriving (Bounded, Enum, Eq, Ord, Read, Show)
instance Universe Bull
instance Finite Bull

Это просто импортирует соответствующие биты пакета и определяет ваш тип. Теперь давайте закодируем моноидные законы. Мы хотим, чтобы наши mappend быть ассоциативным; пишу (+) за mappend, мы можем потребовать:

associative        (+) = all (\(x,y,z) -> (x+y)+z == x+(y+z)) universe

Законы о идентичности очень похожи друг на друга и связывают наши mappend нашим mempty (который мы назовем (+) а также zero Вот):

leftIdentity  zero (+) = all (\x -> zero+x == x) universe
rightIdentity zero (+) = all (\x -> x+zero == x) universe

Моноид должен удовлетворять всем трем законам:

monoid (zero, (+)) = associative (+) && leftIdentity zero (+) && rightIdentity zero (+)

И теперь мы можем составить список всех моноидов, просто отфильтровывая те, которые соответствуют законам:

monoidsOnBull :: [(Bull, Bull -> Bull -> Bull)]
monoidsOnBull = filter monoid universe

Давайте проверим это в ghci:

> mapM_ print monoidsOnBull
(Twoo,[(Fools,[(Fools,Fools),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])
(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Fools)])])
(Twoo,[(Fools,[(Fools,Twoo),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])
(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Twoo)])])

(В сторону: как мы должны прочитать этот вывод? Ну, пакет юниверса показывает функции типа a -> b показывая свой график типа [(a, b)] то есть списки пар входов и выходов. Каждая строка вышеприведенного вывода представляет собой кортеж с подходящим mempty в первой части и подходящий mappend во второй части.)

Так что же делают эти моноиды? Давайте возьмем их по одному:

(Twoo,[(Fools,[(Fools,Fools),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])

Здесь mappend выходы Fools если оба входа Twoo, То есть это Bull эквивалент (&&), Личность для (&&) является True -- или же Twoo, в Bull дело.

(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Fools)])])

это mappend выходы Fools если его два входа равны, и Twoo иначе. Вы можете думать об этом как что-то вроде xor на Bool или добавление двух дополнений к 1-битным числам. Его личность Fools (или ноль).

(Twoo,[(Fools,[(Fools,Twoo),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])

Этот похож на последний, но везде отрицается.

(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Twoo)])])

Этот похож на первый, но везде отрицается. Это также случается так же, как (||) на Bool, который имеет идентичность False,

На этом лекция заканчивается, но есть еще две забавные заметки, которые стоит добавить.

Первый, base предлагает All а также Any моноиды, когда вы хотите, чтобы ваш mappend быть (&&) а также (||) соответственно. Насколько я знаю, нет подходящего нового типа, чтобы получить xor или его отрицание как Monoid; но вы можете подделать его, объявив Num экземпляр для Bool (с использованием Word1 интуиция, которая False 0 и True 1) чтобы получить его через Sum Bool,

А во-вторых, другой ответ здесь: какой моноид есть для data Color = Red | Green | Blue? У нас есть все возможности, чтобы ответить на этот вопрос сейчас и подтвердить, что на самом деле существует довольно много моноидов:

> length monoidsOnColor
33

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

Answer 3

Для данного набора не существует ни одного моноида (или типа в Haskell). Фактически, идентичность в моноиде определяется не набором, на котором он определен, а скорее операцией (которая называется mappend в Хаскеле). Например, моноид на целых числах может быть определен при сложении (с тождеством 0) или на продукт (с удостоверением личности 1).

Вот почему Sum и Product Существуют типы: так как существует несколько возможных реализаций Monoid класс типов на множестве Num a => a мы предпочитаем обернуть его в newtype и определить Monoid реализация на завернутый тип.

Есть аналогичные конструкции для Bool тип, с All моноид на булевы под конъюнктурой ((&&)) с личностью True, а также Any моноид на логические числа при дизъюнкции ((||)) с личностью False, Фактически, логические значения могут образовывать моноиды на множестве других операций (например, на воротах XOR и XNOR).

Так как Bull тип изоморфен Bool тип (оба имеют ровно два нулевых конструктора), вы можете вдохновить себя на реализацию Monoid на Bool, но мы не можем решить, какая реализация лучше всего подходит в вашем случае с дополнительным контекстом.

Кроме того, как отметил Антон Сюэ, даже если бы вы могли определить моноид для Bull это действительно имеет смысл? Какой ваш тип должен представлять?