## Y Combinator

The Y combinator is a higher-order function which takes a single argument, which is a *function* that **isn't** recursive and returns a version of the same *function* which **is** recursive.

If that is not enough to blow your mind, please: **What do you think recursion is?**

More generally, Y gives us a way to get recursion in a programming language that supports first-class functions but that doesn't have recursion built in.

## Introduction

This post will be a comprehensive walk through the Chapter 9 of the Little Schemer. The idea is to reproduce the discussion about recursive functions and move straight to the *Y combinator* definition. I will be using *Clojure* and borrowing some explanations from this amazing article.

## Part 1: Partial Functions and Unnatural Recursion

Partial functions have this strange property of being correct for **some** input values and to have no guarantee that it will produce the correct answer to other values.

For example the `looking`

function below:

```
(defn looking [a lat]
(keep-looking a (first lat) lat))
(defn keep-looking [val index coll]
(let [new-val (get coll (- index 1))]
(cond
(= new-val val)
true
(not (integer? new-val))
false
:else
(keep-looking val new-val coll))))
```

Give it a `:keyword`

and a `collection`

. The `looking`

function will get the first element of the collection and verify if it is equal to the `:keyword`

I passed. If true, returns true.

If false, use the first element of the collection to perform an `index`

lookup.

For example:

```
(def lat [6 2 4 :caviar 5 7 3])
(looking :caviar lat)
=> true
```

The path:

```
6th index --> 7th index --> 3rd index --> 4th index (which is my keyword)
```

However the following example do not have an answer:

```
(def lat3 [7 1 2 :caviar 5 6 3])
(looking :caviar lat3)
```

The path:

```
7th index --> 3rd index --> 2nd index --> 1st index --> 7th index ---> ...
```

There are many functions that present this behavior. We are going to use this kind of functions to develop the idea of the Y combinator below. Why? They appear when you have the huge constrain to not `define`

anything.

Think about it, if you understand recursion as the technique of defining some function f in terms of itself. Then, if you can't `define`

the name of the function in your programming language, it will be ""impossible"" to write a recursive call, right?

## Part 2: Let's get into it!

We are going to use the `length`

function below in order to build our way through the Y Combinator function.

```
(defn length [coll]
(if (empty? coll)
0
(inc (length (rest coll)))))
```

However, without the `define`

constructor we can't write the name `length`

inside the body of the function because there is no way to refer to the name of this function, it will be written as an anonymous function.

```
(fn [coll]
(if (empty? coll)
0
(inc (????? (rest coll)))))
```

We still cannot write a better function to replace `?????`

, however the function above is all useless? Actually, not.

The following call will produce the correct value:

```
((fn [coll]
(if (empty? coll)
0
(inc (??? (rest coll))))) ()) ; call with the empty list
;; => 0
```

**IF** we could `define`

the function above, we could called it `length-0`

because it correctly returns the length of the empty list. However, is also possible to use this new `length-0`

function to write a new version which returns the correct answer to a list with only **one** element.

```
(def length-0
(fn [coll]
(if (empty? coll)
0
(inc (????? (rest coll))))))
((fn [coll]
(if (empty? coll)
0
(inc (length-0 (rest coll))))) (list :A))
;; => 1
```

But, let's pretend we can't use `define`

here, so the last function will become (I am only doing a substitution of the `length-0`

function):

```
(fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc (????? (rest coll)))))
(rest coll)))))
```

Ok, let's pay attention to the function above.

It cannot only answer correctly the length of a list with a single item, it can answer correctly when the input is a list **UP to 1 element**, therefore the empty list will also return the correct value.

Now, let's take another step on that direction, let's build the function that will return correctly when the input is **UP to 2 elements**:

```
(fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc (????? (rest coll)))))
(rest coll)))))
(rest coll)))))
```

UP to 3 elements:

```
(fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc (????? (rest coll)))))
(rest coll)))))
(rest coll))))) (rest coll)))))
```

UP to 4 elements:

```
(fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc ((fn [coll]
(if (empty? coll)
0
(inc (????? (rest coll)))))
(rest coll)))))
(rest coll)))))
(rest coll)))))
(rest coll)))))
```

And now, Friedman asks you:

**Now, what do you think recursion is?**

and that is a tough question.

Looks like if you pile a lot of "incomplete" functions that **for some** primitive values it returns the correct answer, we can get along just fine.

Following this example, it looks like we could compute the length of any list if we knew beforehand the size of the list and we could pile the exact amount of *incomplete* functions ahead of time.

*Crazy.. if you knew the size, you could pile the exact same amount of stacks to compute the size recursively. How nice is that... o.O*

Let's organize the code above and abstract the `?????`

function from the implementation.

```
((fn [func-length]
(fn [coll]
(if (empty? coll)
0
(inc (func-length (rest coll))))))
?????)
```

Ok, the function above is important...It is another version of the `length-0`

function. The only difference here is that: **as I don't know the function ?????, it could be "anything", so I will abstract that out of my main function and receive it as an argument**

Something like this:

```
(main-function ?????) ;; got it?
```

Ok, the new versions of the length up to 2 and 3 elements will be:

