地圖功能的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) 

而這一切，你必須做的！