Получение идентификатора для параметра типа? - PullRequest
Новая
       19

Получение идентификатора для параметра типа?

2 голосов
/ 12 мая 2019

У меня есть следующий тип, который я хочу быть экземпляром Monoid typeclass. Я не знаю, как задать параметризованное поле для идентификатора. Есть ли способ использования параметризованного типа для получения идентификатора этого типа? 

data Tree a=Leaf a | Node a (Tree a) (Tree a) |Empty deriving (Eq,Show)

instance Monoid Tree where
    mempty=Empty
    mappend a Empty=a
    mappend a b=Node (identity) x y

Как видите, мне нужно, чтобы в простом поле была установлена ​​идентичность типа параметра.

Пример 

mappend::Tree Int
mappend (Leaf 1) (Leaf 2)=Node 0 (Leaf 1) (Leaf 2)

mappend::Tree []
mappend (Leaf [1,2])(Leaf [2,3])=Node [] (Leaf [1,2])(Leaf [2,3])

Ответы [ 2 ]

9 голосов
/ 12 мая 2019

Это может произойти только в том случае, если сам a также относится к типу Monoid, поэтому мы можем записать это как: 

instance <b>Monoid a</b> => Monoid (Tree <b>a</b>) where
    mempty = Empty
    mappend Empty a = a
    mappend a Empty = a
    mappend a b = Node <b>mempty</b> a b

Вышеуказанное не будет работать для Int, так какInt не является Monoid.Есть два очень популярных кандидата (ℕ, +, 0) и (ℕ, ×, 1) .Однако вы можете использовать Sum, который представляет собой представление первого моноида.

Таким образом, mempty в теле последней строки не mempty, которое мы определяем, но mempty типа a.

При этом, если вы определяете Monoid Tree таким образом, это означает, что вы считаете,Node mempty (Node mempty a b) c == Node mempty a (Node mempty b c), поскольку это требуется согласно законам моноидов .Таким образом, deriving Eq не совсем в « гармонии » здесь с mappend.Оператор mappend (в математике обычно обозначаемый как ⊕ ) должен удовлетворять условию , a, b, c∈ S: a⊕ (b⊕c) = (a⊕b) ⊕c .

Вы должны либо реализовать Eq самостоятельно, либо попытаться придумать другую структуру для своего моноида.

2 голосов
/ 12 мая 2019

Это не ответ, но он слишком длинный для комментария. Как предполагает Виллем Ван Онсем, ваш Monoid экземпляр не является законным. Я подозреваю, что вы, вероятно, хотите одну из двух вещей:

Свободная магма

Свободная магма над типом может быть определена 

data Magma a = Branch (Magma a) (Magma a) | Leaf a | Empty
  deriving Show

Это, естественно, не моноид, но иногда полезно притвориться это одно: 

instance Monoid (Magma a) where
  mempty = Empty
  mappend = Branch

-- For recent GHC, add this instance
instance Semigroup (Magma a) where
  (<>) = Branch

Это можно использовать со сгибом, чтобы лучше понять структуру этого сгиба. Чтобы понять, как это работает, сравните результаты применения foldMap Leaf к [1..20], Data.Sequence.fromList [1..20] и Data.Set.fromList [1..20].

A (конкретная) свободная монада

Подумайте об обобщении вашего дерева, чтобы разрешить разные типы во внутренних узлах, чем в листьях: 

data Tree a b = Node a (Tree a b) (Tree a b) | Leaf b
  deriving (Show, Eq)

(Получается, что это свободная монада над функтором Tree a, определенная 

data TreeF a b = NodeF a b b

но нам не нужно вдаваться в подробности того, что это значит.)

Операция монады для монады Tree a является своего рода «прививкой», когда листья заменяются деревьями. 

instance Functor (Tree a) where
  fmap f (Leaf b) = Leaf (f b)
  fmap f (Node a l r) = Node a (fmap f l) (fmap f r)

instance Applicative (Tree a) where
  pure = Leaf
  (<*>) = ap
  liftA2 = liftM2

instance Monad (Tree a) where
  Leaf b >>= f = f b
  Node a l r >>= f = Node a (l >>= f) (r >>= f)

Вы можете думать, что >>= поддерживает своего рода вертикальное добавление, когда дерево растет вниз от своих листьев.

...