haskell - 尝试在Haskell中 build 树木

我正在尝试使用展开功能来构建树。

Tree t = Leaf | Node (Tree t) t (Tree t)

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

构建功能需要创建一棵树，该树的高度等于提供的数字，并以有序方式编号。基本情况是构建0 =叶子，下一个是构建1 =节点（叶子0叶子）。

build :: Integer -> Tree Integer

我试图解决它：

build n = unfoldT (\x -> Just x) [0..2^n-2]

我不完全确定如何在此处构建树。
如果有人能指出我正确的方向，我会喜欢的。

编辑1：

如果我要使用2元组，那我应该合并什么？我需要能够以某种方式引用当前节点，其左侧子树和右侧子树，对吗？

最佳答案

如果我要使用2元组，那我应该合并什么？


我建议传递剩余的深度以及从左侧的偏移量：

build = unfoldT level . (0,)
  where
    level (_, 0) = Nothing
    level (o, n) = let mid = 2^(n-1)
                   in ((o, n-1), o+mid-1, (o+mid, n-1))