Functional JavaScript: Building data structures from functions

In the past two columns, we’ve looked at higher-order functions and talked a little bit about the power of functional programming. So far, the concepts we’ve covered do little to indicate how powerful the basic building blocks of functional programming are when combined. In this post, we’ll examine how functions alone can be used as data and data structures. This may sound strange, but you’ll soon see what I mean.

I first came across the concepts in this post in the excellent MIT course, Structure and Interpretation of Computer Programs, or SICP. The original recordings of the course lectures are available through MIT OpenCourseWare and I highly recommend them. In my professional life of programming, JavaScript was effectively my first programming language, but thanks to the SICP lectures, Scheme was my second.

Let’s begin with a rather silly example that sets a baseline. Consider a simple function called parrot that takes an argument and returns the argument.

const parrot = (value) => {
  return value;
};
parrot(1); // returns 1
parrot('Anything'); // returns 'Anything'
parrot(parrot); // returns the function parrot

This is known as the identity function. It is not very interesting but does illustrate that we can call a function with data and get data back immediately. What if we want to get data back later? When we think about storing data for later, we often turn to variables, which simply store data for later use. Could we use a function instead? It turns out that yes, we can, by modifying our parrot function just a little. Instead of returning the value passed in immediately, we’ll return a function that returns the value.

const recall = (value) => {
  return () => {
    return value;
  };
};

const getValue = recall('My Value'); // This returns a function...
getValue(); // ...that when called, returns 'My Value'

When called with 'My Value', recall returns a function that returns 'My Value'. This is a sort of data storage mechanism that we can call at any time to retrieve the value. The above example may seem trivial and not very useful, and I grant that’s true in most cases, but it does demonstrate the use of a function as data. Let’s move on to implement a data structure.

We’re not going to do anything fancy. In fact we’ll build the bare minimum data structure: a pair of values. We’ll want to create our data structure by passing two values in, and we’ll want to be able to get either value back out of it. We can use our previous recall function as a starting point, but let’s rename it makePair. Where recall took a single value and returned a function that returned a single value, makePair will take in two values. Let’s make that relatively easy change:

const makePair = (value1, value2) => {
  return () => {
    return value1;
  };
};

Unfortunately, this function immediately “forgets” the second value and never does anything with it. Our inner function, the one that currently just returns value1, also needs to be modified to return value1 or value2. We’ll want the users of our data structure to be able to determine which value they want, so we’ll modify our inner function to accept an argument that will determine which value to return.

const makePair = (value1, value2) => {
  return (chooseFirst) => {
    if (chooseFirst === true) {
      return value1;
    } else {
      return value2;
    }
  };
};

const myPair = makePair('First Element', 'Second Element');
myPair(true); // Returns 'First Element'
myPair(false); // Returns 'Second Element'

This does exactly what we want it to, but there is a bit of a drawback. It’s not really clear what is supposed to happen when you pass true or false to our myPair function without first looking at the definition of the makePair function. This is an issue that can be fixed by writing two utility functions — getFirst and getSecond — that encapsulate the true/false logic:

const getFirst = (pair) => {
  return pair(true);
};

const getSecond = (pair) => {
  return pair(false);
};

getFirst(myPair); // Returns 'First Element'
getSecond(myPair); // Returns 'Second Element'

This is much more readable and meets the definition of the data structure we set out to create. Furthermore, makePair, getFirst, and getSecond can be used to build more complicated data structures. For example, implementing an immutable list structure could be easily done with virtually no additional logic:

const initializeList = (initialValue) => {
  return makePair(initialValue, undefined);
};

const shift = (value, stack) => {
  return makePair(value, stack);
};

const head = (stack) => {
  return getFirst(stack);
};

const tail = (stack) => {
  return getSecond(stack);
};

In the definitions above, I’ve added some convenience wrappers that give us more descriptive names for some of the manipulations, but otherwise the logic is unchanged. We can now initialize an immutable list, shift items to the head of the list, look at the head of the list, and get the tail of the list.

const myList = initializeList(1);
const sizeTwo = push(2, myList);
const sizeThree = push('Foo', sizeTwo);
const sizeFour = push(false, sizeThree);

head(sizeFour); // returns false
const tailedFour = tail(sizeFour);
head(tailedFour); // returns 'Foo'

If you look more carefully at the convenience wrappers, you may realize there is no real work being done there. The definition of those wrappers could just be aliases for the original functions we wrote:

const initializeList = makePair;
const shift = makePair;
const head = getFirst;
const tail = getSecond;

You wouldn’t want to use this toy data structure in your production applications. But understanding how functions can be used in this way can improve your overall understanding of functional programming. Did you like where this was going? If so, check out the SICP lectures—you’re bound to find a treasure trove of new ways of thinking. Have you built another data structure using only functions? Share it with me on Twitter @freethejazz.