使用FoldTree从列表中的树

问题描述 投票:-2回答:1

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

我用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表达。

有什么建议?谢谢!

haskell tree fold
1个回答
2
投票

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

与列表相关的折叠foldrfoldl使用一个列表(或者,更一般地说,可折叠)来生成其他东西(可能不是列表)。

树相关的折叠foldTree消耗树以产生其他东西(可能不是树)。

因此,你不能从一个切换到另一个:如果你只有一个列表作为输入,你没有一个树来调用foldTree

© www.soinside.com 2019 - 2024. All rights reserved.