```
;; length-1
((fn [func-length]
(fn [coll]
(if (empty? coll)
0
(inc (func-length (rest coll))))))
((fn [func2-length]
(fn [coll]
(if (empty? coll)
0
(inc (func2-length (rest coll))))))
?????))
;; length-2
((fn [func-length]
(fn [coll]
(if (empty? coll)
0
(inc (func-length (rest coll))))))
((fn [func2-length]
(fn [coll]
(if (empty? coll)
0
(inc (func2-length (rest coll))))))
((fn [func3-length]
(fn [coll]
(if (empty? coll)
0
(inc (func3-length (rest coll))))))
?????)))
;; length-3
((fn [func-length]
(fn [coll]
(if (empty? coll)
0
(inc (func-length (rest coll))))))
((fn [func2-length]
(fn [coll]
(if (empty? coll)
0
(inc (func2-length (rest coll))))))
((fn [func3-length]
(fn [coll]
(if (empty? coll)
0
(inc (func3-length (rest coll))))))
((fn [func4-length]
(fn [coll]
(if (empty? coll)
0
(inc (func4-length (rest coll))))))
?????))))
```

Let's try to remove all the repetition above, let's rewrite the `length-0`

:

```
((fn [mk-length]
(mk-length ?????))
(fn [length]
(fn [coll]
(if (empty? coll)
0
(inc (length (rest coll)))))))
```

Let's follow the calls of the function above in order to see how it works to compute the length of the EMPTY list.

```
;;; the first parenthesis has 2 main blocks:
;; the function - Let's call it func0
(fn [mk-length]
(mk-length ?????))
;; and the argument. Let's call it arg0
(fn [length]
(fn [coll]
(if (empty? coll)
0
(inc (length (rest coll))))))
;;; so the first call will be (func0 arg0)
;;; ok, now he will have the second level of calls
;; (arg0 ?????)
;; however, this level expand to another function like:
(fn [coll]
(if (empty? coll)
0
(inc (????? (rest coll)))))
;; behold.. this is our first version of `length-0`
```

Ok, take some time to process this new notation. It only gets worse.

Now, how can we write the `length-1`

and `length-2`

using the concise definition above?

```
;; length-1
(
;; func
(fn [mk-length]
(mk-length
(mk-length ?????)))
;; arg
(fn [length]
(fn [coll]
(if (empty? coll)
0
(inc (length (rest coll))))))
)
;; length-2
(
;; func
(fn [mk-length]
(mk-length
(mk-length
(mk-length ?????))))
;; arg
(fn [length]
(fn [coll]
(if (empty? coll)
0
(inc (length (rest coll))))))
)
```

Wait a second... what just happened? It looks like the amount of levels we need to build **DOES NOT DEPEND OF THE TASK AT HAND**. WoW.. we factor out the `length`

-specific portion of the code and we started to pile up some sort of stack of incomplete calls.

Up to this point, everything was fine. Now, the magic starts to kick-in. The problem at hand is that we don't know beforehand how many calls of `mk-length`

we will need to do when we receive any list to perform the `length`

operation.

If we choose a lower number of `mk-length`

to perform the `length`

task, we will receive an error because it will try to call the `?????`

function by passing the argument `(rest coll)`

but `?????`

does not exist. ... Friedman suggests... let's substitute the function `?????`

for another call of `mk-length`

... :X.... :X ... afterwards `mk-length`

creates another "stack of calls" to enable us to compute one extra element in the list.

Ok...

...

Now, the `length-0`

will become:

```
((fn [mk-length]
(mk-length mk-length))
(fn [length]
(fn [coll]
(if (empty? coll)
0
(inc (length (rest coll)))))))
```

So, if we apply `mk-length`

one time, we will have `length-1`

:

```
((fn [mk-length]
(mk-length mk-length))
(fn [mk-length]
(fn [coll]
(if (empty? coll)
0
(inc ((mk-length ?????)
(rest coll))))))
)
```

The above code is working equivalently to `length-1`

, but it will failed for a list with 2 elements. However, let's get wild. *keep passing mk-length to itself...*, you will create as many frames as you need...

```
(
;;; func0
(fn [mk-length]
(mk-length mk-length))
;;; arg0
(fn [mk-length]
(fn [coll]
(if (empty? coll)
0
(inc ((mk-length mk-length)
(rest coll))))))
)
```

Are you kidding me... there is a problem though. The second function, `arg0`

in the comments above, does not remember the function that actually computes the `length`

operation as we started.

So, let's get rid of the `(mk-length mk-length)`

call in there. Just add another layer of function call and abstract that away.

```
((fn [mk-length]
(mk-length mk-length))
(fn [mk-length]
((fn [length]
(fn [coll]
(if (empty? coll)
0
(inc (length (rest coll))))))
(mk-length mk-length))))
```

However, if you run the code above.. it will give you an `StackOverflow Error`

because you are applying `mk-length`

to itself indefinitely. What you need to do is a "lazy" call, only call it when needed. So you must wrap it under another function call layer.

```
((fn [mk-length]
(mk-length mk-length))
(fn [mk-length]
((fn [length]
(fn [coll]
(if (empty? coll)
0
(inc (length (rest coll))))))
(fn [x]
((mk-length mk-length) x)))))
```

Alright, the next step is just re-arranging the code to factor out the portion of the code that is related to the `length`

operation that we desire.

```
(;;func0
(fn [non-recursive-func]
((fn [mk-length]
(mk-length mk-length))
(fn [mk-length]
(non-recursive-func
(fn [x]
((mk-length mk-length) x))))))
;;; arg0
(fn [length]
(fn [coll]
(if (empty? coll)
0
(inc (length (rest coll)))))))
```

Congratulations... `func0`

above is the Y combinator function. It receives one function and return another function which is recursive.

Changing the name of the variables:

```
(def Y
(fn [non-recursive-func]
((fn [f] (f f))
(fn [f]
(non-recursive-func (fn [x] ((f f) x)))))))
```

This chapter of The Little Schemer could not have ended better:

Q: Do you now know why Y works?

A: Read this chapter just one more time and you will.