使用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。