Posted by **Sten Hiedel** on Mar 16, 2015

# Folds, and insight into the power of simplicity

The functional paradigm has some simple, yet powerful ideas that have changed the way I think about some programming problems, folds has been one of them. Understanding how they provide such versatile functions based on the operations applied, when folding over a given recursive data structure made a great impression on me.

## What is a fold?

Fold is a higher-order function also known as reduce that breaks apart a recursive data structure (typically a list of elements) and processes the structure in a systematic manner to produce a return value.

### Linked list

Implementing a simple linked list in php that conforms to the following pseudo-type `List a = [] | a : List a`

; where `a`

is the given type of element `Int`

, `String`

, `Bool`

etc, `|`

means or, and `:`

means constructing an object that holds two values.

A list of numbers `1 : (2 : (3 : []))`

visualised would look as follows

```
:
/ \
1 :
/ \
2 :
/ \
3 []
```

This diagram shows very clearly that a cons `:`

has two sides left and right, left side points to the element `a`

and right side points to another list `List a`

that is terminated with and empty list `[]`

In most languages there is syntatic sugar that allows creating lists without the parentheses most likely you have seen lists been constructer like this `(1, 2, 3)`

so essentially cons `:`

is a function that takes two arguments `:(x, xs)`

that is the same as `x : xs`

.

Because in PHP we cannot create a infix operator nor use `:`

as function name we’ll create a function `cons`

that returns an array with two elements `[x, xs]`

, and for representing an empty list we use empty array `[]`

, so creating list in php would look like this `cons(1, cons(2, cons(3, [])))`

Notice!For the purpose of making folds easy to understand I’m ignoring all sorts of error checking, stack overflow etc.

```
function cons($x, $xs) {
return [$x, $xs];
}
```

Before we can implement the folds we need two functions that allow extracting the left (element side) that we call `head`

and right (pointer to another list) that we call `tail`

.

```
function head($xs) {
return $xs[0];
}
function tail($xs) {
return $xs[1];
}
```

### Implementing a left fold (foldl)

Left fold can be viewed as a imperitive loop where we pass every element to a function that takes an accumulator and the element, and returns the accumulator.

```
function foldl($f, $initial, $xs) {
for ($r = $initial; false == empty($xs); $xs = tail($xs)) {
$r = $f($r, head($xs));
}
return $r;
}
```

Visualising the `foldl`

execution

```
$list = cons(1, cons(2, cons(3, [])));
foldl($f, $z, $list)
```

```
: ----> f
/ \ / \
1 : f 3
/ \ / \
2 : f 2
/ \ / \
3 [] z 1
```

#### foldl: Product of a list

To calculate a list product we need to pass in a `multiply`

function, and the accumulator initial value of 1.

```
function product($xs) {
$multiply = function ($a, $b) {
return $a * $b;
};
return foldl($multiply, 1, $xs);
}
```

```
: ----> *
/ \ / \
1 : * 3
/ \ / \
2 : * 2
/ \ / \
3 [] 1 1
```

#### foldl: Reversing a list

To reverse a list all we need to do is pass in a function that `cons`

every element with the accumulated list starting from an empty list

```
function reverse($xs) {
$f = function ($acc, $x) {
return cons($x, $acc);
};
return foldl($f, [], $xs);
}
```

```
: ----> :
/ \ / \
1 : : 3
/ \ / \
2 : : 2
/ \ / \
3 [] [] 1
```

#### foldl: The length of a list

To calculate the length of a list we need a function that increments a value by 1 e.g. `increment(1) == 2`

and the accumulator initial value of `0`

so we are ignoring the element altogether.

```
function length($xs) {
$increment = function ($n) {
return $n + 1;
};
return foldl($increment, 0, $xs);
}
```

Handy that php just ignores the extra argument to the

`increment`

function :P

```
: ----> +1
/ \ / \
1 : +1 _
/ \ / \
2 : +1 _
/ \ / \
3 [] 0 _
```

### Implementing right fold (foldr)

`foldr`

is a recursive function that executes the list from the right to the left. The `foldr`

takes 3 arguments: a function, an initial value and a list.

Same as the `foldl`

but they are very different in nature. When with `foldl`

you could think about it as a simple loop then this would be incorrent with `foldr`

. Right folding is a constructor replacement so every occurance of a `cons`

is replaced with a given function and the empty list `[]`

