Cons Lists and Folds in PHP
Cons cells are used to (cons)truct a data object which represents an ordered pair. The elements in this pair can be identified as ‘car’ and ‘cdr’ accordingly. Using this simple representation we are able to not only hold ordered pairs, but also create more complex data-structures, such as a List. Below is an example interface that we will be using to implement the two different kinds of Cons cell required to create this List data-structure.
As you can see we have also included a couple of other useful methods that will be used to traverse the list. Providing a defined closure which will be invoked on each element returning either a predicate or new value.
The first such type of cell that is used to represent this structure is the empty list. Commonly called Nil, it is treated as a sentinel node, distinguishing the end of the list and used as a recursive base-case.
The other type of cell that is required stores the first element in its left-hand value (‘car’) and the next Cons cell in its right (‘cdr’). In this implementation we use alternative, more meaningful names for the ‘car’ and ‘cdr’ values. Following the head and tail naming convention instead.
As you can see, the Cons implementation does the majority of the work in-regards to the methods we use to traverse the list. After supplying how each of the different folds are to be implemented, we are able to use these to create the map and filter methods. A fold is used to analyse a recursive data-structure and create a returning value from this completed process. The ‘foldr’ method is used to do the more common action of iterating over each element in the list (in order) from left to right. The ‘foldl’ method on the other hand can be considered the opposite, going right to left instead. These methods can be typically achieved using ‘array_reduce’ in PHP, with ‘array_reverse’ invoked first in the case of ‘foldl’.
We are able to use the ‘foldl’ method to easily add a ‘reverse’ method to our List implementation, as shown below.
We can also implement a ‘toArray’ method which converts the List representation into an PHP array - which makes it easier to reason about the resulting output.
Lets first try out a combination of a couple of the List methods, invoked via chaining.
In the example above we are creating a Cons list which represents the numbers from 1 to 10. We then subsequently filter out any elements that are not even, apply some pretty printing to each of the resulting elements and then reverse this output. Finally, we convert the Cons representation into an array to be easily output.
The example above tallies up the total number of Fibonacci numbers there are between 1 and 100. Using the ‘filter’ method with a supplied predicate function and the ‘foldr’ reduce method, we are correctly returned the total of 10.