Mindshift: Part 13 Republished on Feb 16th, 2018 Previous Blog Next Blog Using Functions to Create a Simple List We have now covered two keys areas in functional programming: The ability to use a PAIR function to form a pair of values The ability to call a function recursively We can now use these tools to construct and process simple linked lists. The type of list we will create here is a known as a *"singly"* or *"one-way"* linked list. This type of list is one that can only support forward traversal through its items. I.E. once you have moved from item one to item two in the list, you lose the ability to traverse back to any previous item. However, for all its limitations, we can use this construct to implement more familiar data structures such as character strings and arrays. In order to perform this implementation however, we must adopt some simple conventions. Each item in the list will be composed of a pair of values The first element of any given pair will hold that list item's value The second element of any given pair will hold another pair that represents the rest of the list We will arbitrarily create a list terminator identified by the fact that both items in the pair are set to JavaScript null This results in our list actually being implemented as a tree in which the left branch only ever holds a leaf node containing the data value, and the right branch holds either the remainder of the list, or the list terminator. So knowing that all items in a list are just pairs of values, we can access each item using only two functions. The names of these accessor functions vary from language to language, but here we will use the names HEAD and TAIL. Some alternative names for the first item of a pair are FIRST, LEFT or CAR, and for the second item of the pair, SECOND, REST, RIGHT or CDR. ASIDE One thing that I find irritating about the way lists in functional programming languages are *"explained"* is that the LISP function names CAR and CDR are often used with the assumption that people already know exactly what these functions do; therefore, no further explanation is needed. Then to add further insult to this injury, you are usually made to feel stupid if you need to ask what these terms mean. The intellectual smugness caused by this high-mindedness is usually based on the false assumption that being uninformed somehow makes you unintelligent (and therefore worthy of derision?) But since this reasoning is completely false, I see no point in using unexplained, non-intuitive function names such as CAR and CDR when easy-to-understand names such as HEAD and TAIL will do perfectly well. However, in order to remove any possibility for intellectual smugness, let me talk to you as an intelligent (but possibly uninformed) person and explain what the terms CAR and CDR actually mean. In 1954, IBM launched the "Type 704 Electronic Data-Processing Machine" which at the time, was the only computer capable of handling complex mathematical calculations. Therefore, it was for this platform that two of the first high level programming languages were developed - FORTRAN in 1957 and LISP in 1958. The IBM 704 used two types of instruction, A and B. Type A instructions were 36 bits long and were composed of a 3-bit prefix (instruction code), a 15-bit decrement field, a 3-bit tag field, and a 15-bit address field. The term CAR was the IBM 704 assembly instruction for accessing the "Contents of the Address part of the Register". Similarly, CDR is the assembly macro for accessing the "Contents of the Decrement part of the Register". LISP used the address and decrement parts of the register to point respectively to the current and next elements of something called a CONS cell (I.E. one element in a singly linked list that here we identify as a PAIR). The names of the assembly instructions CAR and CDR were then adopted directly into LISP. In this blog, I will use the function names HEAD and TAIL instead of CAR and CDR. Once you get used to these names, you will immediately understand their use in other functional programming languages such as Erlang. The name TAIL is being used because the second item in our PAIR function will contain all items in the list except the current one. You could also use the name REST as an intuitive synonym for TAIL. Making a list, but not checking it twice Unlike Old Saint Nick, when we make a list, we will make it in such a way that we know it will be right; therefore, we won't need to check it. So, to make a list, we will need a PAIR function, and to access the data in the list, at least a HEAD and a TAIL function. We must also create functions that can create and then identify the terminator item. Now when we create a list, we will start with an EMPTY, or terminator item and then add items by nesting the previous list item into each subsequent pair as the second item.
{ var EMPTY = lib.PAIR(null)(null); var is_empty = pair => (lib.HEAD(pair) === null) && (lib.TAIL(pair) === null); // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Create a list consisting of a single item and the special // termination item EMPTY var list1 = lib.PAIR("A")(EMPTY); var result = {}; result.list1_head = lib.HEAD(list1); result.list1_tail = lib.TAIL(list1); result.list1_is_empty = is_empty(list1); // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Add a second item to the list var list2 = lib.PAIR("B")(list1); result.list2_head = lib.HEAD(list2); result.list2_tail = lib.TAIL(list2); result.list2_head_tail = lib.HEAD(lib.TAIL(list2)); // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - // Add a third item var list3 = lib.PAIR("C")(list2); result.list3_head = lib.HEAD(list3); result.list3_tail = lib.TAIL(list3); result.list3_head_tail = lib.HEAD(lib.TAIL(list3)); result.list3_tail_tail = lib.TAIL(lib.TAIL(list3)); result.list3_head_tail_tail = lib.HEAD(lib.TAIL(lib.TAIL(list3))); return result; }
Well, OK. But there are two problems that make our current list implementation particularly user unfriendly: Its pretty tedious to have to add characters one at a time The order of the characters in the list has been reversed So, we'd better fix that. There and Back Again: A Hobbit's (Functional Programming) Tale So let's write a pair of functions that can transform a basic JavaScript datatype such as a character string or an array into a list and back again. Here, I will jump straight to the finished functions rather than show their derivation. Since the functions that convert abstract lists into native JavaScript data types use recursion (via the Y-Combinator), we need a function that will prevent runaway recursion. Therefore, in addition to the is_empty function, we need another function called is_last. is_last takes the current list item and passes the second element to is_empty. Function is_last returns whatever value is returned from is_empty. In keeping with our established naming convention, the function names is_empty and is_last use all lowercase letters because they return JavaScript native datatypes. In the next blog, there will be a second version of these functions called IS_LAST and IS_EMPTY in all uppercase letters. The use of all caps function names denotes that they operate on, and return abstract functions instead of JavaScript native data types. Strings to Lists and Back Again
{ // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * // Convert a character string to a list whilst preserving the // character order // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * var make_str2list = fn_next=> list => str => (str.length > 0) ? fn_next(lib.PAIR(str.substr(-1))(list))(str.slice(0,-1)) : list; var str2list = str => lib.Y(make_str2list)(lib.EMPTY)(str); // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * // Convert a list back into a character string // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * var make_list2str = fn_next=> str => list => lib.is_last(list) ? str.concat(lib.HEAD(list)) : fn_next(str.concat(lib.HEAD(list)))(lib.TAIL(list)); var list2str = list => lib.Y(make_list2str)("")(list); var l = str2list("Hello world!"); return { list : l, list_char1 : lib.HEAD(l), list_char2 : lib.HEAD(lib.TAIL(l)), list_char3 : lib.HEAD(lib.TAIL(lib.TAIL(l))), list_as_string : list2str(l) } }
Arrays to Lists and Back Again Now, let's create a pair of functions that transform a list into a JavaScript array and back again. The actual implementation of this particular function requires that we overcome a quirk in the JavaScript language concerning the value returned by certain array functions such as push or unshift. We will need to use the JavaScript function Array.prototype.push to insert the current list item as a new element into the array. However, for reason known possibly only to Brendan Eich, the function Array.prototype.push does not return the newly modified array; instead, it returns the index of the newly inserted item — which is useful to neither man nor beast... So here, we must create our own version of the Array.prototype.push function that returns the modified array instead of the index value. This can be done simply enough by realising that JavaScript arrow functions do not create their own execution contexts; they execute entirely in the context of the calling function. Therefore, if we pass the result of a normal Array.prototype.push function as a parameter to an inner function, that function can ignore its parameter value (the index value of the newly inserted item) and return the modified array.
// Create our own push function that returns the new array rather // than the index of the newly inserted item push = arr => val => (idx => arr)(arr.push(val))
We can now use our own version of the push function to construct an array.
{ // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * // Convert a character string to a list whilst preserving the // character order // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * var make_str2list = fn_next=> list => str => (str.length > 0) ? fn_next(lib.PAIR(str.substr(-1))(list))(str.slice(0,-1)) : list; var str2list = str => lib.Y(make_str2list)(lib.EMPTY)(str); // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * // Convert a JavaScript array into a list // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * var make_array2list = fn_next=> list => array => (array.length === 0) ? list : fn_next(lib.PAIR(array[array.length-1])(list)) (array.slice(0,-1)); var array2list = lib.Y(make_array2list)(lib.EMPTY); // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * // Convert a list to a JavaScript array // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * var make_list2array = fn_next=> arr => list => lib.is_last(list) ? push(arr)(lib.HEAD(list)) : fn_next(push(arr)(lib.HEAD(list)))(lib.TAIL(list)); var list2array = list => lib.Y(make_list2array)([])(list); var list_of_nums = array2list([1,2,3,4]); var list_of_chars = str2list("Hello"); return { list_of_nums : list_of_nums, list_of_nums_1st : lib.HEAD(list_of_nums), list_of_nums_2nd : lib.HEAD(lib.TAIL(list_of_nums)), list_of_nums_3rd : lib.HEAD(lib.TAIL(lib.TAIL(list_of_nums))), list_of_chars : list_of_chars, list_of_chars_2_array : list2array(list_of_chars) } }
So there we have a basic implementation of a list. We can now take native JavaScript data types such as string or array and convert them into lists, and we can then convert these lists back into the native JavaScript data types. In the next blog, we'll look at how we can implement the classic map function on a list. Chris W
lib = { // ******************************************************************** // 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 // ******************************************************************** var PAIR = val1 => val2 => fn => fn(val1)(val2); var TRUE = true_part => false_part => true_part; var FALSE = true_part => false_part => false_part; var HEAD = pair => pair(TRUE); var TAIL = pair => pair(FALSE); var EMPTY = PAIR(null)(null); 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))) ) // ******************************************************************** // 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)(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); // ******************************************************************** // 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), 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 : EMPTY, 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 } }