Дерево из списка с использованием FoldTree

Question

Я пытаюсь создать дерево из списка.

Я написал функцию, используя foldl и foldr (последний не показан)

treeFromList l
    | null l = error "no elements in list"
    | otherwise = foldl insertIfAbsent (initTree (head l)) (tail l)

где Tree DS определяется в отдельном модуле как

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving Show

initTree x = (Node x EmptyTree EmptyTree)

и treeFold записывается вручную (не выводится) как

foldTree f acc t
    | (empty t) = acc
    | otherwise = foldTree f outerVal (leftSub t) 
        where
        outerVal = f (value t) rightVal 
        rightVal = foldTree f acc (rightSub t)

Подумав об этом, я считаю, что это невозможно сделать из-за конфликта типов. Теоретически, дерево должно быть построено в аккумуляторе, в то время как список постоянно сокращается / сворачивается.

Напротив, мне удалось преобразовать в foldl версию в foldr, и, очевидно, foldr можно выразить с помощью foldTree.

Есть предложения? Спасибо!

Answer 1

Вы, кажется, смущены различными складками.

Связанные со списком сгибы foldr и foldl используют список (или, в более общем случае, складываемый) для создания чего-то другого (который может не быть списком).

Связанная с деревом складка foldTree использует дерево, чтобы произвести что-то еще (что может не быть деревом).

Следовательно, вы не можете переключаться с одного на другое: если у вас есть только список в качестве входных данных, у вас нет дерева для вызова foldTree с помощью.