在LTree上求逆函数

Question

在LTree中，定义为：

data LTree a = Leaf a | Fork (LTree a) (LTree a)

我创建了一个列表，其中包含所有的leafs和相应的级别，如下所示：

cross :: LTree a -> [(a,Int)]
cross (Leaf x) = [(x,0)]
cross (Fork e d) = map (\(x,n) -> (x,n+1)) (cross e ++ cross d)

现在我要创建反函数：

build :: [(a,Int)] -> LTree a

因此，构建(交叉a) =a对于每一个LTree a

非常感谢您提前！

Answer 1

这里有一些提示。

第一个提示:编写一个辅助函数，给定一个级别，它“消耗”列表中的对，并为该级别构建一个子树。它返回子树和列表的其余部分(尚未使用的对)。这有类型

aux :: Int -> [(a, Int)] -> (Tree a, [(a, Int)])

示例：

aux 1 [('a', 2), ('b', 2)]
  -- a subtree at level 1 which has leaves at level 2
  = (Fork (Leaf 'a') (Leaf 'b'), [])
aux 0 [('a', 2), ('b', 2), ('c', 1)]
  -- no leaf remains
  = (Fork (Fork (Leaf 'a') (Leaf 'b')) (Leaf 'c'), [])
aux 1 [('a', 2), ('b', 2), ('c', 1)]
  -- a leaf remains
  = (Fork (Leaf 'a') (Leaf 'b'), [('c', 1)])
aux 2 [('a', 2), ('b', 2), ('c', 1)]
  = (Leaf 'a', [('b', 2), ('c', 1)])
aux 0 [('a', 0)]
  = (Leaf 'a', [])

第二个提示:要实现aux，首先将级别与列表中第一对中的级别进行比较。

在实现aux之后，很容易从它派生出build函数。(如何？)