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

エラーは、のリストではなく、キーと値のペアのリストをフォールドしようとしているためですTrie。あなたがしたいのは、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 に答える