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

- The list being reduced (or folded)
- The function to which each list item will be passed. (This function must take two parameters)
- 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`

:

- The list we want to process in some way
- The function that performs the required processing
- 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:

- The value of the current list item
- 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 `SUCC`

essor 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:

- We could alter the definition of the
`list`

object so that it is populated with Church numerals instead of JavaScript numbers - 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... :-)