**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!