地图功能的BST在Haskell

Question

假设我有BST的数据类型为：

data tree a = Empty | Node a (tree a) (tree a) 
        deriving (Show, Read, Eq) 

我做一个简单的地图功能应用BST的每个元素。

treeMap :: (a -> b) -> tree a -> tree b 
treeMap f (Empty) = Empty 
treeMap f (Node left right) = Node (treeMap f left) (treeMap f right) 

但是它给了我一个错误说：

Constructor `Node' should have 3 arguments, but has been given 2 
In the pattern: Node left right 
In the definition of `treeMap': 
    treeMap f (Node left right) 
       = Node (treeMap f left) (treeMap f right) 

如何解决这个问题？ （P/S不是一门功课的问题，试图了解在Haskell实现的树）

Answer 1

你忘了节点的值：

treeMap f (Node a left right) = Node (f a) (treeMap f left) (treeMap f right) 

你需要修复您的data声明，虽然。数据类型必须用大写字母开头：

data Tree a = Empty | Node a (Tree a) (Tree a) 

而且你喜欢的类型签名

treeMap :: (a -> b) -> Tree a -> Tree b 

这实际上是在Haskell一个共同的模式，并且它被赋予了一个名为fmap映射函数名称Functor。列表是最常见的Functor之一，其中fmap只是标准map，但其他许多类型也是Functor。从概念上讲，Functor只是一个通用的容器，您可以将函数应用于每个元素。 Maybe也是Functor，其中fmap f Nothing = Nothing和fmap f (Just a) = Just (f a)。此外，根据定义，任何Monad或Applicative也是Functor，所以如果您可以使用do表示法，那么您可以使用它fmap。

为了您的结构，你可以把它Functor类型类的实例作为

instance Functor Tree where 
    fmap f Empty = Empty 
    fmap f (Node a left right) = Node (f a) (fmap f left) (fmap f right) 

这是完全一样的定义，你treeMap使用不同的名称。此外，GHC居然又获得此实现你的能力，如果你给它的DeriveFunctor扩展：

{-# LANGUAGE DeriveFunctor #-} 

data Tree a = Empty | Node a (Tree a) (Tree a) 
        deriving (Eq, Show, Read, Functor) 

而这一切，你必须做的！