fold - Haskell - foldl and foldr?

Question

Is difference between foldl and foldr just the direction of looping? I thought there was a difference in what they did, not just in the direction?

Answer 1

There's a difference if your function isn't associative (i.e. it matters which way you bracket expressions) so for example,
foldr (-) 0 [1..10] = -5 but foldl (-) 0 [1..10] = -55.
This is because the former is equal to 1-(2-(3-(4-(5-(6-(7-(8-(9-(10 - 0))))))))), whereas the latter is (((((((((0-1)-2)-3)-4)-5)-6)-7)-8)-9)-10.

Whereas because (+) is associative (doesn't matter what order you add subexpressions),
foldr (+) 0 [1..10] = 55 and foldl (+) 0 [1..10] = 55. (++) is another associative operation because xs ++ (ys ++ zs) gives the same answer as (xs ++ ys) ++ zs (although the first one is faster - don't use foldl (++)).

Some functions only work one way:
foldr (:) :: [a] -> [a] -> [a] but foldl (:) is nonsense.

Have a look at Cale Gibbard's diagrams (from the wikipedia article); you can see f getting called with genuinely different pairs of data:

Another difference is that because it matches the structure of the list, foldr is often more efficient for lazy evaluation, so can be used with an infinite list as long as f is non-strict in its second argument (like (:) or (++)). foldl is only rarely the better choice. If you're using foldl it's usually worth using foldl' because it's strict and stops you building up a long list of intermediate results. (More on this topic in the answers to this question.)