How can foldl be fast?

Learn
#1

I am learning about reversing lists. :grinning_face_with_smiling_eyes:

I know how to do it super slow with recursion and (++), and I know how to do it reasonably fast with recursion and an accumulator.

Now I am looking into doing it with a fold... function. A simple

rev1r :: [a] -> [a]
rev1r lst = foldr (\x l -> x:l) [] lst

does not do the trick, because it builds up the new list the same way it ā€œateā€ the source list. But foldl seem to be exactly what I need here!:

rev1l :: [a] -> [a]
rev1l lst = foldl (\l x -> x:l) [] lst

I have read everywhere that foldl is super slow because it stacks all intermediate terms up before it resolves them. (Note: I am not allowed to use foldl' because it is not in the Prelude.) So I test my rev1l with something big:(*)

rev1l (3:(take 1000000 [1,1..]))) !! 1000000

However, this seems to run as fast as the standard reverse.

So my question is: How can foldl be so fast? Do I overlook something?

(*) I use the added 3 which I print out to make sure GHC canā€™t opimise things out.

#2

foldl stacks intermediate terms up, as you say.

Often, a fold is used to reduce a list to a single value such as a number, that can be stored very compactly. In that case, creating this series of ā€œstacked-upā€ expressions requires much more space than the end result, and the combined expressions then need to be evaluated to get the result. So this unnecessary intermediate step wastes time and memory.

But the end result of your function rev1l is another list. And a list in Haskell is just multiple values joined together with a lazy cons operation (:). So, with rev1l, the ā€œintermediateā€ expression is exactly the same as the end result, which is the reversed list.

To illustrate, according to the documentation for foldl,

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

Applying this to rev1l:

rev1l [1..4] == ((([] `f` 1) `f` 2) `f` 3) `f` 4
  where f l x = x : l

And since f is just a flipped version of the : operator, this is equivalent to:

rev1l [1..4] == 4 : (3 : (2 : (1 : [])))

And that is just the desugared way of writing [4,3,2,1]. So the ā€œintermediateā€ result is identical to the end result you wanted, the reverse list.

1 Like
#3

Hmm, where? Youā€™re more likely to read it uses a lot (O(n)) of memory, not that itā€™s super slow. Using memory costs time, so itā€™s a bit slower in consequence, but time is not really the main problem with foldl.

2 Likes
#4

Doh! Thatā€™s it. Thanks for pointing it out. Totally clear now.