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…