# List Out of Lambda

Posted on March 30th, 2013.

If you ignore the practical issues of computers like size, weight, cost, heat,
and so on, what do you *really* need in a programming language? Let's play
around with this question.

To understand this post you'll need a basic understanding of how functions in Javascript work. If you can look at this code and understand what it prints, you're good to go:

```
var x = 10;
var f = function(y) {
console.log(x);
console.log(y);
}
var g = f;
f(1);
g(2);
```

This blog post is a thought exercise. It's not something you'd ever use for real code. But just like a guitarist practices scales that she won't ever play in a song, we programmers should be exercising our brains every so often.

I'm going to use Javascript for the examples. Any language with first class functions and lexical scoping (basically: closures) will work. The examples would be prettier in a Lisp, but some people would be turned off by the syntax and miss out on some interesting ideas. Feel free to port the code if it bothers you.

If you've already seen this kind of thing before (maybe you've gone through The Little Schemer or SICP) you may want to just skim the code here and look for anything new.

If you *haven't* seen anything like this, then you're in for a treat! It's all
going to look extremely weird the first time you see it. Go slowly and make
sure you understand each piece fully before moving on to the next. These
concepts may be unintuitive, but they're built from very simple pieces.

Finally: if you get stuck, don't worry. Tracing out the execution of a function on paper can be a good way to wrap your brain around it (I recommend investing in a good lap desk for comfy reading and writing). If that doesn't work, just close the window and come back tomorrow. Sometimes new concepts need a while to rattle around in your brain before they click into place.

## Lists

Let's get started. One of the most common things we do as programmers is grouping data together. Javascript has "arrays" built in to the language for this:

`var names = ["Alice", "Bob", "Candice"];`

What if Javascript didn't come with arrays included? Could we create them (or something like them) ourselves?

To answer this, let's think about the bare minimum we'd need to "bootstrap" something like an array. There are a number of ways to do this, but we're going to look at one in particular.

We'll call our array-like thing a "list". To make it work, we need four parts:

- The concept of "the empty list".
- A way to add an element to the front of a list.
- A way to take a list and get the first element.
- A way to take a list and get everything
*but*the first element.

If we have those four things, we can build on top of them to do anything else we might want. For example: to make a list of one item, you add that item to the front of the empty list.

Let's narrow this down further. There are lots of ways you could implement those four things — I'm going to use functions. Let's sketch out an outline:

```
var empty_list = null;
var prepend = function(el, list) {
// ...
};
var head = function(list) {
// ...
};
var tail = function(list) {
// ...
};
var is_empty = function(list) {
// ...
};
```

Here are the descriptions of each of these items.

The `empty_list`

is a special value that represents a list of zero elements.
It can be anything, so for now we'll use `null`

