在构建列表时,我通常使用右折叠,因为这样可以使用右关联的:
运算符而不影响结果列表的顺序。在左折叠中,我可以使用++
,但我了解到这将导致在生成列表时重复复制列表,对于N个元素的列表,这将产生O(N^2)的操作,这通常是不可接受的。
所以,在必须使用左折叠时(在我的特定情况下,这是因为我正在使用foldlM
和产生的单子动作必须按从左到右的顺序执行),除了使用:
构建折叠列表并翻转结果之外,还有更好的方法吗?
在构建列表时,我通常使用右折叠,因为这样可以使用右关联的:
运算符而不影响结果列表的顺序。在左折叠中,我可以使用++
,但我了解到这将导致在生成列表时重复复制列表,对于N个元素的列表,这将产生O(N^2)的操作,这通常是不可接受的。
所以,在必须使用左折叠时(在我的特定情况下,这是因为我正在使用foldlM
和产生的单子动作必须按从左到右的顺序执行),除了使用:
构建折叠列表并翻转结果之外,还有更好的方法吗?
当我需要使用左折叠(因为产生的单子动作必须按从左到右的顺序执行)时
右折叠可以向右倾斜,以至于再次回到左边。例如,您可以使用右折叠从左往右打印(即单子动作)每个数字并计算列表的部分和:
fun :: [Int] -> IO [Int]
fun xs = foldr go (const $ return []) xs 0
where go x f a = let a' = a + x in print x >> (a' :) <$> f a'
那么:
\> fun [1..5]
1
2
3
4
5
[1,3,6,10,15]
请注意,输出列表是使用(a' :)
构建的,并且单子动作从左到右执行,即使它是一个右折叠。
既然你提到了 foldlM
,可能我的这篇博客文章能够详细回答你的问题:
最重要的是:使用差异列表;也就是说,在左折叠中,你累积一个类型为[a] -> [a]
的值,在其中可以使用 . (x:)
高效地添加值,并在最后将此函数应用于 []
以获取列表。
IO
交错组合器,它允许 IO
惰性地生成值,但 不 允许惰性评估驱动 IO
。一种类似于 lazyFixIO
的东西。 - dfeuer
Data.Foldable.foldl
是基于foldr
定义的,以便与其他操作进行融合。reverse
应该是其中之一,因此您只需使用reverse $ foldl ...
就可以得到一个相当高效的版本。至少这是我的猜测。 - Bakuriu