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

why foldl slower foldr ? have list of lists "a" like

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

and want change list using fold

foldr (++) [] 

it works fine (time complexity o(n)). if use foldl instead, slow (time complexity o(n^2)).

foldl (++) [] 

if foldl folding input list left side,

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

and foldr right side,

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

the number of computations (++) supposed same in both cases. why foldr slow? per time complexity, foldl looks if scanning input list twice many times foldr. used following computer time

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

it's because of how ++ works. note is defined induction on first argument.

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

the number of recursive calls depends on length xs.

because of this, in xs ++ ys more convenient have small xs , large ys other way around.

note folding on right achieves this:

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

we have short (o(1)-length) lists on left of ++, making fold cost o(n).

instead folding on left bad:

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

the left arguments become larger , larger. hence, o(n^2) complexity here.

this argument can made more precise considering how output list demanded. 1 can observe foldr produces result in "streaming" fashion, demanding e.g. first output list cell forces little part of input -- first ++ needs performed, , first recursive step needed! instead demanding first item foldl result force all ++ calls, making quite expensive (even if each call needs 1 recursive step, there o(n) calls).