haskell - 可折叠和树木

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 类型的实例声明中使用 t 而不是 a？

Answer 1

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

问题在于：

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

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

顺便说一句，GHC 可以自动为您派生 Foldable 实例（以及 Functor 和 Traversable）。写吧

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