树作为仿函数和可折叠的实例

Question

我正在为一个hw问题编写一些代码,它要求我们将树的定义作为functor和foldable的一个实例.当我写下面的代码时:

 import Data.Foldable
 import Data.Monoid

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

 instance Functor (Tree) where
    fmap f (Leaf a) = Leaf (f a) 
    fmap f (Node [Tree a]) = fmap f [Tree a]

 instance Foldable (Tree) where
    foldMap f (Leaf a) = f a
    foldMap f (Node [Tree a]) = foldMap f `mappend` [Tree a]

出现以下错误:

hw.hs:10:19:
Not in scope: data constructor `Tree'
Perhaps you meant `True' (imported from Prelude)

hw.hs:10:38:
Not in scope: data constructor `Tree'
Perhaps you meant `True' (imported from Prelude)

hw.hs:14:22:
Not in scope: data constructor `Tree'
Perhaps you meant `True' (imported from Prelude)

hw.hs:14:54:
Not in scope: data constructor `Tree'
Perhaps you meant `True' (imported from Prelude)
Failed, modules loaded: none.

我哪里错了？

谢谢!

[[更新]]

我根据下面答案中的建议对代码进行了更改.这是带错误的代码的链接.如果有人看看它并告诉我哪里错了,那就太好了.

http://snipt.org/Bahjg5

再次感谢!

Answer 1

你不能写这个:

fmap f (Node [Tree a]) = ...

因为Tree数据类型不是数据构造函数.在模式匹配,你只能使用数据的构造,这将是Leaf或者Node在这种情况下.在这里,您甚至不需要匹配子树的每个构造函数,因为您无论如何都要直接传递整个列表:

fmap f (Node t) = fmap f t

但实际上还存在另一个错误.结果fmap仍然需要是,Tree所以你需要将结果放回到Node:

fmap f (Node t) = Node (fmap f t)

就像你已经在处理Leaf案件一样.

您可以将其fmap视为修改结构内部值的内容,但根本不会更改结构的形状.即.在列表上进行映射将生成相同长度的列表,并且在树上的映射应该生成相同的树,具有所有相同的分支,但在叶节点中具有不同的值.

您可以将a fold视为完全删除结构的内容,然后找到将叶节点中的所有值组合为单个值的方法.foldMap帮助类型:

 foldMap :: (Foldable t, Monoid m) => 
         (a -> m) -- mapping function from `a` to the monoid result
      -> t a      -- A tree node containing values of type `a`
      -> m        -- a monoid

结果foldMap不应该是Tree!它只是值,使用映射函数进行转换并使用它们的Monoid实例进行组合.