foldl and foldr

First, we start with the definitions:
foldr:

foldr f z (x:xs) = f x (foldr f z xs) (*)
foldr _ z []     = z                 (**)

foldl:

foldl f z (x:xs) = foldl f (f z x) xs (*)
foldl _ z []     = z                 (**)

foldr starts from the right and goes on to the left (right-associative), while foldl does exactly the opposite.
As usual, it’s best to see with examples. Assume generic list of [a, b, c] and generic function f:

Case foldr:

foldr f z (x:xs) = f x (foldr f z xs)
  => foldr f z [a, b, c]
  = f a (foldr f z [b, c])         (by (*))
  = f a (f b (foldr f z [c])       (by (*))
  = f a (f b (f c (foldr f z []))) (by (*) and (**))
  = f a (f b (f c z))

Case foldl:

foldl f z (x:xs) = foldl f (f z x) xs
  => foldl f z [a, b, c]           (by (*))
  = foldl f (f z a) [b, c]         (by (*))
  = foldl f (f (f z a) b) [c]      (by (*))
  = foldl f (f (f (f z a) b) c) [] (by (*) and (**))
  = (f (f (f z a) b) c)

So we’ve shown the associativity of both foldr and foldl.
Why do we need both foldr and foldl? Because of associativity of course. There are some cases where we’d want to use foldr, and some cases where we’d want to use foldl.
Consider some f (binary function) which is not associative (e.g. ‘-‘). Try evaluating:

*Main> foldr (-) 0 [1,2,3]
2
*Main> foldl (-) 0 [1,2,3]
-6

So, what really inspired me to write this article is one of the examples given in LYAH:

solveRPN x = foldl foldingFunction [] $ words x
    where   foldingFunction (x:y:ys) "*" = (x * y):ys
            foldingFunction (x:y:ys) "+" = (x + y):ys
            foldingFunction (x:y:ys) "-" = (y - x):ys
            foldingFunction xs numberString = read numberString:xs

This is a very elegant solution. I tried writing a RPN calculator some time ago in JS (imperative style) and it involved a lot of checks for side cases, while in Haskell where we have the definitions of all functions that we are using, there is no room for side cases. We know exactly what we are trying to evaluate.

If you want a thorough explanation of the solveRPN function, you can check it at http://learnyouahaskell.com/functionally-solving-problems, while here I’ll only give a brief explanation.

Our foldingFunction acts as a stack storage, and accepts two parameters (the first parameter being the initial parameter that we pass (an empty stack), and the second one being the current element taken from the list), as foldl expects. So, in the where clause we are actually pattern matching on foldingFunction .

In the case where we have two (or more) numbers stored into our stack (x:y:ys) and we arrive at “*” as the current element of the input list, then we multiply those two numbers and store the result back in the stack. Likewise is the definition for “+” and “-“. However, if we match none of the specified operators, then we just store it back into our stack as a number.