(we'll revisit this later).

`prepend(1, some_list)`

will return a new list that looks like the old one, but
with `1`

stuck onto the front of it. So if we want to create a list of the
numbers `1`

and `2`

we can say `prepend(1, prepend(2, empty_list))`

or "prepend
one to the result of prepending 2 to the empty list".

`head(some_list)`

will return the first element in the list. Calling it on the
empty list will be undefined, so we'll just be very careful not to do that!

`tail(some_list)`

will return a new list that's like the one we gave it, but
with the first element removed. Again, calling this on an empty list will make
things explode.

`is_empty(some_list)`

will return `true`

if the list given to it is the empty
list, and `false`

otherwise.

Once we have those four functions (plus the special empty list value) we can start building on top of them, so let's figure out how to make them!

### List Out of If

If you haven't seen anything like this before, you might think it's time to start creating Javascript Objects. That's certainly one way to do it.

Since this post is a thought experiment in what we actually *need*, though,
let's try to avoid using big language features (like Objects) unless we
absolutely can't avoid it.

So if we don't want to use other language features yet, what are we left with?
Well so far our skeleton only has functions (and `null`

), so let's try those!

Here's the first working revision of the building blocks of lists:

```
var empty_list = null;
var prepend = function(el, list) {
return function(command) {
if (command === "head") {
return el;
} else if (command === "tail") {
return list;
}
}
};
var head = function(list) {
return list("head");
};
var tail = function(list) {
return list("tail");
};
var is_empty = function(list) {
return list === null;
};
```

Go ahead and paste that into a browser console and play with it:

```
var e = empty_list;
console.log(is_empty(e));
// true
var names = prepend("Alice",
prepend("Bob",
prepend("Candice",
empty_list)));
console.log(is_empty(names));
// False
console.log(head(names));
// Alice
console.log(tail(names));
// Some function representing the list of ("Bob", "Candice")
console.log(head(tail(names)));
// Bob
```

### But Where is the Data?

Did the definitions of those functions surprise you? Lists seem like such an important, object-oriented concept, but there only appear to be functions here!

Let's look at how this actually works. First of all, the "empty list" concept is pretty straightforward:

```
var empty_list = null;
var is_empty = function(list) {
return list === null;
};
```

We could have picked any arbitrary value here. `null`

seemed appropriate, so
I used that.

Now on to the meat of things: `prepend`

.

```
var prepend = function(el, list) {
return function(command) {
if (command === "head") {
return el;
} else if (command === "tail") {
return list;
}
}
};
```

This is where the real magic happens. Let's think through it.

First of all, we know that when you prepend something to a list, you're going to
get a (new) list back. So whatever `prepend`

returns must be a list.

Looking at the code, we can see it returns a function. So in our little thought experiment, a list is actually a Javascript function under the hood!

So what do we need to do with lists (aside from empty checking, which we've
already covered)? Well, we need to be able to get the head and the tail. When
we call `prepend(h, t)`

, we happen to be conveniently specifying the head and
tail as the arguments! So in `prepend`

we return a function that knows how to
return its own head or tail when asked.

So a "list" is "a function that knows how to return its own head or tail when
asked". So our `head`

and `tail`

functions just need to ask nicely!

```
var head = function(list) {
return list("head");
};
var tail = function(list) {
return list("tail");
};
```

That's it! We've created lists in 23 lines of code without using any fancy things like Objects. Before you move on, make sure you really understand why this works. Write out a few examples on paper.

```
var empty_list = null;
var prepend = function(el, list) {
return function(command) {
if (command === "head") {
return el;
} else if (command === "tail") {
return list;
}
}
};
var head = function(list) {
return list("head");
};
var tail = function(list) {
return list("tail");
};
var is_empty = function(list) {
return list === null;
};
```

### Building on the Foundations

Now that we have lists, let's implement a few common things on top of them as practice.

#### map

A common thing to do to a list is to create a new list by looping through it and doing something to each item. This is called "map":

```
var map = function(fn, l) {
if (is_empty(l)) {
return empty_list;
} else {
return prepend(fn(head(l)), map(fn, tail(l)));
}
};
```

If you're not used to recursive definitions like this, you may want to take a few minutes and try to work out how it works. Here's an example:

```
var square = function(x) {
return x * x;
}
var numbers = prepend(1, prepend(2, prepend(3, empty_list)));
var squared_numbers = map(square, numbers);
// map(square, [1, 2, 3])
// prepend(square(1), map(square, [1, 2, 3]))
// prepend(square(1), prepend(square(2), map(square, [3])))
// prepend(square(1), prepend(square(2), prepend(square(3), map(square, []))))
// prepend(square(1), prepend(square(2), prepend(square(3), [])))
// prepend(square(1), prepend(square(2), prepend(9, [])))
// prepend(square(1), prepend(square(2), [9]))
// prepend(square(1), prepend(4, [9]))
// prepend(square(1), [4, 9])
// prepend(1, [4, 9])
// [1, 4, 9]
```

I'm using brackets here to represent lists, but remember that these aren't
arrays, but are actually the functions that were returned by `prepend`

.

If you're still not sure about this, trace out every step of ```
map(square,
empty_list)
```

on paper. Then trace out every step of ```
map(square, prepend(10,
empty_list))
```

.

Thinking recursively like this takes some practice. I have notebooks filled with pages like this. Experienced guitarists practice new material slowly and methodically — there's no reason programmers shouldn't do the same. Watching the function calls expand and contract on paper can help you feel in your gut how these things work in a way that just staring at the words can't.

#### filter

We're going to start moving a bit faster now, but you should still make sure you understand everything completely before moving on. Take as much time as you need. Write things out. Run them. Get a feel for them.

The next "utility" function we'll build on top of lists is `filter`

, which
takes a function and a list, and returns a new list whose elements are those in
the original that make the function return `true`

. Here's an example:

```
var numbers = prepend(1, prepend(2, prepend(3, empty_list)));
var is_odd = function(x) {
return x % 2 === 1;
}
filter(is_odd, numbers);
// [1, 3]
```

Now let's implement `filter`

:

```
var filter = function(fn, l) {
if (is_empty(l)) {
return empty_list;
} else if (fn(head(l))) {
return prepend(head(l), filter(fn, tail(l)));
} else {
return filter(fn, tail(l));
}
};
```

Take your time. Trace out some examples. Move on when you feel it in your gut.

#### and, or, not

Let's take a slight detour to implement a few "helper" functions. Τhese don't have anything specifically to do with lists, but we'll need them later.

```
var not = function(x) {
if (x) {
return false;
} else {
return true;
}
};
var and = function(a, b) {
if (a) {
if (b) {
return true;
} else {
return false;
}
} else {
return false;
}
};
var or = function(a, b) {
if (a) {
return true;
} else {
if (b) {
return true;
} else {
return false;
}
}
};
```

Javascript already has these things built in as `!`

, `&&`

, and `||`

, of course,
but remember that in this thought exercise we're trying to avoid using extra
language features if we don't need them. How far can we scrape by on just
functions and `if`

statements?

One small note: these functions are just normal Javascript functions, which
means that `and(a, b)`

will *not* short-circuit like `a && b`

would. For our
purposes here that won't hurt us, but it's something to be aware of.

### List Out of Lambda

Now that we've had a bit more practice, let's go back to our definition of lists:

```
var empty_list = null;
var prepend = function(el, list) {
return function(command) {
if (command === "head") {
return el;
} else if (command === "tail") {
return list;
}
}
};
var head = function(list) {
return list("head");
};
var tail = function(list) {
return list("tail");
};
var is_empty = function(list) {
return list === null;
};
```

There are a few things about this implementation that bother me. Our goal is to use as few language features as possible, but we've actually used quite a few! I count at least five:

- Functions
`if`

statements- Strings
- Booleans (the
`true`

/`false`

result of`is_empty`

) - Equality checking (the
`===`

checks)

It turns out we can remove most of those things at the cost of a bit of readability (and more bending of our minds).

Let's start by rewriting the core three functions to ditch those ugly strings,
equality checks, and even the `if`

statement:

```
var prepend = function(el, list) {
return function(selector) {
return selector(el, list);
};
};
var head = function(list) {
return list(function(h, t) {
return h;
});
};
var tail = function(list) {
return list(function(h, t) {
return t;
});
};
```

You may want to get a snack before wrapping your brain around this one! There's
no strings, no equality checking, no `if`

statements. But we still have lists!

The `prepend`

functions still returns a function, just like before. Remember
that in the last implementation, a "list" was really a function that knew how to
give out its head or its tail when asked for them.

This time, we're inverting the "asking". In this version, a "list" is "a
function that will tell another function about both its head *and* its tail when
asked". This time the *asker* gets *both* pieces, and can decide which one they
want to use.

Let's look at the `head`

function:

`head`

takes a list and says`return list(...)`

, which means: "Hey list, I would like you to tell all of your info to this little helper function I'm giving you".- The list says
`return ...(el, list)`

, which means: "Okay helper function, here's my head and my tail, enjoy!" - The helper function that
`head`

originally gave was`function(h, t) { return h; }`

. So when the list calls it with the head and the tail as arguments, it returns the head and ignores the tail. `head`

takes that result and just returns it straight through back to the caller.

`tail`

works exactly the same way, but its helper function returns the second
argument (the tail) instead of the first.

That's it! The equality checking and `if`

statements have disappeared. Can you
describe where they've gone? What has taken their place?

Before we move on, let's clean up the idea of the empty list. It's still using
`null`

and equality checking. Let's remove those and make things a little more
uniform.

To do this we'll need to change the other three functions a bit as well, but if you've understood everything so far it shouldn't be too bad.

```
var empty_list = function(selector) {
return selector(undefined, undefined, true);
};
var prepend = function(el, list) {
return function(selector) {
return selector(el, list, false);
};
};
var head = function(list) {
return list(function(h, t, e) {
return h;
});
};
var tail = function(list) {
return list(function(h, t, e) {
return t;
});
};
var is_empty = function(list) {
return list(function(h, t, e) {
return e;
});
};
```

We've now made lists a bit smarter. In addition to telling the helper function
their head and tail, they also tell it "am I the empty list?". We've modified
the helpers `head`

and `tail`

to accept (and ignore) this extra argument.

We then modified `is_empty`

to work just like `head`

and `tail`

.

Finally, we've redefined `empty_list`

to match the rest of the lists instead of
being a special, magic value. The empty list is now just like a normal one:
it's a function that takes an "asker" and tells that asker "Hey, my head and
tail are undefined and I am the empty list".

I used `undefined`

here which is technically another language feature because
it's easier to read. Feel free to replace it with anything you want to make it
more pure. Since we're being very careful to never call `head`

or `tail`

on the
empty list those values will never be seen anyway.

So after all that, we've finally implemented the building blocks of lists with only two things:

- Functions.
`true`

and`false`

for empty lists.

If you're up for a challenge, think about whether you could remove that second
item (and if so, are you *really* removing it, or just using certain features of
Javascript implicitly instead of explicitly?).

## A Brief Intermission

Let's take a minute to reflect on all the code we've seen so far. First, we have an implementation of lists that uses only functions and booleans:

```
var empty_list = function(selector) {
return selector(undefined, undefined, true);
};
var prepend = function(el, list) {
return function(selector) {
return selector(el, list, false);
};
};
var head = function(list) {
return list(function(h, t, e) {
return h;
});
};
var tail = function(list) {
return list(function(h, t, e) {
return t;
});
};
var is_empty = function(list) {
return list(function(h, t, e) {
return e;
});
};
```

From this point on, we can now ignore the details of how lists are implemented.
As long as we have `head`

, `tail`

, and `prepend`

we don't need to worry about
what lists actually *are* under the hood.

We also built a few helper functions on top of this foundation:

```
var not = function(x) {
if (x) {
return false;
} else {
return true;
}
};
var and = function(a, b) {
if (a) {
if (b) {
return true;
} else {
return false;
}
} else {
return false;
}
};
var or = function(a, b) {
if (a) {
return true;
} else {
if (b) {
return true;
} else {
return false;
}
}
};
var map = function(fn, l) {
if (is_empty(l)) {
return empty_list;
} else {
return prepend(fn(head(l)), map(fn, tail(l)));
}
};
var filter = function(fn, l) {
if (is_empty(l)) {
return empty_list;
} else if (fn(head(l))) {
return prepend(head(l), filter(fn, tail(l)));
} else {
return filter(fn, tail(l));
}
};
```

Before you move on, make sure all of this code is crystal clear. Come back tomorrow if you need to let it sink in. We're about to go a lot deeper into the rabbit hole, so make sure you're ready.

## Numbers

If you look at the definitions of `prepend`

, `head`

, and `tail`

, they're pretty
mind-bending. However, the definitions of `map`

and `filter`

are much more
straightforward.

This is because we encapsulated the implementation of lists into the first four
functions. We did all the hard work of building lists out of almost nothing at
all and hid it behind that simple `prepend`

, `head`

, and `tail`

interface.

The idea of creating things from simple pieces and abstracting them into "black boxes" is one of the most important parts of both computer science and programming, so let's take it a step further and get some more practice by implementing numbers.

### What is a Number?

For this blog post we're only going to concern ourselves with non-negative integers. Feel free to try extending all this to include negative integers if you want more.

How can we represent a number? Well we could obviously use Javascript numbers
like `14`

, but that's not very fun, and we're trying to minimize the number of
language features we use.

One way to represent a number is a list whose length is the number. So we could
say that `[1, 1, 1]`

means "three", `["cats", null]`

means "two", and `[]`

means
"zero".

The elements themselves don't really matter, so let's just pick something we already have: the empty list! Let's write out a few to get a feel for this:

```
var zero = empty_list;
// []
var one = prepend(empty_list, empty_list);
// [ [] ]
var two = prepend(empty_list, prepend(empty_list, empty_list));
// [ [], [] ]
```

### inc, dec

We're going to want to *do* things with our numbers, so let's start writing
things that work with this "list of things" representation of numbers.

Our basic building blocks are going to be `inc`

and `dec`

(increment and
decrement).

```
var inc = function(n) {
return prepend(empty_list, n);
};
var dec = function(n) {
return tail(n);
};
```

To add 1 to a number, we just push another element on the list. So
`inc(inc(zero))`

means "two".

To subtract 1, we just pop off one of the elements: `dec(two)`

means "one"
(remember we're ignoring negative numbers).

### is_zero

When we started working with lists we used `is_empty`

a lot, so it's probably
a good idea to create an `is_zero`

function at this point:

```
var is_zero = function(n) {
return is_empty(n);
};
```

Zero is just represented by the empty list, so this one is easy!

### add

Adding one is easy, but we're probably going to want to add arbitrary numbers
together. Now that we have `inc`

and `dec`

this is actually pretty easy:

```
var add = function(a, b) {
if (is_zero(b)) {
return a;
} else {
return add(inc(a), dec(b));
}
};
```

This is another recursive definition. When adding two numbers, there are two possibilities:

- If
`b`

is zero, then anything plus zero is itself, so we can just return`a`

. - Otherwise, adding
`a + b`

is the same as adding`(a + 1) + (b - 1)`

.

Eventually `b`

will "bottom out" and return `a`

(which has been steadily getting
bigger as `b`

got smaller).

Notice how we didn't say anything about lists here! The "numbers are lists
under the hood" idea has been encapsulated behind `is_zero`

, `inc`

, and `dec`

,
so we can ignore it and work at the "number" level of abstraction from here on
out.

### sub

Subtraction is similar to addition, but instead of *increasing* `a`

as `b`

gets
smaller, we *decrease* them both together:

```
var sub = function(a, b) {
if (is_zero(b)) {
return a;
} else {
return sub(dec(a), dec(b));
}
};
```

Now we can say something like `add(two, sub(three, two))`

and the result will be
a representation of "three" in our system (which, of course, is a list of three
elements).

Pause for a minute now and remember that underneath numbers are lists, and
underneath lists there's nothing but functions. We can add and subtract
integers and underneath it all it's just functions shuffling around, expanding
into other functions and contracting as they're called, and this writhing mass
of lambdas somehow ends up representing `1 + 1 = 2`

. That's pretty cool!

### mul, pow

For practice let's create a way to multiply numbers:

```
var mul = function(a, b) {
if (is_zero(b)) {
return zero;
} else {
return add(a, mul(a, dec(b)));
}
};
```

Building on `add`

makes this pretty easy. `3 * 4`

is the same as ```
3
+ 3 + 3 + 3 + 0
```

. Trace out the execution on paper if things are starting to
get away from you. Carry on when you're ready.

`pow`

("power" or exponential) follows a similar structure as `mul`

, but instead
of adding together the copies we multiply them, and our base is one instead of
zero:

```
var pow = function(a, b) {
if (is_zero(b)) {
return one;
} else {
return mul(a, pow(a, dec(b)));
}
};
```

### is_equal

A common thing to do with numbers is to check if two are equal, so let's write that:

```
var is_equal = function(n, m) {
if (and(is_zero(n), is_zero(m))) {
return true;
} else if (or(is_zero(n), is_zero(m))) {
return false;
} else {
return is_equal(dec(n), dec(m));
}
};
```

There are three cases here:

- If both numbers are zero, they are equal.
- If only one number is zero (but not both, or the first case would have caught
it), then they are
*not*equal. - Otherwise, subtract one from each and try again.

When calling this function with two non-zero numbers, both will be decremented in tandem until one of them bottoms out at zero first, or until they bottom out at the same time.

### less_than, greater_than

We can take a similar approach to implementing `less_than`

:

```
var less_than = function(a, b) {
if (and(is_zero(a), is_zero(b))) {
return false;
} else if (is_zero(a)) {
return true;
} else if (is_zero(b)) {
return false;
} else {
return less_than(dec(a), dec(b));
}
};
```

The difference here is that we have four cases.

- If both numbers are zero, then
`a`

is not less than`b`

. - Otherwise if
`a`

is zero (and we know`b`

isn't) then yes,`a`

is less than`b`

. - Otherwise if
`b`

is zero (and we know that`a`

isn't) then no,`a`

cannot be less than`b`

(remember that we're ignoring negative numbers). - Otherwise decrement both and try again.

Once again, both numbers race to bottom out, and the outcome is decided by which one bottoms out first.

We could do something similar for `greater_than`

, but let's do it the easy way
instead:

```
var greater_than = function(a, b) {
return less_than(b, a);
};
```

### div, mod

Once we have `less_than`

we're ready to implement division and remainders:

```
var div = function(a, b) {
if (less_than(a, b)) {
return zero;
} else {
return inc(div(sub(a, b), b));
}
};
var rem = function(a, b) {
if (less_than(a, b)) {
return a;
} else {
return rem(sub(a, b), b);
}
};
```

This pair is a bit more complicated than the three other basic operations because we can't deal with negative numbers. Make sure you understand how it works.

## Full Circle

At this point, we have a (very basic) working system of numbers built on top of lists. Let's chase our tails a bit and implement a few more list functions that use numbers.

### nth

To get the Nth item in a list, we just pop things off of it as we decrement N until we hit zero:

```
var nth = function(l, n) {
if (is_zero(n)) {
return head(l);
} else {
return nth(tail(l), dec(n));
}
};
```

Under the hood there are really *two* lists getting things popped off as we
iterate, because `n`

is a number, which is a list, and `dec`

pops things off.
But it's much easier to read when we've abstracted away the representation of
numbers, don't you think?

### drop, take

Two handy functions for working with lists are `drop`

and `take`

.

`drop(l, three)`

will return the list with the first three elements removed.

`take(l, three)`

will return the list containing only the first three elements.

```
var drop = function(l, n) {
if (is_zero(n)) {
return l;
} else {
return drop(tail(l), dec(n));
}
};
var take = function(l, n) {
if (is_zero(n)) {
return empty_list;
} else {
return prepend(head(l), take(tail(l), dec(n)));
}
};
```

### slice

Slicing a list is easy now that we have `drop`

, `take`

, and the ability to
subtract numbers:

```
var slice = function(l, start, end) {
return take(drop(l, start), sub(end, start));
};
```

First we drop up to the start, then take enough to get us to the end.

### length

We can define `length`

recursively like everything else:

```
var length = function(l) {
if (is_empty(l)) {
return zero;
} else {
return inc(length(tail(l)));
}
};
```

The length of the empty list is zero, and the length of any non-empty list is one plus the length of its tail.

If your mind isn't in knots by this point, consider the following:

- Lists are made of functions.
- Numbers are made of lists whose length represents the number.
`length`

is a function that takes a list (which is a function) and returns the length as a number (a list whose length represents the number).- We only just now got around to defining
`length`

even though we've been using numbers (which use the*length*of a list to represent a number) for a while now!

Are you dizzy yet? If not:

```
var mylist = prepend(empty_list,
prepend(empty_list,
empty_list));
var mylistlength = length(mylist);
```

`mylist`

is a list of two empty lists.

`mylistlength`

is the length of `mylist`

...

which is "two"...

which is represented by a list of two empty lists...

which is `mylist`

itself!

## Conclusion

If you liked this twisty little story, I highly recommend you check out The Little Schemer. It was one of the first books that really changed how I thought about programming. Don't be put off by the fact that it uses Scheme -- the language doesn't really matter.

I've also created a gist with all the code. Feel free to fork it and use it for practice.

You could add some more utility functions for practice writing recursively:

`append`

to add an item to the end of a list.`concat`

to concatenate two lists.`min`

and`max`

which take two numbers and return the minimum/maximum one.`remove`

, which is like filter except it only leaves the elements that return`false`

for the predicate.`contains_number`

, which checks if a specific number is inside a list of numbers.

Or if you want something more challenging, try implementing bigger concepts on top of the current ones:

- Negative numbers.
- Non-negative rational numbers.
- Negative rational numbers.
- Association lists (a data structure that associates keys with values).

Remember: the point is not to create something that runs well on a physical computer. Instead of thinking about how to make a particular combination of transistors and circuits have the right voltages, think about "computing" in the beautiful, perfect, abstract sense.