is replaced with given initial value.

Its easier to understand if we use a infix function for this example, and lets use add function `+`

and an intial value of `0`

.

When replacing every cons function `:`

with `+`

and the empty list `[]`

with `0`

we will get the sum of an list:

```
1 : (2 : (3 : []))
1 + (2 + (3 + 0 ))
```

The same example in PHP would looks more like this:

```
cons(1, cons(2, cons(3, [])))
$f(1, $f(2, $f(3, $z)))
```

#### foldr: The implementation in PHP

```
: ----> f
/ \ / \
1 : 1 f
/ \ / \
2 : 2 f
/ \ / \
3 [] 3 z
```

```
function foldr($f, $z, $xs) {
if (empty($xs)) {
return $z;
}
return $f(head($xs), foldr($f, $z, tail($xs)));
}
```

Notice that the passed in function

`$f`

signature is different from the one passed into`foldl`

function where the accumulator is the first argument. Here the function follows the same function signature as`cons`

, and therefor the element goes first. When you compare the`foldl`

and`foldr`

diagrams you will notice that`foldl`

accumulator is on the left side of the tree, and`foldr`

accumulator remains on the right side.

As the diagram is hinting `foldr("cons", [], $list) == $list`

is a lists identity function (or a shallow copy).

#### foldr: The sum of a list

Implementing the above example

```
function sum($xs) {
$add = function ($a, $b) {
return $a + $b;
};
return foldr($add, 0, $xs);
}
```

```
$list = cons(1, cons(2, cons(3, [])));
sum($list) == 6
```

```
: ----> +
/ \ / \
1 : 1 +
/ \ / \
2 : 2 +
/ \ / \
3 [] 3 0
```

#### foldr: Mapping a function over a list

Applies a given function to each element in a list, and returning a list of results.

We apply to the `cons`

first argument the given mapping function and then `cons`

the returned value to the list. The initial value stays the empty list `[]`

To visualise it `1 : (2 : (3 : []))`

becomes `f 1 : (f 2 : (f 3 : []))`

```
function map($f, $xs) {
$g = function ($a, $xs) use ($f) {
return cons($f($a), $xs);
};
return foldr($g, [], $xs);
}
```

```
$list = cons(1, cons(2, cons(3, [])));
$f = function ($n) {
return $n + 1;
};
map($f, $list) == cons(2, cons(3, cons(4, [])));
```

#### foldr: Filtering a list

We pass in a predicate that and only `cons`

the element to the list if the predicate function returns `true`

.

```
function filter($predicate, $xs) {
$g = function ($x, $xs) use ($predicate) {
return $predicate($x) ? cons($x, $xs) : $xs;
};
return foldr($g, [], $xs);
}
```

```
$list = cons(1, cons(2, cons(3, [])));
$odd = function ($x) {
return $x & 1;
};
filter($odd, $list) == cons(1, cons(3, []));
```

#### foldr: Append one list to another

Couldn’t be easier replace the empty list `[]`

with the second list. The `cons`

function remains unchanged.

To visualise it

```
1 : (2 : (3 : []))
4 : (5 : (6 : []))
1 : (2 : (3 : (4 : (5 : (6 : [])))))
```

```
function append($list1, $list2) {
return foldr("cons", $list2, $list1);
}
```

#### foldr: Concatenating list of lists

For readability I’m going to leave out inner list parentheses and use the append in infix position :)

```
1:2:3:[] : (4:5:6:[] : (7:8:9:[] : []))
```

For illustration lets do it by hand

```
1:2:3:[] `append` (4:5:6:[] `append` (7:8:9:[] `append` []))
1:2:3:[] `append` (4:5:6:[] `append` 7:8:9:[])
1:2:3:[] `append` 4:5:6:7:8:9:[]
1:2:3:4:5:6:7:8:9:[]
```

So only thing we need to replace is the `cons`

function with `append`

and Bob’s your builder :p

```
function concat($xs) {
return foldr("append", [], $xs);
}
```

There’s no denying that it has been challenging to learn how to think in the functionl paradigm. But I have really enjoyed learning languages such as Haskell and Clojure, they have shown me new ways to think about problems. Functional languages by desgin remove a lot of the boilerplate and accidental complexity we see in most OOP languages. This in turn makes it easier to work with complex problems, and sometimes actually rather enjoyable :p

This is just an appetiser for more, much more functional goodness…