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

这是《Haskell 编程的第一原理》第 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)

这是BinaryTree数据结构的映射函数：

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)

为二叉树编写foldr

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

-- 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

在以下方面的大量帮助下，我设法得到了适用于第一个问题的答案：https://github.com/johnchandlerburnham/hpfp/blob/master/11/BinaryTree.hs 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

然而，对于关于为 BinaryTree 编写新的 mapTree 的第二个问题，我找不到答案。上面提供了原始的mapTree。甚至连答案都在约翰钱德勒伯纳姆链接 https://github.com/johnchandlerburnham/hpfp/blob/master/11/BinaryTree.hs使用不同的折叠树。

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

用于测试的树可以是：

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

你不能写mapTree用一个foldTree与那个签名。 （正如 @chi 指出的，技术问题是foldTree有错误的签名是真正的变形BinaryTree.) 事实上，如果您加载链接的 Haskell 文件BinaryTree.hs https://raw.githubusercontent.com/johnchandlerburnham/hpfp/master/11/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

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

我没有那本书的副本，所以我无法确切地看到你所看到的内容，但也许这些笔记 https://gist.github.com/DadgadCafe/7b544493bb440be3b440ecdbc3581660会有帮助的。在11.15节的最后，作者讨论了2参数和3参数版本foldTree，并且表明只有mapTree'使用 3 参数版本编写的代码将正常工作。