Нахождение обратной функции на LTree

Question

В виде LTree определяется как:

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

I создает список всех лаврового листа и соответствующего уровня, как это:

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 

Так что строить (скрестить) = а для каждого LTree

Большое вам спасибо!

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. (Как?)