实现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 | BNode a (BinaryTree a) (BinaryTree a)

因此，这意味着它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 l r) = BNode (f x) (treeMap f l) (treeMap f r)

或更优雅：

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：

{-# LANGUAGE DeriveFunctor #-}

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

该treeMap只是fmap :: Functor f => (a -> b) -> f a -> f b用f ~ BinaryTree在这里。