**Gist**: JavaScript allows to describe lists as functions in a very natural way. By putting in place a few short albeit sophisticated functions called `cons`

, `car `

(aka `head`

) and `cdr `

(aka `tail`

) a complete system for handling lists (`create`

, `sort`

, `filter`

, etc.) as binary trees is shown here. Recursion of calls lies at the basis of all; any sizeable list in this system requires a huge call stack and, unfortunately, this seems to go against the way the various JavaScript engines are implemented. Therefore, this has to remain an exercise.

In the last couple of years, my studies about functional programming have shifted focus, moved away from Java and gotten into JavaScript. This was caused firstly by me going to work for a web agency and having to become proficient in that pesky language (well, only in its good parts :-))

Using JavaScript and its first-order functions, it is perfectly legitimate to stay away from classes, types and stuff. Being just you and the functions makes it just right to program …functionally.

My most relevant products so far are all on GitHub (user Muzietto):

*geieslists*: a complete (experimental !) library for managing lists built purely from primitive functions, starting from`cons`

,`car`

/`head`

,`cdr`

/`tail`

, and ending up with high-level list operations like`splice`

or`mergesort`

*littleFunkyJavaScripter*: a thorough rewrite of the Little Schemer in JavaScript, using geieslists as engine to build and manage the unavoidable lists. I still have to “do” chapter 10, but the rest of the book is all there, especially the supercool Y-combinator.*seasonedFunkyJavaScripter*: still work in progress. Same as above with regards to the Seasoned Schemer. I just got till chapter 13 and got stuck over`call-with-current-continuation`

. I hope I’ll be able to proceed further in the future: continuations are insanely interesting.*geiesmonads*: maybe and state monad in JavaScript – examples of usage. In the case of the state monad you can find there the embryo for a whole system of modular, chainable operations.*geiesfolds*: Fold right and then left in JavaScript. Lots of examples of usages.

(*geieslists *reads *j-s-lists* in Italian, how funny…)

### Example list computation in JavaScript

I am presenting a simple example using geieslists. Let’s evaluate the head of a two-elements list.

Inside geieslists any list (in the best LISP tradition) is the concatenation of an element `car `

and another list `cdr`

. This concatenation takes place through the application of a function named `cons `

(they tell me that’s an abbreviation of *constructor*), which binds those two values. The resulting `cons `

is obviously a list, just like `cdr `

was. A list of two elements `'a'`

and `'b'`

is created recursively starting from a value `EMPTY_LIST`

(we’ll see later what an `EMPTY_LIST`

is) as:

`list = cons('a',cons('b',EMPTY_LIST))`

#### Off with her head!

When we want to extract the head (aka `car`

) of that list (aka `cons`

), we apply over that `cons `

a function named `head `

(or `car`

); `head `

passes to `cons `

a third function (in this case anonymous) which, given two arguments, simply returns the first one. Those two arguments happen to be the original two values given to cons in the previous paragraph. In detail, the expression of head is:

```
head = function(cons){
return cons(function(first,second){
return first;
});
};
```

In other words the head of a list comes from the application of function head to list; that’s the result of running:

```
head(list) = (function(cons){
return cons(function(first,second){
return first;
});
)(list)
```

If we search instead the `tail`

, we apply over the same `cons `

a function named `tail `

(or `cdr`

); `tail `

passes to `cons `

a new anonymous binary function that receives the two original values of the `cons `

and returns the second one. In short, the tail of a list is the result of running:

```
tail(list) = (function(cons){
return cons(function(first,second){
return second;
});
)(list)
```

#### Happy the cons: he lives a simple life

The missing piece is `cons`

. `cons `

is basically a binary function with a single simple goal in life: to allow other binary functions to access its two original arguments and use them as **their **own arguments. In a way, `cons `

does nothing with its arguments; it just wraps them and keeps them warm and ready for other functions to use. In plain JavaScript:

```
cons = function(first, second) {
return function(anotherBinaryFunction){
return anotherBinaryFunction(first, second);
};
};
```

Technically `cons `

is a function that receives two arguments, runs and returns as a result a function which in turn is ready to receive another function as its parameter. A bit dizzying, first time I saw it.

This means that if we pass to the function `cons(first, second)`

another function as parameter, the value `cons(first, second)(anotherBinaryFunction)`

will be whatever returns from running `anotherBinaryFunctions `

using `cons`

‘ arguments as parameters. In detail:

```
cons(first, second)(anotherBinaryFunction) =
anotherBinaryFunction(first, second);
```

In the case of the two-elements list we’d have:

```
cons('a', cons('b', EMPTY_LIST))(anotherBinaryFunction) =
anotherBinaryFunction('a', cons('b', EMPTY_LIST));
```

