Book Image

Mastering JavaScript Functional Programming

By : Federico Kereki
Book Image

Mastering JavaScript Functional Programming

By: Federico Kereki

Overview of this book

Functional programming is a programming paradigm for developing software using functions. Learning to use functional programming is a good way to write more concise code, with greater concurrency and performance. The JavaScript language is particularly suited to functional programming. This book provides comprehensive coverage of the major topics in functional programming with JavaScript to produce shorter, clearer, and testable programs. You’ll delve into functional programming; including writing and testing pure functions, reducing side-effects, and other features to make your applications functional in nature. Specifically, we’ll explore techniques to simplify coding, apply recursion for loopless coding, learn ways to achieve immutability, implement design patterns, and work with data types. By the end of this book, you’ll have developed the JavaScript skills you need to program functional applications with confidence.
Table of Contents (22 chapters)
Title Page
About the Author
About the Reviewer
Customer Feedback
Connecting Functions - Pipelining and Composition
Answers to Questions

Appendix 2. Answers to Questions

Here are solutions (partial, or worked out in full) to the questions posed along the text. In many cases, there are extra questions for you to do further work.

1.1. Classes as first class objects. If you remember that a class is basically a function that can be used with new, then it stands to reason that we should be able to pass classes as parameters to other functions. The makeSaluteClass() basically creates a class (that is, a special function) that uses a closure to remember the value of term. We'll be seeing more examples of these kind of things in the rest of the book.

