1

我想让我的 Trie 数据结构可折叠。基本数据结构如下所示：

data Trie a = Trie {
    value :: Maybe a,
    children :: [(Char, Trie a)]
} deriving (Show)

我试图通过定义 foldr 来实现 Foldable 类：

instance F.Foldable Trie where
    foldr f z (Trie (Just v) children) =
        F.foldr (\a b -> F.foldr f b a) (f v z) children

    foldr f z (Trie Nothing children) =
        F.foldr (\a b -> F.foldr f b a) z children

这不会与此错误一起编译：

Couldn't match type `a' with `Trie a'
  `a' is a rigid type variable bound by
      the type signature for foldr :: (a -> b -> b) -> b -> Trie a -> b
      at Trie.hs:17:5
Expected type: [(Char, a)]
  Actual type: [(Char, Trie a)]
In the third argument of `F.foldr', namely `children'
In the expression:
  F.foldr (\ a b -> F.foldr f b a) (f v z) children

但是，如果我将子项的类型更改为Map Char (Trie a)，则 Foldable 实现无需更改即可工作。为了简单起见，我现在想保留关联列表。你能解释一下为什么 foldr 在地图和关联列表上的行为不同吗？

4

1 回答 1

3

该错误是因为您试图折叠键值对列表，而不是Tries 列表。您想要做的是忽略Char 键并像这样折叠到每个子节点中

foldr f z (Trie (Just v) children) =
    F.foldr (\(_, a) b -> F.foldr f b a) (f v z) children

foldr f z (Trie Nothing children) =
    F.foldr (\(_, a) b -> F.foldr f b a) z children
于 2013-01-30T15:48:27.360 回答