地图功能的BST在Haskell
假设我有BST的数据类型为:地图功能的BST在Haskell
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实现的树)
你忘了节点的值:
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)
而这一切,你必须做的!
我只是在发帖后2分钟就想出了它。尽管感谢您对命名约定的建议! – Walle
偏题:注意'f'必须是单调的以保持BST不变量。 – chi