Haskell

Question

这是第 11 章“Haskell 从第一原则编程”的代数数据类型中的问题：

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)

为二叉树写入文件夹

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

-- 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。即使 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 参数版本才能正常工作。

Haskell - 如何根据二叉树的文件夹创建一个mapTree函数？

Haskell - How to create a mapTree function based on a foldr of a BinaryTree?

tree

binary

fold

map-function