Mindshift: Part 14 / Chris Whealy / Observable

Mindshift: Part 14 Republished on Feb 20th, 2018 Previous Blog Next Blog Functional Cartography:The MAP Function Ok, so what point have we now reached? We're at the point now where we can construct a singly linked list into which we can add items. We can retrieve the first item from the list using a HEAD function and access the remainder of the list using a TAIL function. We can also determine whether we've reached the end of the list using the is_last function. Next, we implemented functionality that converts this abstract list into the native JavaScript datatypes of String and Array. When you're lost, use a MAP Now that we can access all the items of a list in sequential order, we have the foundation upon which to build a mechanism for applying a function to each item in that list. In other words, we want to work our way sequentially down the list, passing each item to some function. The result of this process is the creation of a new list in which every item has been modified by that function. This implies two things about the new list: It contains the same number of items as are in the old list The modified items in the new list appear in the same order as the items from which they have been derived in the old list. The process by which a function is applied to every item in a list is known as mapping, and is one of the most fundamental tools in the functional programmer's toolbox. Aside Remember that in functional programming we are far less concerned with what a function does, and much more concerned with how a function is used. I mention this to pre-empt a question that often arises here. When we say we want to apply a function to every item in a list, programmers from an imperative background will usually understand the situation by focussing on what the function does. This is a perfectly natural question for someone with an imperative mindset because they are strongly focussed on defining the exact sequence of instructions a computer should perform. However, within certain broad parameters, functional programming doesn't actually care what a function does. All we really care about how is a function should be applied - I.E. in this case, understanding the function's interface is more important than knowing what the function does. In the case of mapping a function across the items in a list, all we are concerned about is ensuring that the function to be applied takes a single parameter and returns a single value. So let's say we have a list that holds the first four positive integers [1,2,3,4] If we want to double each item in this list, then the first thing we need to do (after creating the list itself) is to create a function capable of performing the required task:// Create a list holding the first four positive integers listOfInts = lib.array2list([1,2,3,4])// Generic multiplier function multiplier = val1 => val2 => val1 * val2// Partial function to double a number doubler = multiplier(2)Building the MAP function The MAP function needs to take two parameters: firstly, the function to be applied to each item in the list, and secondly, the list to be processed. It then returns a new list. It is important to understand that the map function does not modify the original list. The new list is generated by successively applying the following steps to each item in the list: Take the current list item and pass it to the function as a parameter Store the value returned by the function as a new item in the return list Recursively repeat steps one and two using the following three values as parameters: The TAIL of the old list The function being applied The return list If you've been following the blog series up to this point, you'll know that in order to repeat the same action an unknown number of times, we must use recursion (I.E. The Y-Combinator). Further to this, in order to successfully implement any recursive process, we need some way to detect when the recursion should finish - otherwise we'll disappear down the rabbit hole of infinite recursion. So we'll need both an IS_EMPTY and an IS_LAST function that can detect whether the current item in the list is the last one. You may remember that we already have the functions is_empty and is_last, but these functions operate on JavaScript datatypes. Here however, we need equivalent functions that operate on our abstract quantity functions — hence the uppercase function names.IS_EMPTY = pair => (lib.HEAD(pair) === null && lib.TAIL(pair) === null) ? lib.TRUE : lib.FALSEIS_LAST = pair => IS_EMPTY(lib.TAIL(pair))The implementation of the MAP function is shown below. I trust that if you've read the previous blogs in this series, then the comments should be all you need to understand its structure.// First attempt at the recursive function used by MAP make_map1 = next_map => new_list => fn => list => (list_acc => // Have we reached the end of the list? IS_LAST(list) // Yup, so we're done (list_acc) // 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) (lib.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 (lib.PAIR(fn(lib.HEAD(list)))(new_list))// Create the MAP function using the Y-Combinator and an initial empty list MAP1 = lib.Y(make_map1)(lib.EMPTY_LIST)Ok, let's see how we get on with this...doubled_list1 = MAP1(doubler)(listOfInts)lib.list2array(doubled_list1)Hmmmm... We've got a problem here. We have the right numbers in the list, but the order is backwards. Reversing out of a problem Thinking about the way our MAP function builds up its results in the list_accumulator variable; we can see that it would be more accurate to call this data structure a stack or a LIFO list. Each time we pass the HEAD of the old list to our doubler function, the result is pushed into the list_accumulator, and this inadvertently results in the order of items becoming reversed. This is actually a common problem in list handling; very often, tasks performed on a list cause the item order to be reversed. However, rather than altering the way the current MAP function works, the simplest solution is to write a function that reverses the order of items in a list, and then pass the list_accumulator to this function as the return value from MAP. A REVERSE function is implemented as follows:do_reverse = next_rev => new_list => old_list => IS_LAST(old_list) (lib.PAIR(lib.HEAD(old_list))(new_list)) (f => (next_rev(lib.PAIR(lib.HEAD(old_list))(new_list)) (lib.TAIL(old_list))) (f))REVERSE = lib.Y(do_reverse)(lib.EMPTY_LIST)All we need to do now is make a small change to the make_map function. Notice however, that the call to REVERSE has been wrapped in a function that takes a dummy parameter. This ensures that the execution of REVERSE is delayed until IS_LAST evaluates to TRUE.// Second attempt at the recursive function used by MAP make_map2 = 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) (lib.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 (lib.PAIR(fn(lib.HEAD(list)))(new_list))// Create the MAP function using the Y-Combinator and an initial empty list // This version of MAP now returns the items in the correct order! MAP = lib.Y(make_map2)(lib.EMPTY_LIST)Ok, let's try this again...doubled_list2 = MAP(doubler)(listOfInts)// We're expecting the list to contain [2,4,6,8]... lib.list2array(doubled_list2)That's better! The Generic Power of the MAP function Together with the REDUCE function, the MAP function is arguably the most widely used tool in functional programming - to the point that many people perceive functional programming to be nothing more than using MAP and REDUCE on their dataset. To quote President George Bush, they have greatly overmisunderestimated the situation; that said, this perception does illustrate the central position occupied by these two functional concepts. So let's create a variety of functions that can all be used by the MAP function. Remember that the most basic requirement here is that whatever function is passed to MAP must take a single parameter as input, and produce a single value as output. Beyond that, the MAP function doesn't care what your function actually does.{ // Create a list hold 4 numbers var listOfInts = lib.array2list([1,2,3,4]); // Generic multiplier function var multiplier = val1 => val2 => val1 * val2; // Functions to perform variety of numerical operations var doubler = multiplier(2); var tripler = multiplier(3); var squarer = val => multiplier(val)(val); var sqrter = val => Math.sqrt(val); return { double : lib.list2array(MAP(doubler)(listOfInts)) , triple : lib.list2array(MAP(tripler)(listOfInts)) , squared : lib.list2array(MAP(squarer)(listOfInts)) , sqrt : lib.list2array(MAP(sqrter)(listOfInts)) } }In the next blog, we'll look at how the REDUCE function can be implemented. Chris Wlib = { // ******************************************************************** // 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); // ******************************************************************** // 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); 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, 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 } }