# Mindshift: Part 15 Republished on Feb 20th, 2018 Previous Blog Next Blog 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 have behaviour identical to FOLDL I.E. folding the list from the left. So, What Does REDUCE Actually Do? The REDUCE function works on a principle very similar to the MAP function in that each list item is passed to some transformation function. However, instead of creating a new list of modified items, REDUCE returns a new value that represents some sort of accumulation of all the values in the list. This new value is always a single value, but its data type is not limited to being a primitive type such as an integer or a string; it could equally well be a new object or array or even a new list. In other words, by means of some function, all the items in the list are reduced down to some single, new value - where that single value could be an integer, a Boolean, an object or possibly even a new list. The function passed to REDUCE must receive two parameters. The first is the value of the current list item, and the second is the variable usaed to build up the accumulated result - hence this parameter is known as the "accumulator". When you call REDUCE, you must supply not only the function used to build up the accumulator, but also some appropriate starting value for the accumulator. After all the list items have been processed, whatever value is left in the accumulator becomes the REDUCE function's return value. 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 current list item and the current accumulator value) 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.
// The recursive function used by REDUCE make_reduc = next_reduc => list => fn => acc => (new_acc => // Have we reached the end of the list? lib.IS_LAST(list) // Yup, so simply return the accumulator (f => (new_acc)(f)) // Nope, so recursively call ourselves passing the // remainder of the list, the reduction function and the // new accumulator value (f => (next_reduc(lib.TAIL(list)) (fn) (new_acc)) (f) ) ) // Calculate the new accumulator value. This value // appears as parameter new_acc in the above function (fn(lib.HEAD(list))(acc))
// Create the REDUCE function using the Y-Combinator REDUCE = lib.Y(make_reduc)
Ok, let's perform one of the simplest tasks we can on a list. Let's count the number of items it contains...
// Define a function to count the number of items in a list COUNT = list => REDUCE(list) // The list being reduced (dont_care => acc => lib.SUCC(acc)) // The reduction function (lib.ZERO) // The accumulator start value
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 - in this situation, 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 coding in the COUNT function amounts 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. Let's use the same list as in the previous blog; one that holds the first four positive integers [1,2,3,4]
// Create a list holding the first four positive integers listOfInts = lib.array2list([1,2,3,4])
Counting the number of items in this list can now be done as follows
lib.to_integer(COUNT(listOfInts))
That Was Easy Enough Wasn't It? Well, not so fast tiger... All we've done here 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:
// Define a FACTORIAL function FACTORIAL1 = list => REDUCE(list) // The list being reduced (val => acc => lib.MULTIPLY(val)(acc)) // The reduction function (lib.ONE) // The starting value for the accumulator
Here we multiply the current list item val by whatever value is currently held in acc. Ok, let's give this a try:
lib.to_integer(FACTORIAL1(listOfInts))
Bother - it's blown up! Jake, You Get Wise! You Get To Church! ✱ The problem here is that the MULTIPLY function is designed to work only with abstract quantity functions - and what type of data do we have in listOfInts array? (The clue is in the name!) Normal JavaScript integers, not abstract quantity functions - oops! So in order to make this work, we must first convert each integer in the listOfInts array into an abstract quantity function. At this point, instead of calling them abstract quantity functions, we'll use the more academic name of Church Numerals (named after the logician Alonzo Church). The function to convert an integer to a Church numeral is shown below:
// Convert a positive integer to its Church encoding // Null must be explicitly tested for to avoid disappearing down the rabbit hole of infinite recursion. // This is because JavaScript coerces null to be zero; therefore, the "(n-1)" part of the expression // "next_qty_fn(lib.SUCC(qty_fn))(n-1)" will become 0-1 which then leads to infinite recursion. // This behaviour does however result in mapping null to ZERO, which might produce misleading results... do_qty_fn = next_qty_fn => qty_fn => n => (n === 0 || n === null) ? qty_fn : next_qty_fn(lib.SUCC(qty_fn))(n-1)
TO_CHURCH = lib.Y(do_qty_fn)(lib.ZERO)
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:
// Define a FACTORIAL function FACTORIAL = list => REDUCE(list) // The list being reduced (val => acc => lib.MULTIPLY(TO_CHURCH(val))(acc)) // The reduction function now using Church numerals (lib.ONE) // The accumulator start value
lib.to_integer(FACTORIAL(listOfInts))
We can also add up the values of all the items in the list just as easily
// Define a SUM function SUM = list => REDUCE(list) // The list being reduced (val => acc => lib.ADD(TO_CHURCH(val))(acc)) // The reduction function now using Church numerals (lib.ZERO) // The accumulator start value
lib.to_integer(SUM(listOfInts))
That's better. The only slightly complicating factor here is that we must remember to ensure the data type of each list element is compatible with the data type expected by the reduction function. If our list contains JavaScript integers, as is the case with listOfInts, then we must remember that these values cannot be passed directly to some function that acts on abstract quantity functions such as ADD or MULTIPLY; hence the need to write an intermediate call to the TO_CHURCH function. 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 (fold left) 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.
// Fold left is simply a synonym for REDUCE FOLDL = REDUCE
// Fold right is simply a fold left on the reversed list FOLDR = list => REDUCE(lib.REVERSE(list))
In the particular cases of the FACTORIAL and SUM functions, the order in which the list items are processed makes no difference to the result. And finally... MAP is Actually Just a Special Case of REDUCE Strictly speaking, the MAP function is unnecessary because wherever it is used, we could potentially use REDUCE instead. However, MAP is a useful convenience function because it guarantees that the number and order of elements in the new list will be exactly the same as in the original list. This guarantee can be summarised in the following psuedocode: [n, n+1, n+2, ...].map(fn) -> [fn(n), fn(n+1), fn(n+2), ...] The REDUCE function can be used in the same way, but it will always be without this guaruntee. Chris W ✱ I just couldn't resist sneaking in a reference to the Blues Brothers :-)
lib = { // ******************************************************************** // Naming Conventions // // Functions with all uppercase names return abstract functions // // Functions with all lowercase names return native JavaScript data // types // ******************************************************************** // ******************************************************************** // Generic operations // ******************************************************************** var adder = val1 => val2 => val1 + val2; var multiplier = p => q => q*p; var str_concatenate = char => acc => acc.concat(char); var asPlusChar = str_concatenate('+'); // The increment and decrement functions can now be created var incr = adder(1); var decr = adder(-1); // Use the multiplier function to create partial functions that // double, triple and quadruple their subsequent operand var double = multiplier(2); // -> double = q => q*p (p = 2) var triple = multiplier(3); // -> triple = q => q*p (p = 3) var quadruple = multiplier(4); // -> quadruple = q => q*p (p = 4) var add5 = adder(5); // -> add5 = q => q+5 // ******************************************************************** // Function Composition // ******************************************************************** var compose = fn1 => fn2 => val => fn2(fn1(val)); // Now we can "compose" double and add5 into a single function var doubleAndAdd5 = compose(double)(add5); // ******************************************************************** // Reification functions // ******************************************************************** var to_integer = qtyFn => qtyFn(incr)(0); var to_string = qtyFn => qtyFn(asPlusChar)(''); var to_boolean = fn => fn(true)(false); // ******************************************************************** // Functions that operate on pairs and return abstract functions // ******************************************************************** var TRUE = true_part => false_part => true_part; var FALSE = true_part => false_part => false_part; // HEAD and TAIL are synonyms for TRUE and FALSE var HEAD = pair => pair(TRUE); var TAIL = pair => pair(FALSE); var PAIR = val1 => val2 => fn => fn(val1)(val2); var EMPTY_LIST = PAIR(null)(null); var IS_EMPTY = pair => (HEAD(pair) === null && TAIL(pair) === null) ? TRUE : FALSE var IS_LAST = pair => IS_EMPTY(TAIL(pair)) // ******************************************************************** // Functions that operate on pairs and return JavaScript data types // ******************************************************************** var is_empty = pair => (HEAD(pair) === null) && (TAIL(pair) === null); var is_last = pair => is_empty(TAIL(pair)); // ******************************************************************** // Define an abstract quantity function for ZERO. // ******************************************************************** var ZERO = transform => start_value => start_value; // ******************************************************************** // Successor and predecessor functions // ******************************************************************** var SUCC = qtyFn => transform => start_value => transform(qtyFn(transform)(start_value)); var SUCC_PAIR = pair => PAIR(pair(FALSE))(SUCC(pair(FALSE))); var PRED = qtyFn => qtyFn(SUCC_PAIR)(PAIR(ZERO)(ZERO))(TRUE); // ******************************************************************** // Now each quantity function can be defined simply as the successor // of the quantity function before it. // ******************************************************************** var ONE = SUCC(ZERO); var TWO = SUCC(ONE); var THREE = SUCC(TWO); var FOUR = SUCC(THREE); var FIVE = SUCC(FOUR); var SIX = SUCC(FIVE); var SEVEN = SUCC(SIX); var EIGHT = SUCC(SEVEN); var NINE = SUCC(EIGHT); var TEN = SUCC(NINE); var ELEVEN = SUCC(TEN); var TWELVE = SUCC(ELEVEN); // ******************************************************************** // Arithmetic operations based on abstract quantity functions // ******************************************************************** var ADD = qtyFn1 => qtyFn2 => qtyFn1(SUCC)(qtyFn2); var MULTIPLY = qtyFn1 => qtyFn2 => qtyFn1(ADD(qtyFn2))(ZERO); var POWER = qtyFn1 => qtyFn2 => qtyFn2(MULTIPLY(qtyFn1))(ONE); var SUBTRACT = qtyFn1 => qtyFn2 => qtyFn2(PRED)(qtyFn1); // ******************************************************************** // Boolean Operators // ******************************************************************** var NOT = bool => bool(FALSE)(TRUE); var AND = bool1 => bool2 => bool1(bool2)(FALSE); var OR = bool1 => bool2 => bool1(TRUE)(bool2); var XOR = bool1 => bool2 => bool1(NOT(bool2))(bool2); // ******************************************************************** // Predicate functions // ******************************************************************** var IS_ZERO = qtyFn => qtyFn(dont_care => FALSE)(TRUE); var IS_LTE = val1 => val2 => IS_ZERO(SUBTRACT(val1)(val2)); var IS_LT = val1 => val2 => NOT(IS_LTE(val2)(val1)); // ******************************************************************** // Combinators // ******************************************************************** var U = fn => fn(fn); var Y = (rec_fn => (gen_rec => U(gen_rec)) (gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b))) ) // ******************************************************************** // Create our own push function that returns the new array rather than // the index of the newly inserted item // ******************************************************************** var push = arr => val => (idx => arr)(arr.push(val)); // ******************************************************************** // Convert a character string to a list whilst preserving the // character order // ******************************************************************** var make_str2list = fn_next=> list => str => (str.length > 0) ? fn_next(PAIR(str.substr(-1))(list))(str.slice(0,-1)) : list; var str2list = str => Y(make_str2list)(EMPTY_LIST)(str); // ******************************************************************** // Convert a list back into a character string // ******************************************************************** var make_list2str = fn_next=> str => list => is_last(list) ? str.concat(HEAD(list)) : fn_next(str.concat(HEAD(list)))(TAIL(list)); var list2str = list => Y(make_list2str)("")(list); // ******************************************************************** // Convert a JavaScript array into a list // ******************************************************************** var make_array2list = fn_next=> list => array => (array.length === 0) ? list : fn_next(PAIR(array[array.length-1])(list)) (array.slice(0,-1)); var array2list = Y(make_array2list)(EMPTY_LIST); // ******************************************************************** // Convert a list to a JavaScript array // ******************************************************************** var make_list2array = fn_next=> arr => list => is_last(list) ? push(arr)(HEAD(list)) : fn_next(push(arr)(HEAD(list)))(TAIL(list)); var list2array = list => Y(make_list2array)([])(list); // ******************************************************************** // Reverse a list // ******************************************************************** var do_reverse = next_rev => new_list => old_list => IS_LAST(old_list) (PAIR(HEAD(old_list))(new_list)) (f => (next_rev(PAIR(HEAD(old_list))(new_list)) (TAIL(old_list))) (f)) var REVERSE = Y(do_reverse)(EMPTY_LIST) // ******************************************************************** // Generic MAP function // ******************************************************************** var make_map = next_map => new_list => fn => list => (list_acc => // Have we reached the end of the list? IS_LAST(list) // Yup, so reverse the items in the list and // we're done (f => REVERSE(list_acc)(f)) // Nope, so recursively call ourselves passing // in the list accumulator, the function being // applied and whatever is left in the current // list (f => (next_map(list_acc) (fn) (TAIL(list))) (f)) ) // Apply the mapping function to the first list item and // append the result to the start of the new list. This // value is then received as argument list_acc in the // function above (PAIR(fn(HEAD(list)))(new_list)) var MAP = Y(make_map)(EMPTY_LIST) return { adder : adder , multiplier : multiplier , str_concatenate: str_concatenate , asPlusChar : str_concatenate('+') , incr : adder(1) , decr : adder(-1) , push : push , to_integer : to_integer , to_string : to_string , to_boolean : to_boolean , is_empty : is_empty , is_last : is_last , str2list : str2list , list2str : list2str , array2list : array2list , list2array : list2array , PAIR : PAIR , TRUE : TRUE , FALSE : FALSE , HEAD : HEAD , TAIL : TAIL , EMPTY_LIST : EMPTY_LIST , IS_EMPTY : IS_EMPTY , IS_LAST : IS_LAST , SUCC : SUCC , SUCC_PAIR : SUCC_PAIR , PRED : PRED , ZERO : ZERO , ONE : ONE , TWO : TWO , THREE : THREE , FOUR : FOUR , FIVE : FIVE , SIX : SIX , SEVEN : SEVEN , EIGHT : EIGHT , NINE : NINE , TEN : TEN , ELEVEN : ELEVEN , TWELVE : TWELVE , ADD : ADD , MULTIPLY : MULTIPLY , POWER : POWER , SUBTRACT : SUBTRACT , NOT : NOT , AND : AND , OR : OR , XOR : XOR , IS_ZERO : IS_ZERO , IS_LTE : IS_LTE , IS_LT : IS_LT , Y : Y , REVERSE : REVERSE , MAP : MAP } }