How does foldl work?

Question

Can anybody explain how foldl works?
I understood that, for example, foldr (-) 0 [1,2,3] produces (1 - (2 - (3 - 0))), whereas foldl (-) 0 [1,2,3] produces (((0 - 1) - 2) - 3), but I have still some questions:

• 1st example (length of a list with foldr/foldl):
  foldr (\_ acc -> acc + 1) 0 [1,2,3,4,5] produces 5, as expected.
  foldl (\_ acc -> acc + 1) 0 [1,2,3,4,5] produces 6. :|
  foldl (\_ acc -> acc + 1) 0 [2] produces 3. :|
  How does foldl react to these given examples?

• 2nd example:
  foldr (:) [] [1,2,3,4] produces [1,2,3,4] - no worry, but foldl (:) [] [1,2,3,4] gives me an error: Occurs check: cannot construct the infinite type: a ~ [a]
  What is wrong with foldl?

Answer 1

In foldr, the accumulator is the second argument of the function you're folding with, but in foldl, the accumulator is the first argument. If you look carefully at the question's introductory paragraph, you can work this out for yourself...

The "1st example" code is misleading because the acc argument (whose name suggests that it should be an accumulator) is consistently the second argument to the lambda, when it should be first for foldl. It is additionally confusing because the type and values of the sample list elements mirror the type and value of the accumulator value... as the comments mention, it would have been better to use other values, and better yet to use some other type!

For the "2nd example", you get a type error because your arguments are swapped (and you can't have a list whose elements are lists of itself). Either swap the argument order by hand:

foldl (\xs x -> x:xs)

or else use flip, the library function designed for this:

foldl (flip (:))

Note that the result for the foldl case should be a reversed list (not a copied one), because foldl iterates in the opposite direction from foldr.