Haskell中的树构建功能(家庭作业)

Question

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)

鉴于上面的两条信息,我被要求实现树构建功能.

我的尝试是

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工作？在正常展开中,a中的第一个元素Just将是我想要的元素,第二个元素将用于继续展开,但这在3元组中如何工作？

作为示例输出: 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？

Answer 1

我认为你在粘贴定义时省略了一个空格unfoldTree.应该是这个吗？

unfoldTree f b =
    case f b of ...

有什么本质意义的左右Maybe (b, a, b),但在这种特殊情况下,你可以看到,unfoldTree在元组结合的项目lt,x和rt.的中间值x被用来创建的节点,并且lt和rt被用于接种到递归调用unfoldTree.

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

中间值0+1是树中根节点的值.除了b现在之外,左子树的构建类似2*0,右子树是用bas 构建的2*0+1.

你提到这是一个应该用2^n - 1节点构建树的家庭作业.我将猜测Leaf值不计算,并且您希望以广度优先顺序对这些节点进行编号,并且希望此示例可以将您带到附近.以下是如何做到这一点:

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.

现在的格局是可见的:如果当前节点编号b,他的左边和右边的节点编号2*b+1和2*b+2分别.因为2^n - 1是深度树中的节点总数n,并且我以广度优先顺序对节点进行编号,所以返回Nothing时b >= 2^n-1确保在填充树到深度之后停止n.