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

作为示例输出:treeBuild 2 ---->节点(节点叶子0叶子)1(节点叶子2叶子)

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

Answer 1

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

unfoldTree f b =    case f b of ...

Maybe (b, a, b) 没有任何内在意义，但在这种特殊情况下，您可以看到 unfoldTree将元组中的项目绑定(bind)到 lt , x , 和 rt .中间值x用于创建节点，lt和 rt用于播种递归调用 unfoldTree .

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

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

---

你提到这是应该用 2^n - 1 build 一棵树的作业节点。我猜 Leaf值不重要，并且您想按广度优先顺序对这些节点进行编号，希望这个示例能让您了解情况。以下是如何做到这一点:

treeBuild :: Int -> Tree InttreeBuild 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 .