CODEWITHSUNDEEP
haskellfunctional-programmingfold
Jules
Jules

Reputation: 15199

Most efficient way of building a list in a left fold?

When building lists, I usually use a right fold, as that lets me use the right-associative : operator without affecting the order of the resulting list. In a left fold, I could use ++, but I understand that this will entail repeatedly copying the list while it is being produced, giving O(N^2) operations for an N-element list, which is generally unacceptable.

So, when I have to use a left fold (in my specific case this is because I'm using foldlM and the monadic actions produced must be performed in left-to-right order), is there any better way of reconciling this other than building the list in the fold using : and reversing the result?

Upvotes: 3

Views: 331

Answers (2)

behzad.nouri
behzad.nouri

Reputation: 77941

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

Right fold can lean so far right that it comes back left again. For example, you can print (i.e. monadic action) each number and calculate partial sums of a list from left to right using a right fold:

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'

then:

\> fun [1..5]
1
2
3
4
5
[1,3,6,10,15]

note that the output list is built using (a' :) and the monadic action is performed left to right, even though it is a right fold.

Upvotes: 5

Joachim Breitner
Joachim Breitner

Reputation: 25763

Since you mention foldlM, likely this blog post of mine answers your question in depth:

Constructing a list in a Monad

The bottom line is: Use difference lists; i.e. in your left-fold, you accumulate a value of type [a] -> [a], where you can append a value using . (x:) efficiently, and at the end you apply this function to [] to obtain your list.

Upvotes: 3

Related Questions