haskell - 将函数映射到 Haskell 中的 BST

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 中的常见模式，它被命名为 Functor映射函数称为 fmap 。列表是最常见的之一 Functor s，与 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 的定义完全相同用不同的名字。此外，如果您给它 DeriveFunctor，GHC 实际上能够为您导出此实现。扩展名:

{-# LANGUAGE DeriveFunctor #-}

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

这就是您所要做的!