Mindshift: Part 15

Implementing the REDUCE function

Now that we have an implementation of the MAP function, its just a small modification to create a REDUCE function.

In other programming languages the names FOLDL for "Fold Left" or FOLDR for "Fold Right" are used instead of REDUCE. The concept here is that if you treat the list as a long ribbon or piece of tape, and each item occupies some fixed width of the tape, then the REDUCE function can be thought of as folding the tape in a concertina-like fashion so that it ends up occupying the width of only a single item.

In this blog, we will implement the REDUCE function to be identical to FOLDL I.E. folding the list from the left.

So, what does REDUCE actually do?

The REDUCE function works on the same principle as the MAP function in that it passes each list item as a parameter to some transformation function. However, instead of creating a new list of modified items, REDUCE returns a single value that is the accumulated result across all the function calls. In other words, by means of some function, we are processing the items in the list in order to reduce them down to a single value.

When defining the function passed to MAP, we had to ensure that it took a single parameter and returned a single value as the result; however, the function passed to REDUCE must receive not only the value of the current list item, but must also accept a second parameter. This second parameter must be initialised to the starting value of the accumulator and ultimately becomes the REDUCE function's return value.

So let's use the same list as in the previous blog; one that holds the first four positive integers [1,2,3,4]

Building the REDUCE function

The REDUCE function itself needs to take three parameters:

  1. The list being reduced (or folded)
  2. The function to which each list item will be passed. (This function must take two parameters)
  3. The initial value of the accumulator

The REDUCE function then returns a single value leaving the original list unmodified.

The implementation of the REDUCE function is shown below.

Ok, let's perform one of the simplest tasks we can on a list. Let's count the number of items it contains...

It's worth just taking a bit of time to explain how incredibly simple the COUNT functionality actually is. Remember, we must pass three parameters to REDUCE:

  1. The list we want to process in some way
  2. The function that performs the required processing
  3. The starting value for the accumulator

The first and third parameters are easy enough, but take a look at the second parameter (dont_care => acc => SUCC(acc)).

This anonymous function must receive two parameters:

  1. The value of the current list item
  2. The accumulator

On each invocation, this function must return the new value of the accumulator.

However, in the case of counting the number of items in a list, we don't care in the slightest what the actual item value is; all we care about is that there is an item.

This is why the first parameter to our function is called dont_care - its value is of no consequence. What we do care about however is counting the number of times this function is called, because that corresponds exactly to the number of items in the list.

So the functionality of the COUNT function adds up to nothing more than incrementing the accumulator each time the function is called; hence, we repeatedly use the SUCCessor function to increment the accumulator's starting value of ZERO.

That Was Easy Enough Wasn't It?

Well, not so fast tiger... All we've done so far is write a simple counter function that operates only on the accumulator and completely ignores the list item value. This is hardly the standard use case for the REDUCE function.

So let's make things more realistic and write a function that calculates a result using both the list item value and the accumulator. A simple example here is the factorial calculation.

If you have a sequential, one-based sequence of positive integers, then the factorial calculation is implemented simply by reducing the list using the multiply operator.

So, initially, we could try something like this:

Here we multiply the current list item val by whatever value is currently held in acc. Ok, let's give this a try:

Uncaught TypeError: qtyFn1 is not a function

Bother - it's blown up!

Jake, You Get Wise!
You Get To Church!*

The problem here is that the MULTIPLY function is designed to receive only abstract quantity functions - and what type of data do we have in the array with which we're testing?

Normal JavaScript numbers - oops!

So in order to make this work, we must first convert the JavaScript numbers into abstract quantity functions. Here, instead of calling them abstract quantity functions, we'll use the more academic name of Church Numerals (named after the logician Alonzo Church).

The implementation is shown below:

All we're doing here is using the Y-Combinator to find the n'th successor of ZERO; where n is the integer being converted.

Now we need to adapt the function we pass to FACTORIAL to represent the item value using Church encoding:

We can add up the values of all the items in the list just as easily

That's better.

Improving The API

At the moment, our implementation has a bit of a usability problem.

REDUCE takes three parameters; the second one being the function that performs the reduction. However, our current implementation does not allow us simply to pass in the raw function such as MULTIPLY or ADD. Instead, we have to wrap these functions inside an inline function such as (val => acc => ADD(to_church(val))(acc).

So let's change the definition of REDUCE so that you don't need to care about such internal implementation details.

What this amounts to is moving the definition of the inline function to within the definition of REDUCE. Then the developer only need supply the raw materials upon which REDUCE acts. I.E. The list, a reduction function and the accumulator's start value.

We'll that's certainly easier to use. Let's try running it.

Uncaught TypeError: qtyFn1 is not a function

Uncaught TypeError: qtyFn1 is not a function

Rats! Its blowing up again with the same error we had before.

The problem is that we've omitted the step that performed the call to to_church. Consequently, we've gone back to passing JavaScript numbers to a function that expects Church numerals.

We can solve the problem by taking one of two different approaches here:

  1. We could alter the definition of the list object so that it is populated with Church numerals instead of JavaScript numbers
  2. We could modify the FACTORIAL and SUM functions to accept JavaScript numbers and perform the conversion internally

The first solution is possible, but does not yield a very interesting solution. However, modifying the FACTORIAL and SUM functions to perform the required conversion is a much more interesting approach.

Therefore, we need to convert every element in the list from a JavaScript number into a Church numeral. Luckily for us, we've just created a general-purpose way of doing exactly this - the MAP function. We also have a function that can convert a JavaScript number to a Church numeral - to_church.

So all we need to do is MAP the to_church function across the list at the time we start the REDUCE process. This way, we don't need to alter the object holding the data, and we supply both the MULTIPLY and ADD functions with exactly the data they require.

This serves as a good practical example of the simplicity and power of the MAP function. Just by wrapping our list in a single function call, we have found a simple solution for what would otherwise be a potentially awkward problem.

This Is Not Poker, But We Do Need To Fold

At the start of this blog, I mentioned that the REDUCE function is known in some languages as FOLD. However, the FOLD function is implemented such that you can process a list either from left-to-right, or right-to-left.

In the case of our REDUCE function above, we have implemented a FOLDL function because we always process the list items in a left-to-right order.

However, implementing a FOLDR (fold right) function is very simple. All we need to do is reverse the order of items in the list before performing our left-to-right REDUCE on it.

In the case of the FACTORIAL and SUM functions with which we have been testing, the order in which the list items are processed makes no difference to the result.

Chris W

All source code from the Mindshift blog series can be found on GitHub

* Just had to get a Blue's Brothers quote in there... :-)