可折叠和树木

Question

我有一个树的以下定义

 data Tree a = Leaf a
           | Node [Tree a] 
     deriving (Show)

以及可折叠的以下实例:

 instance Foldable (Tree) where
 foldMap f (Leaf t) = (f t)
 foldMap f (Node t) = (foldMap `mappend` (foldMap f) t)     

这段代码引发了我的错误

 Couldn't match type `a' with `Tree a'
  `a' is a rigid type variable bound by
      the type signature for
        foldMap :: Monoid m => (a -> m) -> Tree a -> m
      at trees.hs:8:5
 Expected type: [a]
   Actual type: [Tree a]

如何在Tree a类型的实例声明中而不是？

Answer 1

(我假设您在实例声明中缩进了代码,否则编译器会抱怨它.)

问题在于:

 foldMap f (Node t) = (foldMap `mappend` (foldMap f) t)

什么是(foldMap`mappend` ...)应该做的？您将foldMap本身视为monadic值.我想你想做的只是foldMap (foldMap f) t.

顺便说一句,GHC可以自动为您导出可折叠实例(以及Functor和Traversable).写吧

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
data Tree a = Leaf a
            | Node [Tree a]
  deriving (Show, Functor, Foldable)