Written by Pete Corey on Oct 30, 2017.

I’ve been re-reading one of my favorite programming books, The Little Schemer, and I had an epiphany in one of the final chapters.

Among many other mind-bending topics, the book goes through a derivation of the Y combinator. In the past, any technical explanations of the Y combinator have left me with a brain folded into a pretzel and a throbbing headache. This time, however, something clicked.

But with the help of the quirky guiding dialog of The Little Schemer, I feel like I finally understand the Y combinator.

I want to share that understanding with you, my Elixir-loving friend!

In this article we’ll briefly go over what exactly the Y combinator is, and then dive deep into how we can derive it using anonymous Elixir functions. This is definitely a brain-stretcher of an article, and I hope you find it as interesting as I do.

## But Why? (Pun Intended)

Why is it important that you know about the Y combinator? Honestly, unless you’re a professional computer scientist, it’s not. When it comes to day-to-day web development, the applicable benefits of knowing what the Y combinator is and how it works are practically nonexistent.

Putting practicality aside, the Y combinator is one of the most interesting objects in all of computer science.

In the most basic sense, the Y combinator allows computer scientists to define recursive functions in Lambda Calculus, a language that fundamentally doesn’t support recursion. The way in which it does this is one of the most clever and intricately beautiful solutions to any programming problem I’ve ever seen.

For me, the Y combinator is something like the Mandelbrot set, or Conway’s Game of Life. It’s something to be marveled at; something to be revered.

## Deriving An Example

Let’s start our dive into the world of the Y combinator by coming up with a recursive function we want to build *without using recursion*!

We’ll use a simple classic:

```
def length([]), do: 0
def length([h|t]), do: 1 + length(t)
```

Defined as an anonymous function, `length`

computes the length of a list:

```
length([]) # 0
length([1]) # 1
length([1, 1]) # 2, etc...
```

When `length`

is passed an empty list, we return a length of `0`

. When its passed a non-empty list, we return `1`

plus the `length`

of the tail of the list. We’re able to create this type of recursive definition because when defining functions using `def`

and `defp`

, Elixir is kind enough to allow the defined function to make direct references and calls to itself.

However, what if we were to try to write a recursive anonymous function?

```
length = fn
[] -> 0
[h|t] -> 1 + length.(t)
end
```

Here we’re binding `length`

to an anonymous function. Within that anonymous function we attempt to recurse by calling `length`

. Unfortunately, at this point `length`

is not in scope, and so Elixir blows up with a compilation error:

```
** (CompileError) iex:9: undefined function length/0
(stdlib) lists.erl:1354: :lists.mapfoldl/3
(stdlib) lists.erl:1355: :lists.mapfoldl/3
```

Is it possible to write a recursive anonymous function? Put another way, can you write a recursive function without being able to directly refer to yourself?

Yes! **Behold the power of the Y combinator!**

## Down the Rabit Hole

Before we start our deep dive, let’s pull back and simplify things a bit. While our recursive call to our anonymous `length`

function doesn’t work, part of our `length`

function is still correct.

Let’s pull out the recursive piece to highlight what we mean:

```
length = fn
[] -> 0
[h|t] -> 1 + (fn _ -> raise "oops" end).(t)
end
```

Even with the recursive piece removed, we’re able to calculate the length of empty lists:

```
length.([]) # 0
length.([1]) # oops
```

We could add support for lists of length `1`

by substituting the function that raises an exception (our “raising function”) with another identical copy of our `length`

function:

```
length = fn
[] -> 0
[h|t] -> 1 + (fn
[] -> 0
[h|t] -> 1 + (fn _ -> raise "oops" end).(t)
end).(t)
end
```

Now our function works for lists of length `0`

and `1`

, but blows up on lists two or more elements long:

```
length.([]) # 0
length.([1]) # 1
length.([1, 2]) # oops
```

We could add support for even longer lists by continuously replacing the raising function with additional copies of our `length`

function:

