利用高阶函数的Ltree逆交叉函数

Question

我正在解决一些Haskell练习，作为刷新一些语言概念的方法。

我遇到以下情况：

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

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

上面的函数基本上是接受一个Ltree，并变成一个部分列表(列出树的叶子，以及它们的深度)。

练习是使一个函数build :: [(a,Int)] -> LTree a，它做crossing函数的逆函数，例如任何'a‘树的build (crossing a) = a。

我到目前为止所做的事：

build :: [(a,Int)] -> LTree a
build l = fst (multConvert (map (\(x,n) -> (Leaf x, n)) l))

multConvert :: [(LTree a,Int)] -> (LTree a,Int)
multConvert [x] = x    
multConvert l = multConvert (convert l)

convert :: [(LTree a,Int)] -> [(LTree a,Int)]
convert [] = []
convert [x] = [x]
convert ((a,b):(c,d):xs) | b == d = ((Fork a c),(b-1)):xs
                         | otherwise = (a,b):convert ((c,d):xs)

基本上，我将crossing生成的列表转换为(LTree，a)列表，例如，[(3,3),(4,3)..]变成[(Leaf 3, 3), (Leaf 4, 3)...]。convert函数将接受这个(LTree,a)列表，并将具有相同深度的连续元素转换为具有这两个元素的Fork。例如，[(Leaf 3, 3), (Leaf 4, 3), (Leaf 5, 2)...]变成了[(Fork (Leaf 3) (Leaf 4),2), (Leaf 5, 2)...]。注意，新产生的元素具有深度-1。

multConvert函数会一次又一次地在列表上应用上面的思想，直到这个列表只有一个元素。此元素将表示原始树。换句话说，我的算法使用自下而上的方法构建Ltree。

我想知道是否有更有力的方法来解决这个问题。例如，使用高阶函数，而不是显式递归(可能使用foldr)。

Answer 1

我认为这是一个用于编写build的延续传递解决方案(简单解析器)：

build :: [(a,Int)] -> LTree a
build xs = parseAt 0 xs fst

-- The first Int is the depth of the "root" of parseAt
parseAt :: Int -> [(a,Int)] -> ( (LTree a, [(a,Int)]) -> r ) -> r
parseAt r [] k = error "input too short"
parseAt r xs@((a,n):rest) k =
  case compare r n of
    GT -> error "depth too small"
    EQ -> k (Leaf a,rest)
    LT -> parseAt (succ r) xs (\ (left,rest1) ->
            parseAt (succ r) rest1 (\ (right,rest2) ->
              k (Fork left right, rest2)))