Haskell中的树构建功能(作业) [英] Tree building function in Haskell (Homework)

问题描述

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

unfoldTree:: (b -> Maybe (b, a, b)) -> b -> Tree a
unfoldTree f b =
    case f b of
      Nothing -> Leaf
      Just (lt, x, rt) -> Node (unfoldTree f lt) x (unfoldTree f rt)

鉴于以上两点信息，我被要求实现树构建功能.

Given the two piece of information above, I'm asked to implement a tree building function.

我的尝试是

treeBuild :: Integer -> Tree Integer
treeBuild 0 = Leaf
treeBuild n = treeUnfold (\b -> if b < 2^n-1 
                then Just(2*b, b + 1, 2*b + 1) 
                else Nothing) 
                0

在n = 0的情况下可以正常工作的基本情况，但我知道函数完全错误.有人可以向我重新解释3-tuple Just的工作方式吗?在正常展开中，Just中的第一个元素将是我想要的元素，第二个元素将用于继续展开，但这在三元组Just中如何工作?

The base case works where n = 0 works fine but I know the function is completely wrong. Can someone re-explain to me how would a 3-tuple Just work? In a normal unfold, the first element in a Just would be the element I want and the second element would be used to continue unfolding but how does this work in a 3-tuple Just?

作为示例输出: treeBuild 2 ----> Node (Node Leaf 0 Leaf) 1 (Node Leaf 2 Leaf)

我不完全确定Just在这里如何工作，对于Just(2*b, b + 1, 2*b + 1)的情况，其中b从0开始，它是否变为Just(0, 1, 0)?我实际上如何增加b?

I'm not completely sure how Just works here, for the case of Just(2*b, b + 1, 2*b + 1) where b starts at 0, does it become Just(0, 1, 0)? How do I actually increment b?

推荐答案

我认为您在粘贴unfoldTree的定义时省略了空格.应该是这个吗?

I think you omitted a space when pasting the definition of unfoldTree. Should it be this?

unfoldTree f b =
    case f b of ...

关于Maybe (b, a, b)并没有本质上的意义，但是在这种特殊情况下，您可以看到unfoldTree将元组中的项目绑定到lt，x和rt.中间值x用于创建节点，lt和rt用于将对unfoldTree的递归调用植入种子.

There's nothing intrinsically meaningful about Maybe (b, a, b), but in this particular case you can see that unfoldTree binds the items in the tuple to lt, x, and rt. The middle value x is used to create a node, and lt and rt are used to seed the recursive calls to unfoldTree.

要解释示例输出，请注意n始终绑定到2. treeUnfold的初始0参数意味着(\b -> ...)函数首先检查0 < 2^n-1，然后生成Just (2*0, 0+1, 2*0+1).

To explain your example output, note that n is always bound to 2. The initial 0 argument to treeUnfold means the (\b -> ...) function first checks 0 < 2^n-1, then yields Just (2*0, 0+1, 2*0+1).

中间值0+1是树中根节点的值.左子树的构建方式类似，除了b现在是2*0，右子树的构建方式是b作为2*0+1.

The middle value, 0+1 is the value of the root node in your tree. The left subtree is built similarly except b is now 2*0, and the right subtree is built with b as 2*0+1.

您提到这是家庭作业，应该用2^n - 1节点构建一棵树.我猜想Leaf的值不计算在内，并且您想按广度优先的顺序对这些节点进行编号，希望此示例可以使您在附近.这样做的方法如下:

You mention this is homework which is supposed to build a tree with 2^n - 1 nodes. I'm going to guess that Leaf values don't count and that you want to number these nodes in breadth-first order, and hopefully this example gets you in the neighborhood. Here's how to do that:

treeBuild :: Int -> Tree Int
treeBuild n = treeUnfold (\b -> if b < 2^n - 1
                                   then Just (2*b+1, b, 2*b+2)
                                   else Nothing) 0

达到此目的的方式是绘制一棵深度为3的二叉树.我将以根为起点的节点编号为0，将左侧节点编号为1，将右侧节点编号为2.底部的节点从4到7结束从左到右编号.

The way I arrived at this is by drawing a binary tree with depth 3. I numbered the nodes starting with the root as 0, the left node as 1 and the right node as 2. The bottom nodes are numbered from left to right starting with 4 and ending at 7.

现在该模式可见:如果当前节点编号为b，则其左节点和右节点分别编号为2*b+1和2*b+2.由于2^n - 1是深度为n的树中节点的总数，并且我以广度优先顺序对节点进行编号，因此当b >= 2^n-1确保将树填充至深度n.

Now the pattern is visible: if the current node is numbered b, his left and right nodes are numbered 2*b+1 and 2*b+2 respectively. Since 2^n - 1 is the total number of nodes in a tree of depth n, and I'm numbering nodes in breadth-first order, returning Nothing when b >= 2^n-1 ensures I stop after filling the tree up to depth n.

这篇关于Haskell中的树构建功能(作业)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！