Haskell-如何基于BinaryTree的文件夹创建mapTree函数? [英] Haskell - How to create a mapTree function based on a foldr of a BinaryTree?

问题描述

这是第11章从第一原理进行Haskell编程"的代数数据类型中的一个问题:

This is a question from Chapter 11, Algebraic Datatypes of "Haskell Programming from first principles":

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

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

We do not actually insert a value into an existing tree; each time we want to insert a value into the data structure, we build a whole new tree:

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数据结构的映射函数:

This is a map function for the data structure of 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)

为BinaryTree编写文件夹

鉴于我们提供的BinaryTree的定义，为二叉树写一个同构关系.

Given the definition of BinaryTree we have provided, write a catamorphism for the binary trees.

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

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

The type above is a hint for those that don’t convert the tree into a list before applying the folding function.

为BinaryTree重写映射

使用您刚刚编写的foldTree，使用foldTree重写mapTree. 没有Ord约束是有意的，您不需要使用insert函数.

Using the foldTree you just wrote, rewrite mapTree using foldTree. The absence of an Ord constraint is intentional, you don’t need to use the insert function.

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

在许多帮助下，我设法获得了一个有关文件夹的第一个问题的答案: https://github.com/johnchandlerburnham/hpfp/blob/master/11/BinaryTree.hs

I managed to get an answer that works for the first question about foldr with a lot of help from: 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.甚至 johnchandlerburnham链接上的答案都使用了不同的折叠树.

However, for the second question about writing a new mapTree for BinaryTree, I could not find an answer to that. The original mapTree is provided above. Even the answer at the johnchandlerburnham link uses a different foldtree.

请问有人可以根据我对第一个问题的回答为第二个问题提供可行的答案吗?还是第一个问题需要另一个答案?

Could someone please help get a workable answer for the second question based on my answer to the first question? Or is another answer for the first question required?

用于测试的树可能是:

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

推荐答案

您不能使用带有该签名的foldTree编写mapTree. (正如@chi所指出的，技术问题是foldTree具有错误的签名，不能真正成为BinaryTree的类同化.)实际上，如果您加载该链接的Haskell文件

You can't write mapTree using a foldTree with that signature. (As @chi notes, the technical problem is that foldTree has the wrong signature to be a true catamorphism for BinaryTree.) In fact, if you load up that linked Haskell file BinaryTree.hs, you'll see that the mapTree' there doesn't work correctly:

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

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

It gives the right node values, but the structure of the tree is wrong.

我没有那本书的副本，所以我看不到您在看什么，但是也许

I don't have a copy of that book, so I can't see exactly what you're seeing, but maybe these notes will be helpful. At the end of section 11.15, the author talks about 2-parameter and 3-parameter versions of foldTree, and shows that only mapTree' written to use the 3-parameter version will work correctly.

这篇关于Haskell-如何基于BinaryTree的文件夹创建mapTree函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！