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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s