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.
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.
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.