时间戳

首页 > 解决方案 > 使用 FoldTree 从列表中创建树

haskell - 使用 FoldTree 从列表中创建树

问题描述

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

我已经使用 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)

在考虑了这一点之后，我相信由于类型冲突而无法做到这一点。理论上，当列表不断减少/折叠时，需要在累加器中建立树。

相反，我能够将foldl版本转换为foldr，并且显然foldr可以使用foldTree.

有什么建议么？谢谢！

标签： haskelltreefold

解决方案

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

与列表相关的折叠foldr并foldl使用一个列表（或者更一般地说，一个可折叠的）来产生其他东西（可能不是一个列表）。

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

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

推荐阅读