foldl with (++) is a lot slower than foldr

Question

Why is foldl slower than foldr sometimes ? I have a list of lists "a" like

a = [[1],[2],[3]]

and want to change it to a list by using fold

foldr (++) [] a

It works fine (time complexity is O(n)). But if I use foldl instead, it is very slow (time complexity is O(n^2)).

foldl (++) [] a

If foldl is just folding the input list from the left side,

(([] ++ [1]) ++ [2]) ++ [3]

and foldr is from the right side,

[1] ++ ([2] ++ ([3] ++ []))

the number of computations (++) is supposed to be same in both cases. Why is foldr so slow? As per the time complexity, foldl looks as if scanning the input list twice as many times as foldr. I used the following to computer the time

length $ fold (++) [] $ map (:[]) [1..N]   (fold is either foldl or foldr)

Answer 1

It's because of how ++ works. Note that is is defined by induction on its first argument.

[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

The number of recursive calls only depends on length xs.

Because of this, in xs ++ ys it is more convenient to have a small xs and a large ys than the other way around.

Note that folding on the right achieves this:

[1] ++ ([2] ++ ([3] ++ ...

We only have short (O(1)-length) lists on the left of ++, making the fold cost O(n).

Instead folding on the left is bad:

((([] ++ [1]) ++ [2]) ++ [3]) ++ ...

The left arguments become larger and larger. Hence, we get O(n^2) complexity here.

This argument can be made more precise considering how the output list is demanded. One can observe that foldr produces its result in a "streaming" fashion, where demanding e.g. the first output list cell only forces a little part of the input -- only the first ++ needs to be performed, and only its first recursive step is actually needed! Instead demanding even only the first item from the foldl result will force all the ++ calls, making it quite expensive (even if each call only needs one recursive step, there are O(n) calls).