8

我正在为一个硬件问题编写一个小代码，它要求我们将树的定义定义为函子和可折叠的实例。当我写下面的代码时：

 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

再次感谢！

4

1 回答 1

8

你不能这样写： 

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

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

fmap f (Node t) = fmap f t

但实际上那里还有另一个错误。的结果fmap仍然需要是 aTree所以你需要把结果放回里面 a Node：

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

就像你已经在处理这个Leaf案子一样。

您可以将其fmap视为修改结构内部值的东西，但根本不改变结构的形状。IE。映射到一个列表将产生一个相同长度的列表，映射到一个树应该产生一个相同的树，具有所有相同的分支，但在叶节点中具有不同的值。

您可以将 afold视为完全删除结构的东西，然后找到一种方法将叶节点中的所有值组合成一个值。帮助类型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实例组合的值。

于 2013-11-14T22:32:28.627 回答