实现 mapTree 函数

Question

我被要求定义函数：

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

它接受一个函数和一棵二叉树，并生成一棵二叉树，其中所有节点都是在给定树上应用该函数的结果

二叉树是：

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a)

我的代码不符合要求。我收到以下错误：

error: Not in scope: data constructor ‘BinaryTree’
treeMap f (BNode x (BinaryTree l) (BinaryTree r)) =    |                                    ^^^^^^^^^^

我的代码：

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a)

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b
treeMap f Nil  = Nil
treeMap f (BNode x (BinaryTree l) (BinaryTree r)) =
    BNode (f x) (BinaryTree (treeMap f l)) (BinaryTree (treeMap f r))

Answer 1

您的模式 (BNode x (BinaryTree l) (BinaryTree r)) 不是有效模式。事实上，二叉树的数据定义说：

data BinaryTree a = Nil | <b>BNode a (BinaryTree a) (BinaryTree a)</b>

所以这意味着 BNode 是一个包含三个参数的 数据构造函数 。最后两个参数的类型是BinaryTree a，但是不能在模式匹配中使用类型。

因此您应该使用 l 和 r 作为这些参数的变量（或者您可以使用 BinaryTree a 类型的数据构造函数）。

构造BinaryTree a类型时也是如此。您使用 BNode x l r 和 x、l 和 r 值调用构造函数，您没有在此处的表达式中指定类型。您可以指定类型，然后使用 :: 运算符。

因此您可以通过以下方式修复您的代码：

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b
treeMap f Nil  = Nil
treeMap f (BNode x <b>l</b> <b>r</b>) = BNode (f x) <b>(treeMap f l)</b> <b>(treeMap f r)</b>

或更优雅：

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b
treeMap f = go
    where go Nil = Nil
          go (BNode x l r) = BNode (f x) (go l) (go r)

也就是说，您可以让 ghc 为您派生 Functor 实例，方法是使用 DeriveFunctor pragma:

{-# <b>LANGUAGE DeriveFunctor</b> #-}

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a) <b>deriving Functor</b>

这里的 treeMap 就是 fmap :: Functor f => (a -> b) -> f a -> f b 和 f ~ BinaryTree。

实现 mapTree 函数

implementing mapTree function

binary-tree

dictionary

haskell