1.2. Factorial errors. The key to avoiding repeated tests is to write a function that will:

  • First check the value of the argument to see it it's valid, and if so
  • Call an inner function to do the factorial itself, without worrying about erroneous arguments.
     const carefulFact = n => {
         if (
            typeof n !== "undefined" &&
            Number(n) === n &&
            n >= 0 &&
           n === Math.floor(n)
         ) {
const innerFact = n => (n === 0 ? 1 : n * innerFact(n - 1));
          return innerFact(n);

      console.log(carefulFact(3));     // 6, correct
      console.log(carefulFact(3.1));   // undefined
      console.log(carefulFact(-3));    // undefined
      console.log(carefulFact(-3.1));  // undefined
      console.log(carefulFact("3"));   // undefined
      console.log(carefulFact(false)); // undefined
      console.log(carefulFact([]));    // undefined
      console.log(carefulFact({}));    // undefined

You could throw an error on recognizing a wrong argument; I just ignored it, and let the function return undefined.

1.3. Climbing factorial. The following code does the trick. We add an auxilliary variable f, and we make it "climb" from 1 to n. We must be careful so factUp(0)===1.

const factUp = (n, f = 1) => (n <= f ? f : f * factUp(n, f + 1));

2.1. No extra variables. We can make do by using the fn variable itself as a flag; after having called fn(), we set the variable to null. Before calling fn(), we check if it's not null.

const once = fn => {
    return (...args) => {
fn && fn(...args);
fn = null;

2.2. Alternating functions. In a manner similar to what we did in the previous question, we call the first function, and then switch functions for the next time. We used a destructuring assignment to write the swap in a more compact manner: see

const alternator = (fn1, fn2) => {
    return (...args) => {
[fn1, fn2] = [fn2, fn1];

2.3. Everything has a limit! We simply check if the limit variable is greater than zero. If so, we decrement it by 1, and we call the original function; otherwise, we do nothing.

const thisManyTimes = (fn, limit) => {
    return (...args) => {
if (limit > 0) {
            return fn(...args);

3.1. Unitialized object? The key is that we missed wrapping the returned object in parentheses, so JS thinks the braces enclose code to be executed. In this case, "type" is considered to be labelling a statement, which doesn't really do nothing: it's an expression (t) with which nothing is done. So, the code is considered valid, and since it doesn't have an explicit return statement, the implicit returned value is undefined. See for more on labels, and on returning objects. The corrected code is as follows.

const simpleAction = t => ({
    type: t;

3.2. Are arrows allowed? There would be no problems with listArguments2(), but with listArguments() you would get an error, since arguments is not defined for arrow functions.

Uncaught ReferenceError: arguments is not defined

3.3. One liner. It works! (Yes, a one line answer is appropriate in this case!)

4.1. Minimalistic function. It works, just because fib(0)=0 and fib(1)=1, so it's true that for n<2, fib(n)=n.

4.2. A cheap way. Basically, this algorithm works the same way you'd calculate a Fibonacci number by hand. You'd start writing down fib(0)=0 and fib(1)=1, add them to get fib(2)=1, add the last two to get fib(3)=2, and so on. In this version of the algorithm, a and b stand for two consecutive Fibonacci numbers. This implementation is quite efficient!

4.3. A shuffle test. A simple idea: before shuffling the array, sort a copy of it, JSON.stringify() it, and save the result. After shuffling, sort a copy of the shuffled array, and JSON.stringify() it as well. Finally, the two produced JSON strings, which should be equal. This does away with all the other tests, since it ensures that the array doesn't change length, nor change its elements.


describe("shuffleTest", function() {
    it("shouldn't change the array length or its elements", () => {
        let a = [22, 9, 60, 12, 4, 56];
let old = JSON.stringify([...a].sort());
let new = JSON.stringify([...a].sort());

4.4. Breaking laws. Some of the properties are no longer always valid. To simplify the examples, let's assume two numbers are close to each other if they differ by no more than 0.1. Then:

  • 0.5 is close to 0.6, and 0.6 is close to 0.7, but 0.5 is not close to 0.7
  • 0.5 is close to 0.6, and 0.7 is close to 0.8, but 0.5+0.7=1.2 is not close to 0.6+0.8=1.4;
  • with the same numbers, 0.5*0.7=0.35 is not close to 0.6*0.8=0.48
  • 0.6 is close to 0.5, and 0.9 is close to 1.0, but 0.6/0.9=0.667 is not close to 0.5/1.0=0.5

The other cited properties are always true.

5.1. Filtering... but what? Boolean(x) is the same as !!x, and it turns an expression from "truthy" or "falsy", into true or false. Thus, the .filter() operation removes all falsy elements from the array.

5.2. Generating HTML code, with restrictions. In real life, you wouldn't limit yourself to using only .filter(), .map(), and .reduce(), but the objective of this question was to make you think how to manage with only those. Using .join() or other extra string functions, would make the problem easier. For instance, finding out a way to add the enclosing <div><ul> ... </ul></div> tags is tricky, so we had to make the first .reduce() operation produce an array, so we could keep on working on it.

var characters = [
    {name: "Fred", plays: "bowling"},
    {name: "Barney", plays: "chess"},
    {name: "Wilma", plays: "bridge"},
    {name: "Betty", plays: "checkers"},
    {name: "Pebbles", plays: "chess"}

let list = characters
    .filter(x => x.plays === "chess" || x.plays == "checkers")
    .map(x => `<li>${}</li>`)
    .reduce((a, x) => [a[0] + x], [""])
    .map(x => `<div><ul>${x}</ul></div>`)
    .reduce((a, x) => x);

// <div><ul><li>Barney</li><li>Betty</li><li>Pebbles</li></ul></div>

Accessing the array and index arguments to the .map() or .reduce() callbacks would also provide solutions.

let list2 = characters
    .filter(x => x.plays === "chess" || x.plays == "checkers")
        (x, i, t) =>
            `${i === 0 ? "<div><ul>" : ""}` +
            `<li>${}</li>` +
            `${i == t.length - 1 ? "</ul></div>" : ""}`
    .reduce((a, x) => a + x, "");

Or also:

let list3 = characters
    .filter(x => x.plays === "chess" || x.plays == "checkers")
    .map(x => `<li>${}</li>`)
        (a, x, i, t) => a + x + (i === t.length - 1 ? "</ul></div>" : ""),

Study the three examples: they will help you gain insight into these higher order functions, and provide you with ideas for further work of your own.

5.3. More formal testing. Use an idea from question 4.3: select an array and a function, find the result of mapping using both the standard .map() method and the new myMap() function, and compare the two JSON.stringify()-ed results: they should match.

5.4. Ranging far and wide. This requires a bit of careful arithmetic, but shouldn't be much trouble. We distinguish two cases: upward and downward ranges. The default step is 1 for the former, and -1 for the latter; we used Math.sign() for that.

const range2 = (start, stop, step = Math.sign(stop - start)) =>
    new Array(Math.ceil((stop - start) / step))
        .map((v, i) => start + i * step);

A few examples of calculated ranges show the diversity of options.

console.log(range2(1, 10));       // [1, 2, 3, 4, 5, 6, 7, 8, 9]
console.log(range2(1, 10, 2));    // [1, 3, 5, 7, 9]
console.log(range2(1, 10, 3));    // [1, 4, 7]
console.log(range2(1, 10, 6));    // [1, 7]
console.log(range2(1, 10, 11));   // [1]

console.log(range2(21, 10));      // [21, 20, 19, ... 13, 12, 11]
console.log(range2(21, 10, -3));  // [21, 18, 15, 12]
console.log(range2(21, 10, -4));  // [21, 17, 13]
console.log(range2(21, 10, -7));  // [21, 14]
console.log(range2(21, 10, -12)); // [21]

Using this new range2() function, means that you can write a greateer variety of loops in a functional way, with no need of for(...) statements.

5.5. Doing the alphabet. The problem is that String.fromCharCode() is not unary. This method may receive any number of arguments, and when you write map(String.fromCharCode), the callback gets called with three parameters (current value, index, array) and that causes unexpected results. Using unary() from section "Arity Changing" of Chapter 6, Producing Functions - Higher-Order Functions, would also work. See more on

5.6. Producing a CSV. A first solution, with some auxiliary functions, is as follows; can you understand what does each function do?

const concatNumbers = (a, b) => (a == " " ? b : a + "," + b);
const concatLines = (c, d) => c + "\n" + d;
const makeCSV = t =>
    t.reduce(concatLines, " ", => f.reduce(concatNumbers, " ")));

An alternative one-liner is also possible, but not so clear, in my opinion... do you agree?

const makeCSV2 = t =>
        (c, d) => c + "\n" + d,
        " ", => x.reduce((a, b) => (a == " " ? b : a + "," + b), " "))

6.1. A border case. Just applying the function to a null object will throw an error.

const getField = attr => obj => obj[attr];

// Uncaught TypeError: Cannot read property 'a' of null

Having functions throw exceptions isn't usually good in FP. You might opt to produce undefined instead, or work with monads as in the last chapter of the book. A safe version of getField() is as follows.

const getField2 = attr => obj => (attr && obj ? obj[attr] : undefined);

6.2. How many? Let's call calc(n) the number of calls needed to evaluate fib(n). Analyzing the tree that shows all the needed calculations, we get this:

  • calc(0)=1
  • calc(1)=1
  • for n>1, calc(n)=1 + calc(n-1) + calc(n-2)

The last line follows from the fact that when we call fib(n), we have one call, plus calls to fib(n-1) and fib(n-2). A spreadsheet shows that calc(50) is 40,730,022,147 -- rather high!

If you care for some algebra, it can be shown that calc(n)=5fib(n-1)+fib(n-4)-1, or that as n grows calc(n) becomes approximately (1+√5)=3.236 times the value of fib(n) -- but since this is not a Maths book, I won't even mention those results!

6.3. A randomizing balancer. Using our shuffle() function from Chapter 4, Behaving Properly - Pure Functions, we can write the following. We remove the first function from the list before shuffling the rest, and we add it back at the end of the array, to avoid repeating calls.

const randomizer = (...fns) => (...args) => {
    const first = fns.shift();
    fns = shuffle(fns);
    return fns[0](...args);

A quick verification shows it fulfills all our requirements.

const say1 = () => console.log(1);
const say22 = () => console.log(22);
const say333 = () => console.log(333);
const say4444 = () => console.log(4444);

const rrr = randomizer(say1, say22, say333, say4444);
rrr(); // 333
rrr(); // 4444
rrr(); // 333
rrr(); // 22
rrr(); // 333
rrr(); // 22
rrr(); // 333
rrr(); // 4444
rrr(); // 1
rrr(); // 4444

A small consideration: the first function in the list can never be called the first time around, because of the way that randomizer() is written. Can you provide a better version, that won't have this small defect, so that all functions in the list will have the same chance of being called the first time?

6.4. Just say no! Call the original function, and then use typeof to see if the returned value is numeric or boolean, before deciding what to return.

7.1. Sum as you will. The following sumMany() function does the job.

const sumMany = total => number =>
number === undefined ? total : sumMany(total + number);

sumMany(2)(2)(9)(6)(0)(-3)(); // 16

7.2. Working stylishly. We can do currying by hand for applyStyle().

const applyStyle = style => string => `<${style}>${string}</${style}>`;

7.3. Currying by prototype. Basically, we are just transforming the curryByBind() version to use this.

Function.prototype.curry = function() {
    return this.length === 0 ? this() : p => this.bind(this, p).curry();

You could work in a similar fashion and provide a .partial() method.

7.4. Uncurrying the curried. We can work in a similar fashion to what we did in curryByEval().

const uncurryByEval = (fn, len) =>
        `(${range(0, len)
            .map(i => `x${i}`)
            .join(",")}) => ${}${range(0, len)
            .map(i => `(x${i})`)

Earlier, when currying, given a fn() function of arity 3, we would have generated the following.

x0=>x1=>x2=> make3(x0,x1,x2)

Now, to uncurry a function (say, curriedFn()) we want to do something very similar: the only difference is the placement of the parentheses.

(x0,x1,x2) => curriedFn(x0)(x1)(x2)

The expected behavior follows.

const make3 = (a, b, c) => String(100 * a + 10 * b + c);
const make3c = a => b => c => make3(a, b, c);
console.log(make3c(1)(2)(3));  // 123

const remake3 = uncurryByEval(make3c, 3);
console.log(remake3(4, 5, 6)); // 456

8.1. Headline Capitalization. We can make use of several functional equivalents of different methods, such as .split(), .map(), or .join(). Using demethodize() from Chapter 6, Producing Functions - Higher-Order Functions, and flipTwo() from Chapter 7, Transforming Functions - Currying and Partial Application would have also been possible.

const split = str => arr => arr.split(str);
const map = fn => arr =>;
const firstToUpper = word =>
    word[0].toUpperCase() + word.substr(1).toLowerCase();
const join = str => arr => arr.join(str);

const headline = pipeline(split(" "), map(firstToUpper), join(" "));

The pipeline works as expected: we split the string into words, we map each word to make its first letter uppercase, and we join the array elements to form a string again. We could have used reduce() for the last step, but join() already does what we need, so why reinvent the wheel?

console.log(headline("Alice's ADVENTURES in WoNdErLaNd")); 
// Alice's Adventures In Wonderland

8.2. Pending tasks. The following pipeline does the job.

const getField = attr => obj => obj[attr];
const filter = fn => arr => arr.filter(fn);
const map = fn => arr =>;
const reduce = (fn, init) => arr => arr.reduce(fn, init);

const pending = (listOfTasks, name) =>
        filter(t => t.responsible === name),
        map(t => t.tasks),
        reduce((y, x) => x, []),
        filter(t => t && !t.done),
    )(allTasks || {byPerson: []}); //

The reduce() call may be mystifying. By that time, we are handling an array with a single element, an object, and we want the object in the pipeline, not the array. This code works even if the responsible person doesn't exist, or if all tasks are done; can you see why? Also note that if allTasks is null, an object must be provided with the .byPerson property, so future functions won't crash! For an even better solution, I think monads are better: see question 12.1.

8.3. Thinking in abstract terms. The simple solution implies composing. I preferred it to pipelining, to keep the list of functions in the same order.

const getSomeResults2 = compose(sort, group, filter, select);

9.1. Into reverse. An empty string is reversed by simply doing nothing. To reverse a non-empty string, remove its first character, reverse the rest, and append the removed character at the end. For example, reverse("MONTEVIDEO") can be found by doing reverse("ONTEVIDEO")+"M". In the same way, reverse("ONTEVIDEO") would equal reverse("NTEVIDEO")+"O", and so on.

const reverse = str =>
    str.length === 0 ? "" : reverse(str.slice(1)) + str[0];

9.2. Climbing steps. Suppose we want to climb a ladder with n steps. We can do it in two ways:

  • climbing one single step, and then climbing a (n-1) steps ladder, or
  • climbing two steps at once, and then climbing a (n-2) steps ladder.

So, if we call ladder(n) the number of ways to climb a n steps ladder, we have that ladder(n) = ladder(n-1) + ladder(n-2). Adding the fact that ladder(0)=1 (there's only 1 way to climb a ladder with no steps: do nothing) and ladder(1)=1, the solution is that ladder(n) equals the (n-1) Fibonacci number! Check it out: ladder(2)=2, ladder(3)=3, ladder(4)=5, etc.

9.3. Longest Common Subsequence. The length of the longest common sequence (LCS) of two strings a and b can be found with recursion as follows:

  • If the length of a is zero, or if the length of b is zero, return zero;
  • If the first characters of a and b match, the answer is 1 plus the LCS of a and b, both minus their initial characters; and
  • If the first characters of a and b do not match, the answer is the largest of the following two results:
    • the LCS of a minus its initial character, and b
    • the LCS of a, and b minus its initial character

An implementation follows. We do memoization "by hand" to avoid repeating calculations; we could also have used our memoization function.

const LCS = (strA, strB) => {
    let cache = {}; // memoization "by hand"

    const innerLCS = (strA, strB) => {
        const key = strA + "/" + strB;
        if (!(key in cache)) {
            if (strA.length === 0 || strB.length === 0) {
                ret = 0;
            } else if (strA[0] === strB[0]) {
                ret = 1 + innerLCS(strA.substr(1), strB.substr(1));
            } else {
                ret = Math.max(
                    innerLCS(strA, strB.substr(1)),
                    innerLCS(strA.substr(1), strB)
            cache[key] = ret;
        return cache[key];
    return innerLCS(strA, strB);

console.log(LCS("INTERNATIONAL", "CONTRACTOR")); // 6, as in the text

As an extra exercise, you could try to produce not only the length of the LCS, but also the characters involved.

9.4. Symmetrical queens. The key to finding only symmetric solutions, is that after the first 4 queens have been (tentatively) placed in the first half of the board, we don't have to try all possible positions for the other queens; they are automatically determined with regard to the first ones.

const SIZE = 8;
let places = Array(SIZE);
const checkPlace = (column, row) =>
        .slice(0, column)
        .every((v, i) => v !== row && Math.abs(v - row) !== column - i);

const symmetricFinder = (column = 0) => {
    if (column === SIZE) {
        console.log( => x + 1)); // print out solution
} else if (column <= SIZE / 2) { // first half of the board?
        const testRowsInColumn = j => {
            if (j < SIZE) {
                if (checkPlace(column, j)) {
                    places[column] = j;
                    symmetricFinder(column + 1);
                testRowsInColumn(j + 1);
} else { // second half of the board
      let symmetric = SIZE-1-places[SIZE-1-column];
        if (checkPlace(column, symmetric)) {
            places[column] = symmetric;
            symmetricFinder(column + 1);

Calling symmetricFinder() produces four solutions, which are essentially the same. Make drawings and check it!

[3, 5, 2, 8, 1, 7, 4, 6]
[4, 6, 8, 2, 7, 1, 3, 5]
[5, 3, 1, 7, 2, 8, 6, 4]
[6, 4, 7, 1, 8, 2, 5, 3]

9.5. Sorting recursively. Let's see just the first of these algorithms; many of the techniques here will help you write the other sorts. If the array is empty, sorting it produces a (new) empty array. Otherwise, we find the maximum value of the array (max), create a new copy of the array but without that element, sort the copy, and then return the sorted copy with max added at the end. Check how we dealt with the mutator functions, to avoid modifying the original string.

const selectionSort = arr => {
    if (arr.length === 0) {
        return [];
    } else {
        const max = Math.max(...arr);
        const rest = [...arr];
        rest.splice(arr.indexOf(max), 1);
return [...selectionSort(rest), max];

selectionSort([2, 2, 0, 9, 1, 9, 6, 0]);
[0, 0, 1, 2, 2, 6, 9, 9]

10.1. Freezing by proxying. As requested, using a proxy allows you to intercept changes on an object. (See for more on the subject.) We use recursion to apply the proxy "all the way down", in case some attributes are objects themselves.

const proxySetAll = obj => {
    Object.keys(obj).forEach(v => {
        if (typeof obj[v] === "object") {
            obj[v] = proxySetAll(obj[v]);
    return new Proxy(obj, {
set(target, key, value) {
            throw new Error("DON'T MODIFY ANYTHING IN ME");
deleteProperty(target, key) {
            throw new Error("DON'T DELETE ANYTHING IN ME");

We can see the results of this. You'd probably require something other than showing a "DON'T MODIFY ANYTHING IN ME" message, of course!

let myObj = {a: 5, b: 6, c: {d: 7, e: 8}};
myObj = proxySetAll(myObj);

myObj.a = 777;  // Uncaught Error: DON'T MODIFY ANYTHING IN ME
myObj.f = 888;  // Uncaught Error: DON'T MODIFY ANYTHING IN ME
delete myObj.b; // Uncaught Error: DON'T DELETE ANYTHING IN ME

10.2. Inserting into a list, persistently. Using recursion helps out.

  • If the list is empty, we cannot insert the new key.
  • If we are at a node, and its key isn't oldKey, we create a clone of the node, and insert the new key somewhere in the rest of the original node's list
  • If we are at a node, and its key is oldKey, we create a clone of the node, pointing at a list that starts with a new node, with newKey as its value, and itself pointing to the rest of the original node's list.
      const insertAfter = (list, newKey, oldKey) => {
          if (list === null) {
              return null;
          } else if (list.key !== oldKey) {
              return node(list.key, insertAfter(, newKey,                   oldKey));
          } else {
              return node(list.key, node(newKey,;

We can see this working. The new list is just as in figure 10.2. However, printing out the lists (c3 and newList) wouldn't be enough; you wouldn't be able to recognize the new or old nodes, so I included several comparisons. The last comparison below shows that from the "F" node onwards, the list is the same.

class Node {
    constructor(key, next = null) {
        this.key = key; = next;
const node = (key, next) => new Node(key, next);
let c3 = node("G", node("B", node("F", node("A", node("C", node("E"))))));
let newList = insertAfter(c3, "D", "B");

c3 === newList // false
c3.key === newList.key // true (both are "G") === // false === // true (both are "B") === // false === "F" // true === "D" // true === // true

As we implemented this, if oldKey isn't found, nothing is inserted. Could you change the logic so in that case, the new node would be added at the end of the list?

11.1. Decorating methods, the future way. As we said, decorators aren't yet a fixed, definitive feature. However, following we can write the following.

const logging = (target, name, descriptor) => {
    const savedMethod = descriptor.value;
    descriptor.value = function(...args) {
        console.log(`entering ${name}: ${args}`);
        try {
            const valueToReturn = savedMethod.bind(this)(...args);
            console.log(`exiting ${name}: ${valueToReturn}`);
            return valueToReturn;
        } catch (thrownError) {
            console.log(`exiting ${name}: threw ${thrownError}`);
            throw thrownError;
    return descriptor;

We want to add a @logging decoration to a method. We save the original method in savedMethod, and substitute a new method that will log the received arguments, call the original method saving its return value, log that, and finally return. If the original method throws an exception, we catch it, report it, and throw it again so it can be processed as expected. A simple example follows.

class SumThree {
    constructor(z) {
        this.z = z;
    sum(x, y) {
        return x + y + this.z;

new SumThree(100).sum(20, 8);
// entering sum: 20,8
// exiting sum: 128

11.2. Decorator with mixins. Working along the same lines as in question 1.1, we write an addBar() function that receives a Base class, and extends it. In this case, I decided to add a new attribute and a new method. The constructor for the extended class first calls the original constructor, and then creates the .barValue attribute. The new class has both the original's .doSomething() method, and the new .somethingElse() one.

class Foo {
    constructor(fooValue) {
        this.fooValue = fooValue;
    doSomething() {
        console.log("something: foo...", this.fooValue);

var addBar = Base =>
class extends Base {
        constructor(fooValue, barValue) {
this.barValue = barValue;

somethingElse() {
            console.log("something added: bar... ", this.barValue);

var fooBar = new (addBar(Foo))(22, 9);
fooBar.doSomething();   // something: foo... 22
fooBar.somethingElse(); // something added: bar... 9

12.1. Maybe tasks? The following code shows a simpler solution than the one we saw for question 8.2.

const pending = Maybe.of(listOfTasks)
    .map(filter(t => t.responsible === name))
    .map(t => tasks)
    .map(t => t[0])
    .map(filter(t => !t.done))

We just apply one function after the other, secure in the knowledge that if any of these functions produces an empty result (or even if the original listOfTasks is null) the sequence of calls will go on. At the end you will either get an array of task id's, or a null value.

12.2. Extending your trees. Calculating the tree's height is simple, in a recursive fashion. The height of an empty tree is zero, and the height of a non-empty tree is one (for the root) plus the maximum height of its left and right subtrees.

const treeHeight = tree =>
        (val, left, right) =>
            1 + Math.max(treeHeight(left), treeHeight(right)),
        () => 0

Listing the keys in order is a well known requirement. Because of the way that the tree is build, you first list the left subtree's keys, then the root, and finally the right subtree's keys, all in a recursive fashion.

const treeList = tree =>
        (value, left, right) => {
        () => {
            // nothing

Finally, deleting a key from a binary search tree is a bit more complex. First, you must locate the node that is going to be removed, and then there are several cases:

  • if the node has no subtrees, deletion is simple
  • if the node has only one subtree, you just replace the node by its subtree
  • and if the node has two subtrees, then you have to find the minimum key in the tree with a greater key, and place it in the node's place

Since this algorithm is well covered in all computer science textbooks, I won't go into more detail.

const treeRemove = (toRemove, tree) =>
    tree((val, left, right) => {
        const findMinimumAndRemove = (tree /* never empty */) =>
            tree((value, left, right) => {
                if (treeIsEmpty(left)) {
                    return {min: value, tree: right};
                } else {
                    const result = findMinimumAndRemove(left);
                    return {
                        min: result.min,
                        tree: Tree(value, result.tree, right)

        if (toRemove < val) {
            return Tree(val, treeRemove(toRemove, left), right);
        } else if (toRemove > val) {
            return Tree(val, left, treeRemove(toRemove, right));
        } else if (treeIsEmpty(left) && treeIsEmpty(right)) {
            return EmptyTree();
        } else if (treeIsEmpty(left) !== treeIsEmpty(right)) {
            return tree((val, left, right) =>
                left(() => left, () => right)
        } else {
            const result = findMinimumAndRemove(right);
            return Tree(result.min, left, result.tree);
    }, () => tree);

12.3. Functional lists. Let's add to the samples already given. We can simplify working with lists, if we can transform a list into an array, and vice versa.

const listToArray = list =>
    list((head, tail) => [head, ...listToArray(tail)], () => []);

const listFromArray = arr =>
        ? NewList(arr[0], listFromArray(arr.slice(1)))
        : EmptyList();

Concatenating two lists together, or appending a value to a list, have simple recursive implementations. And, we can reverse a list by using the appending function.

const listConcat = (list1, list2) =>
        (head, tail) => NewList(head, listConcat(tail, list2)),
        () => list2

const listAppend = value => list =>
        (head, tail) => NewList(head, listAppend(value)(tail)),
        () => NewList(value, EmptyList)

const listReverse = list =>
        (head, tail) => listAppend(head)(listReverse(tail)),
        () => EmptyList

Finally, the basic map(), filter() and reduce() operations are good to have.


const listMap = fn => list =>
        (head, tail) => NewList(fn(head), listMap(fn)(tail)),
        () => EmptyList

const listFilter = fn => list =>
        (head, tail) =>
                ? NewList(head, listFilter(fn)(tail))
                : listFilter(fn)(tail),
        () => EmptyList

const listReduce = (fn, accum) => list =>
        (head, tail) => listReduce(fn, fn(accum, head))(tail),
        () => accum

Some exercises left to you:

  • generate a printable version of a list
  • compare two lists to see if they have the same values, in the same order
  • search a list for a value
  • get, update, or remove, the value at the n-th position of a list

12.4. Shortening code. A first approach would get rid of the first ternary operator, by taking advantage of the short circuit evaluation of the || operator.


const treeSearch2 = (findValue, tree) =>
        (value, left, right) =>
findValue === value ||
            (findValue < value
                ? treeSearch2(findValue, left)
                : treeSearch2(findValue, right)),
        () => false

Also, seeing that both alternatives in the second ternary operator are very similar, you could also do some shortening there.

const treeSearch3 = (findValue, tree) =>
        (value, left, right) =>
            findValue === value ||
            treeSearch3(findValue, findValue < value ? left : right),
        () => false

Remember: Shorter doesn't imply better! However, I've found many examples of this kind of code tightening, and it's better if you have been exposed to it too.