使用 FoldTree 从列表树

Question

我正在尝试从列表创建树。

我已经使用 foldl 和 foldr 编写了函数（后者未显示）

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

其中树 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)

经过深思熟虑，我认为这是因为类型冲突而无法完成的。理论上，当列表不断 reduced/folded 时，需要在累加器中建立树。

相反，我可以将foldl版本转换为foldr，显然foldr可以用foldTree.

表示

有什么建议吗？谢谢！

Answer 1

您似乎对不同的褶皱感到困惑。

与列表相关的折叠 foldr 和 foldl 使用列表（或者更一般地说，可折叠）来生成其他内容（可能不是列表）。

与树相关的折叠foldTree消耗一棵树来产生其他东西（可能不是一棵树）。

因此，您不能从一个切换到另一个：如果您只有一个列表作为输入，则没有树可以调用 foldTree。

使用 FoldTree 从列表树

Tree From List using FoldTree

tree

haskell

fold