## Preface

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

**recursive.**

**is**
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)

Will result into a infinite sequence of calls…

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 **element.**

**one**(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:

– FriedmanNow, 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 works?

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