Как обрабатывать экземпляр класса типов, требующий дополнительных ограничений типа - PullRequest
Новая
       10

Как обрабатывать экземпляр класса типов, требующий дополнительных ограничений типа

0 голосов
/ 04 сентября 2018

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

data Trie a = Node {
    label :: a,
    edges :: DM.Map a (Trie a),
    isFinal :: Bool
}

в то время как экземпляр для Show: 

import qualified Data.Tree as DT

instance (Show a, Eq a, Eq (Trie a)) => Show (Trie a) where
    show trie@(Node label edges _) = DT.drawTree (mapTree show $ toDataTree trie)

Я потребовал Eq a и Eq (Trie a) здесь, так как я использую toDataTree, который преобразует Trie a в DT.Tree a и влечет за собой следующие ограничения типа: 

import qualified Data.Map as DM

toDataTree :: (Eq a, Eq (Trie a)) => Trie a -> DT.Tree a
toDataTree (Node label edges isFinal)
    | edges == DM.empty = DT.Node label (map toDataTree (DM.elems edges))
    | otherwise = DT.Node label []

mapTree :: (a -> b) -> DT.Tree a -> DT.Tree b
mapTree f (DT.Node rootLabel subForest) = DT.Node (f rootLabel) $ map (mapTree f) subForest

Теперь, когда это компилируется, когда я на самом деле хочу вызвать print на Trie a (где a = Char в данном случае), я получаю 

• No instance for (Eq (Trie Char)) arising from a use of ‘print’
• In a stmt of an interactive GHCi command: print it

Это должно быть потому, что мне нужно было добавить эти дополнительные ограничения типов к экземпляру Show. Так что мой подход, вероятно, неверен.

Какое правильное решение для дополнительных ограничений типов требуется для определения экземпляра класса типов?

1 Ответ

0 голосов
/ 04 сентября 2018

Я полагаю, в вашей программе есть ошибка в toDataTree, и вы имели в виду: 

| edges /= DM.empty = ...

Однако вам не нужно Eq экземпляров, чтобы проверить, что карта пуста. Если вместо этого вы используете DM.null, вы можете удалить ограничения Eq с toDataTree и с экземпляра Show: 

toDataTree :: Trie a -> DT.Tree a
toDataTree (Node label edges isFinal)
    | not (DM.null edges) = DT.Node label 
                             (map toDataTree (DM.elems edges))
    | otherwise = DT.Node label []

На самом деле, если карта пуста, то отображение ее элементов в любом случае создаст пустой список, так что вы можете еще больше упростить это до: 

toDataTree :: Trie a -> DT.Tree a
toDataTree (Node label edges isFinal)
  = DT.Node label (map toDataTree (DM.elems edges))

В любом случае, это должно решить вашу непосредственную проблему.

Если оставить все это в стороне, причина ошибки в том, что вы не предоставили ни одного экземпляра Eq для Trie. Вы можете добавить предложение deriving (Eq) в определение для Trie: 

data Trie a = Node {
    label :: a,
    edges :: DM.Map a (Trie a),
    isFinal :: Bool
} deriving (Eq)

Это может дать вам страшное предупреждение о хрупких внутренних привязках, но вы можете удалить ограничения Eq (Trie a) (поскольку они будут подразумеваться ограничением Eq a) как из экземпляра Show, так и из toDataTree, чтобы сделать предупреждение исчезнет.

Тем не менее, как уже упоминалось, вы на самом деле не хотите этого делать, потому что лучше использовать DM.null и полностью обходить экземпляры Eq.

...