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.

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;
}

function tail(\$xs) {
return \$xs;
}
``````

### 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…

## Jobs at MyBuilder

We need an experienced software engineer who loves their craft and wants to share their hard-earned knowledge.

View vacancies