折叠式树木

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]

如何使t在Tree类型的实例声明中而不是在一个实例声明中？

Answer 1

(我假设您在实例声明中缩进了代码，否则编译器会抱怨这一点。)

问题就在眼前：

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

什么是(foldMap mappend .)该怎么做？您将foldMap本身视为一个一元值。我认为你想做的只是foldMap (foldMap f) t。

顺便说一下，GHC可以自动为您导出可折叠的实例(以及函子和可遍历的实例)。只管写

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