Haskell - 如何基于二叉树的文件夹创建 mapTree 函数？

Question

这是“Haskell Programming from first principles”第 11 章代数数据类型中的一道题:

data BinaryTree a =
  Leaf
  | Node (BinaryTree a) a (BinaryTree a)
  deriving (Eq, Ord, Show)

我们实际上并没有将一个值插入到现有的树中；每次我们想向数据结构中插入一个值时，我们都会构建一棵全新的树:

insert' :: Ord a => a -> BinaryTree a -> BinaryTree a
insert' b Leaf = Node Leaf b Leaf
insert' b (Node left a right)
  | b == a = Node left a right
  | b < a = Node (insert' b left) a right
  | b > a = Node left a (insert' b right)

这是二叉树数据结构的映射函数:

mapTree :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree _ Leaf = Leaf
mapTree f (Node left a right) = 
  Node (mapTree f left) (f a) (mapTree f right)

为二叉树写入文件夹

根据我们提供的 BinaryTree 的定义，为二叉树编写一个变形。

-- any traversal order is fine
foldTree :: (a -> b -> b) 
  -> b 
  -> BinaryTree a 
  -> b

上面的类型是对那些在应用折叠功能之前不将树转换为列表的人的提示。

为二叉树重写映射

使用您刚刚编写的 foldTree，使用 foldTree 重写 mapTree。 没有 Ord 约束是有意的，您不需要使用插入功能。

mapTree' :: (a -> b)
  -> BinaryTree a
  -> BinaryTree b
mapTree' f bt =
  foldTree undefined undefined undefined

在以下方面的大量帮助下，我设法得到了适用于第一个有关 foldr 的问题的答案: https://github.com/johnchandlerburnham/hpfp/blob/master/11/BinaryTree.hs

我的回答:

foldTree f b Leaf = b
foldTree f b (Node left a right) 
  = (foldTree f tempb left) where
    tempb = (f a) tempright
    tempright = foldTree f b right

但是，对于第二个关于为二叉树编写新的 mapTree 的问题，我找不到答案。上面提供了原始的 mapTree。即使是 johnchandlerburnham link 处的答案使用不同的折叠树。

有人可以根据我对第一个问题的回答，帮助获得第二个问题的可行答案吗？或者是否需要第一个问题的另一个答案？

用于测试的树可以是:

testTree :: BinaryTree Integer
testTree =
  Node (Node Leaf 3 Leaf) 1 (Node Leaf 4 Leaf)

Answer 1

您不能使用具有该签名的 foldTree 编写 mapTree。 (正如@chi 指出的那样，技术问题是 foldTree 的签名错误，无法成为 BinaryTree 的真正变形。)事实上，如果您加载链接的 Haskell 文件BinaryTree.hs ，您会看到那里的 mapTree' 无法正常工作:

λ> :l BinaryTree
λ> mapTree (+1) testTree
Node (Node Leaf 2 Leaf) 3 (Node Leaf 4 Leaf)
λ> mapTree' (+1) testTree
Node (Node (Node Leaf 3 Leaf) 2 Leaf) 4 Leaf

它给出了正确的节点值，但是树的结构是错误的。

我没有那本书的副本，所以我无法确切地看到你所看到的，但也许 these notes会有帮助。在 11.15 节的最后，作者谈到了 foldTree 的 2 参数和 3 参数版本，并表明只有 mapTree' 编写为使用 3 参数版本将正常工作。