```
length = fn
[] -> 0
[h|t] -> 1 + (fn
[] -> 0
[h|t] -> 1 + (fn
[] -> 0
[h|t] -> 1 + (
...
).(t)
end).(t)
end).(t)
end
```

While this works, it’s obviously infeasible. If we wanted to calculate the length of a one thousand element list, we’d need to chain at least one thousand function definitions together.

Not only that, but we’ll always have an upper bound using this technique. At some point, our chain will end and our raising function will throw an exception.

We need to do better.

## Don’t Repeat Yourself

If you look at the code above, you’ll notice lots of repetition. At each level of “recursion” we define an anonymous function that looks very similar to our original `length`

function.

Every level is identical except for the function we’re calling into in the next level. Sometimes we call into another `length`

-like function, but at the very end we call into our raising function.

We can cut down on all that repeated code by writing a function that makes each level of this `length`

stack. Our `make_length`

function takes the bit that changes in each level, the next function to call into, as an argument:

```
make_length = fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end
```

Now we can use `make_length`

to write a `length`

function that works on empty lists:

```
make_length.(fn _ -> raise "oops" end)
```

And similarly, we can use `make_length`

to write a `length`

function that works on lists of length zero or one:

```
make_length.(make_length.(fn _ -> raise "oops" end))
```

This works because we create our zero-length function and pass it into `make_length`

, which wraps it in another application of our `length`

-like function.

We can even use Elixir pipes to make things a bit cleaner:

```
(fn _ -> raise "oops" end)
|> (make_length).()
|> (make_length).()
```

Without using the `make_length`

binding, we could define a totally anonymous version of `length`

that works on lists up to three elements long:

```
(fn
make_length ->
(fn _ -> raise "oops" end)
|> (make_length).() # support for length 1
|> (make_length).() # support for length 2
|> (make_length).() # support for length 3
end).(fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end)
```

Now we’re getting somewhere!

While we’ve managed to cut out most of the repetition of our original solution, we’re still facing the problem of being restricted to a finite number of recursions.

## Building the Road as we Go

In our current solution, we need to define, in advance, the maximum list length our anonymous `length`

function will support.

Every repeated application of `make_length`

adds another layer to our growing stack of functions. But if we’re passed a long enough list that chews through that stack, the raising function is called and our length calculation grinds to a screeching halt.

To solve the last piece of this puzzle, we need to think very carefully about what it is we’re doing…

Every time our `length`

-like function is called it decides whether or not it needs to recurse. If it does, it calls the `length`

function tied to its closure. If it doesn’t, it simply returns a value which trickles its way back up the call stack.

The danger is that the `length`

function might actually point to our raising function.

Instead of throwing an exception when we hit that last function in the stack, we’d really like to add another layer of our `length`

-like function and call that instead. Really, we only ever need two functions in our stack. The current function, and the next function we want to call into.

Each layer of our `length`

-like function is created by passing `make_length`

into `make_length`

. Let’s simplify our stack creation by pulling out our raising function and simply returning the next layer of our `length`

-like function:

```
(fn
make_length ->
make_length.(make_length) # Add another layer
end).(fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end)
```

At this point we could even rename the `length`

argument in our second anonymous function to `make_length`

to remind ourselves of what’s not being passed into it.

```
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length -> # We're being passed make_length
fn
[] -> 0
[h|t] -> 1 + make_length.(t)
end
end)
```

But there’s a problem here.

Now we’re trying to pass the tail of our list (`t`

) into `make_length`

. This doesn’t make much sense. The `make_length`

function *expects a function* as an argument, and *returns a function* that accepts a list.

What could we pass into `make_length`

to build the next layer of our recursion? Take a minute, and remember that at this point `make_length`

represents the entirety of our second anonymous function:

```
(fn
make_length ->
fn
[] -> 0
[h|t] -> 1 + make_length.(t)
end
end)
```

Well, couldn’t we just pass `make_length`

into `make_length`

? Yes!

Passing `make_length`

into `make_length`

