Как определить `mempty` для этого типа` Or`? - PullRequest
Новая
       76

Как определить `mempty` для этого типа` Or`?

0 голосов
/ 23 октября 2018

В книге «Программирование на Haskell из первых принципов» есть упражнение, в котором меня просят создать экземпляр Monoid для типа Or: 

data Or a b =
  Fst a
  | Snd b
  deriving (Eq, Show)

. Ранее мы определяли правила при создании экземпляра * 1006.*: 

instance Semigroup (Or a b) where
  (Fst _) <> (Fst y) = Fst y
  (Fst _) <> (Snd y) = Snd y
  (Snd x) <> (Fst _) = Snd x
  (Snd x) <> (Snd _)= Snd x

в соответствии с вышеуказанными правилами, очевидно, Fst x должно быть mempty, если это был моноид, где x - это что-то типа a.Но я не знаю, как написать правила: 

instance (Monoid a, Monoid b) => Monoid (Or a b) where
  mempty = ???  -- Please help me with this, to make every (Fst x) be mempty.
  mappend = (<>)

1 Ответ

0 голосов
/ 23 октября 2018

Короче говоря : ваше определение для (<>) не может использоваться в качестве бинарного оператора для моноида.Если только вы не можете гарантировать, что существует только одно возможное значение для a (или b, если мы используем Snd в качестве конструктора для "нейтрального элемента").

в соответствии с вышеизложеннымправила, очевидно, Fst x должен быть mempty, если это был Monoid.

Точно, , если это был моноид [вики] .Но для моноида можно доказать, что существует * точно один элемент идентичности.Доказательство состоит в следующем: если есть два нейтральных элемента e 1 и e 1 , то это означает, что e 1 *e 2 = e 1 , но в то же время e 1 *e 2 = e 2 (поскольку a⊕e = e⊕a = a выполняется с e единичным элементом), что означаетчто e 1 = e 2 имеет место, и, таким образом, они совпадают.

Теперь в вашем определении (<>) естьнет такой элемент идентичности.В самом деле, скажите, что этот элемент Fst e, тогда он должен содержать следующее: 

Fst e <> Fst a = Fst a

, которое содержит (первая строка вашего определения), но он также должен содержать следующее: 

Fst a <> Fst e = Fst a

и это, согласно вашей функции (<>), будет удерживаться, только если a равно e.Таким образом, единственный способ объявить это моноидом - это определить только одно значение в конструкторе Fst, как, например, @ leftroundabout , например: 

instance Monoid (Or () b) where
    mempty = Fst ()
    mappend = (<>)

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

Теперь все еще возможно, что элемент идентификации имеет форму Snd e, но опять же: 

(Snd x) <> (Snd e) = Snd x
(Snd e) <> (Snd x) = Snd x

должны оба храниться, тогда как в вашей реализации: 

(Snd x) <> (Snd _)= Snd x

последнее не будет выполняться (поскольку x может отличаться от e).

...