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

Question

在构建列表时,我通常使用右折叠,因为这允许我使用右关联:运算符而不影响结果列表的顺序.在左侧折叠中,我可以使用++,但据我所知,这将需要在生成列表时重复复制列表,为N元素列表提供O(N ^ 2)操作,这通常是不可接受的.

因此,当我必须使用左侧折叠时(在我的具体情况下,这是因为我正在使用foldlM并且所产生的monadic动作必须以从左到右的顺序执行),除了构建之外,还有更好的方法来协调它折叠中的列表使用:和反转结果？

Answer 1

当我必须使用左折(...因为...产生的monadic动作必须以从左到右的顺序执行)

右折叠可以向右倾斜,使其再次向左返回.例如,您可以打印(即monadic动作)每个数字,并使用右侧折叠从左到右计算列表的部分总和:

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' :)并且monadic动作是从左到右执行的,即使它是正确的折叠.