haskell - 在左侧折叠中构建列表的最有效方法？

Question

构建列表时，我通常使用右折叠，因为这样我可以使用右关联 : 运算符，而不会影响结果列表的顺序。在左侧折叠中，我可以使用 ++，但我知道这将需要在生成列表时重复复制列表，从而为 N 元素列表提供 O(N^2) 操作，这通常是 Not Acceptable 。

因此，当我必须使用左折叠时(在我的具体情况下，这是因为我正在使用 foldlM 并且产生的单子(monad)操作必须在左侧执行-从右顺序)，除了使用 : 在折叠中构建列表并反转结果之外，还有其他更好的方法来协调此问题吗？

Answer 1

when I have to use a left fold (... because ... the monadic actions produced must be performed in left-to-right order)

右折叠可以向右倾斜太远，以至于再次向左倾斜。例如，您可以打印(即单子(monad)操作)每个数字并使用右折叠从从左到右计算列表的部分和:

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