Foldl with (++) is much slower than foldr

Question

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

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

and want to change it to a list using fold

 foldr (++) [] a 

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

 foldl (++) [] a 

If foldl just folds the input list to the left,

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

and foldr is on the right side,

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

the number of calculations (++) should be the same in both cases. Why is foldr so slow? According to the time complexity, foldl looks as if scanning the input list is twice as large as foldr. I used computer time

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

Answer 1

This is due to how ++ works. Note that this is determined by induction on its first argument.

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

The number of recursive calls depends only on length xs .

Because of this, in xs ++ ys it is more convenient to have small xs and large ys than vice versa.

Note that bending to the right achieves this:

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

We have only short (O (1) -line) to the left of ++ , which makes the cost of adding O (n).

Instead, folding left is bad:

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

Leftist arguments are getting bigger and bigger. Therefore, here we get the complexity O (n ^ 2).

This argument can be clarified considering how an output list is required. You may notice that foldr gives its result in a "streaming" way, requiring, for example, the first cell of the output list only forces a small part of the input - you only need to execute the first ++ , and in fact, only its first recursive step is needed! Instead, only the first element from the result of foldl , which will make all ++ calls make it quite expensive (even if each call needs only one recursive step, there are O (n) calls).