returns another layer of our `length`

-like function that accepts a list as an argument:

```
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length ->
fn
[] -> 0
[h|t] -> 1 + (make_length.(make_length)).(t)
end
end)
```

This new layer of our `length`

-like function still has access to `make_length`

, so if it decides to recurse, it has everything it needs to build and apply the next layer of `length`

. We don’t need to build our entire tower of `length`

functions up-front. We can construct each layer as we go!

Amazing… Does your brain hurt yet?

Each generation would be both content and vessel, an echo in a self-sustaining reverberation.
— Ted Chiang in Stories of Your Life and Others

## Reclaiming Our Length Function

As it stands now, our solution is fully functional. We can calculate the length of any list, no matter its size:

```
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length ->
fn
[] -> 0
[h|t] -> 1 + (make_length.(make_length)).(t)
end
end).([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...])
```

The only problem with this solution is that we’ve lost sight of the structure and shape of our original function:

```
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
```

Instead, we’ve had to modify that function to include strange implementation-specific calls to `make_length`

:

```
fn
[] -> 0
[h|t] -> 1 + (make_length.(make_length)).(t)
end
```

If we could reclaim the original shape of our `length`

function, we could theoretically factor it out and create a generic utility that could be used to make *any* function recursive without modification.

The first step towards our goal is refactoring the code that makes our next application of `length`

(`(make_length.(make_length)))`

into a function of its own:

```
fn
t ->
(make_length.(make_length)).(t)
end
```

This function accepts `t`

(the tail of our list) as an argument and applies `t`

to the next layer of `length`

after it’s been created.

The result of this function is actually `length`

! We can write another closure that accepts `length`

as an argument and pass this new function into it. The result is slightly longer, but we’ve managed to reclaim the structure of our original `length`

function:

```
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length ->
(fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end).(fn
t ->
(make_length.(make_length)).(t)
end)
end)
```

Our reclaimed `length`

function doesn’t make any references to `make_length`

, so we’re free to untangle it from this rat’s nest of anonymous functions.

Let’s wrap the entire block in one more closure that accepts our `length`

function as a parameter:

```
(fn
length ->
(fn
make_length ->
make_length.(make_length)
end).(fn
make_length ->
length.(fn
t ->
(make_length.(make_length)).(t)
end)
end)
end).(fn
length ->
fn
[] -> 0
[h|t] -> 1 + length.(t)
end
end)
```

With `length`

factored out, let’s refactor the meat of our solution to use slightly more traditional, albeit significantly less readable argument names:

```
y = fn
f ->
(fn
x ->
x.(x)
end).(fn
x ->
f.(fn
t ->
(x.(x)).(t)
end)
end)
end
```

What’s especially amazing is that we can use this helper function, `y`

, to make any function recursive! Here’s a recursive function that calculates the Nth number in the Fibonacci series:

```
y.(fn
fib ->
fn
0 -> 0
1 -> 1
n -> fib.(n-1) + fib.(n - 2)
end
end)
```

As you may have guessed, this *thing* that we’ve come up with has a name. **It’s the Y combinator!** It’s my opinion that the Y combinator is one of the most beautiful structures in all of computer science.

## Final Thoughts and More Resources

I hope this article helped you understand the Y combinator in all of its recursive, fractal glory.

To be honest, I still find the Y combinator to be a difficult thing to understand. I understand each step of the derivation, but when confronted with the Y combinator in its condensed, Lambda Calculus form, I find myself unable to succinctly sum up what it does in plain English:

λf. (λx. f (x x))(λx. f (x x))

It’s all Greek to me.

If you need more help wrapping your brain around this slippery idea, I highly recommend you check out The Little Schemer by Daniel P. Friedman and Matthias Felleisen. This book opened my eyes to the beauty of the Y combinator and many other equally mind-blowing topics. Highly recommended.

If books aren’t your thing, check out this gentle introduction to the Y combinator on Computerphile, or read through this in-depth article to deepen your understanding.