如何处理需要额外类型约束的类型类实例

Question

我发现自己处于一种情况，我想要定义的类型类实例需要额外的类型约束。具体来说，我想为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的实例中。所以我的方法可能是错的。

类型类实例定义所需的其他类型约束的正确解决方案是什么？

Answer 1

我认为你的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实例是更好的做法。