If we want to extract the head of this two-elements list and we recall the definition of `head`

, the substitution goes:

```
cons('a', cons('b', EMPTY_LIST))(head) =
headInnerBinaryFunction('a', cons('b', EMPTY_LIST)) =
(function(x, y) { return x; })('a', cons('b', EMPTY_LIST)) = 'a';
```

This makes a lot of sense when told this way, but things ain’t that easy. In the code of our program we don’t write:

`cons('a', cons('b', EMPTY_LIST))(head)`

but we write instead:

`head(cons('a', cons('b', EMPTY_LIST)))`

What makes the magic happen, so that:

`head(cons('a', cons(‘b’, EMPTY_LIST))) = 'a'`

like if there was no `cons`

in between ?

#### Head’s Version

Here is how the matter is seen from the point of view of head. I guess it is better to use here a simpler lambda notation (Scala, Java8) that allows to see clearly input parameters and returned values.

In this notation `cons`

, `head `

and `tail `

become respectively (please compare with the JavaScript implementations given previously):

```
cons = (x, y) -> w -> w(x, y)
head = c -> c((x, y) -> x)
tail = c -> c((x, y) -> y)
```

Here `c`

is a shortcut/reminder that the operand of `head `

and `tail `

is a `cons`

. We saw that:

`head(list) = `**(**c -> c((x, y) -> x)**)**(cons('a', cons('b', EMPTY_LIST)))

NB: I am putting in **bold **the two brackets that delimit head.

For the sake of clarity, let’s substitute:

`cons('b', EMPTY_LIST) = TAIL`

Substituting inside list the first usage of `cons `

with its definition we obtain:

`head(list) = `**(**c -> c((x, y) -> x)**)**(cons('a', TAIL)) =
**(**c -> c((x, y) -> x)**)**(w -> w('a', TAIL))

At this point we see that technically `head `

receives its `cons`

, which is nothing else than a closure carrying the whole list. Because of the definition of `head`

, parameter `c`

(the `cons`

) becomes `c(fun)`

, where `fun `

is that convenient inner binary function that always returns the first of its own parameters: that’s where `head `

got its name from. The steps are (please follow carefully the various substitutions):

`head(list) = `**(**c -> c((x, y) -> x)**)**(w -> w('a', TAIL)) =
(w -> w('a', TAIL))((x, y) -> x)) =
((x, y) -> x))('a', TAIL) = 'a'

So, in a way, `head `

and `cons `

pass each other the sherry…

Basically, `cons `

and `head `

(or `tail`

) plug into each other: `cons `

takes a function and gives it its own context; `head `

takes a function and gives it a visitor that operates in its context. In a way, `head `

is more *refined*; `cons `

is more *generic*. `head `

is the specialist, and so is `tail`

.

There is lot to understand here, a lot more to dig and discover:

- are there other possible list specialists besides
`head`

and`tail`

? - what are the characteristics that make these functions pluggable in each other?
- what are other problems (not necessarily involving lists) that may be solved by pairs of such crafted functions?

The key must be in the signatures, but it’s the bodies that express the intent. Gotta play some more with these concepts.

**UPDATE **All the playing resulted in another post, which investigates whether this may be a known FP pattern.

#### Full of Emptiness

The last bit is the definition of `EMPTY_LIST`

.

`EMPTY_LIST`

is something that, whenever encountered, signals that it’s time to stop processing the list. It can be any value. But here we are used to have `cdr `

as a function, so it’s nicer that `EMPTY_LIST`

be a function (provided that we use always exactly the same instance!). We like the fixed-point function because it reminds us of the Y-combinator, so we say:

`EMPTY_LIST = function(x) { return x; }`

### The problem with the stack of the function calls

At the heart of this system we have recursive calls to the cons function. This creates very soon a huge call stack for each list you need. It comes out that javaScript engines are not optimized for recurring on closures [1] (why is that?).

This impacts both the waste of memory created by each list and the running time of a mid-sized cons operation. It is interesting to measure the impact on execution speed by using the benchmark page [1]

The pages I owe credit to for building geieslists are primarily three:

- http://matt.might.net/articles/js-church/
- http://blairmitchelmore.com/javascript/cons-car-and-cdr
- http://dankogai.typepad.com/blog/2006/03/lambda_calculus.html

[1] see http://spencertipping.com/js-instabench/ – please compare:

– allocating small structures -> 1M (int, int) pairs as array literals

– allocating small structures -> 1M (int, int) pairs as binary CPS closures

– accessing small structures -> 1M (int, int) pairs as array literals

– accessing small structures -> 1M (int, int) pairs as binary CPS closures