# foldl and foldr

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`

`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`