在左折叠中构建列表的最有效方法是什么？

Question

在构建列表时，我通常使用右折叠，因为这样可以使用右关联的: 运算符而不影响结果列表的顺序。在左折叠中，我可以使用++，但我了解到这将导致在生成列表时重复复制列表，对于N个元素的列表，这将产生O(N^2)的操作，这通常是不可接受的。

所以，在必须使用左折叠时（在我的特定情况下，这是因为我正在使用foldlM和产生的单子动作必须按从左到右的顺序执行），除了使用: 构建折叠列表并翻转结果之外，还有更好的方法吗？

- Jules

---

在更新的版本中，Data.Foldable.foldl 是基于 foldr 定义的，以便与其他操作进行融合。reverse 应该是其中之一，因此您只需使用 reverse $ foldl ... 就可以得到一个相当高效的版本。至少这是我的猜测。 - Bakuriu

不，reverse 不参与列表融合。 - Joachim Breitner

Answer 1

当我需要使用左折叠（因为产生的单子动作必须按从左到右的顺序执行）时

右折叠可以向右倾斜，以至于再次回到左边。例如，您可以使用右折叠从左往右打印（即单子动作）每个数字并计算列表的部分和：

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' :)构建的，并且单子动作从左到右执行，即使它是一个右折叠。

- behzad.nouri

Answer 2

既然你提到了 foldlM，可能我的这篇博客文章能够详细回答你的问题：

在单子中构建列表

最重要的是：使用差异列表；也就是说，在左折叠中，你累积一个类型为[a] -> [a]的值，在其中可以使用 . (x:) 高效地添加值，并在最后将此函数应用于 [] 以获取列表。

- Joachim Breitner

---

区别列表是否比累加列表然后反转它更好？ - dfeuer

啊，我猜你也这样发现了。我很惊讶；在其他情境中，我见过反转技巧略胜一筹。整个情况有点不尽如人意。我希望能够看到一个安全的 IO 交错组合器，它允许 IO 惰性地生成值，但 不 允许惰性评估驱动 IO。一种类似于 lazyFixIO 的东西。 - dfeuer

我同意；一个“这里有一个带有空洞的表达式，稍后我会填补它”的组合子会很好。但无论如何，这将是对某个闭包的可变更改，而运行时/GC总是会惩罚它。 - Joachim Breitner