12 Jun 2015
Disclaimer: There are some differences in the definition of fold and reduce in different languages - I won’t explore them here. Neither is the right / left variations of fold or reduce explained here.
Fold or reduce, from now on I will only use fold, is one of those functions which can be a bit hard to grasp when you’re new to functional programming but once you get it, it feels very natural and you end up using it all the time. A little while back I listened to a discussion about how to explain fold to novice programmers. Usually you end up drawing each iteration on a whiteboard and try to explain how the accumulator changes in each step.
But yesterday I was reading the paper Why functional programming matters and found that it explained fold in a way which I’d never seen before - perhaps that’s just me but it goes something like this:
Suppose you want to use fold on a list. First we must acknowledge that a list simply consists of many cons cells. In Scala, we can create the
cons cells used in lists with the function
::. The function will take a value on the left hand side of the operator and another
cons cell or the “empty”
Nil value on the right hand side, and return a new
This is how it looks like:
// Nil is equal to the empty list. Nil == List() // A cons cell consisting of 1 and Nil equals a // list with one element which has the value 1. 1 :: Nil == List(1) // A list consisting of any number of elements can // be created by combining multiple cons cells. 1 :: (2 :: (3 :: Nil)) == 1 :: 2 :: 3 :: Nil == List(1, 2, 3)
Now we want explain fold by creating the function
sum which sums up the elements of a list. In Scala, we can do it like this:
// Add is a function that takes two integers, a and b // and returns the resulting a + b. val add = (a: Int, b: Int) => a + b // Sum is a function which takes a list of integers // and returns the sum of all the integers using fold. val sum = (l: List[Int]) => l.fold(0)(add) // This is how it we can use it. sum(List(1, 2, 3)) == 1 + 2 + 3 == 6
What the paper did, which I found interesting, is how it explains how the
fold works. As seen in the example above,
fold takes two arguments, an accumulator:
0, and a function:
add. By using
fold on a list, we essentially replace the function
::, which represents the
cons cells, with our specified function
a + b), and the accumulator
0 replaces the Nil value.
Or explained in code:
sum(List(1, 2, 3)) == sum(1 :: (2 :: (3 :: Nil))) == 1 + (2 + (3 + 0))
A neat way to explain fold or reduce if you ask me. The paper continues and applies this concept to a tree, but you have to read that yourself if you want to know more - I highly recommend it!