dictionary - 实现 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值，您没有在表达式中指定类型。您可以指定类型，然后使用 ::运算符(operator)。

因此，您可以使用以下方法修复您的代码:

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这里。