Understanding reduce / fold

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 cons cell.

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 add (or 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!