# Y Combinator

I've been reading "The Little Schemer" from Daniel P. Friedman and Matthias Felleisen. Very interesting reading.

The nineth chapter introduces the Y Combinator function, a pretty interesting beast! Quoting Crockford: "one of the most strange and wonderful artifacts of Computer Science". As a primer, here's how the Y Combinator looks like (in Python):

```def Y(func):
return (lambda f : f(f))(lambda f : func(lambda x : (f(f))(x)))
```

Looks scary, doesn't it? (It did scare me when I first saw it at least.)

The Y Combinator creates a recursive function from a non-recursive function that looks like the recursive function one wants to create. The Y Combinator can for example be used to obtain recursive functions from anonymous functions, which, with most programming languages, cannot be recursive.

This blog post proposes defining the Y Combinator function in Python.

Goal: find the function Y (the Y Combinator) such that:

```fact = Y(like_fact)
```

where:

• fact is the factorial function
• like_fact is defined as follows:
```def like_fact(r):
def f(n):
if n < 2:
return 1
else:
return n * r(n - 1)
return f
```

So Y takes a non-recursive function (which can theoritically be expressed as an anonymous function) that looks like the recursive factorial function and returns the factorial function.

You may have noticed thay our like_fact function is not expresed as an anonymous function. This is because Python does not allow us to do it: the inner function f cannot be defined with lambda because it includes conditional statements, the outer function like_fact cannot be defined with lambda because it includes an inner function that isn't defined with lambda.

Using JavaScript the like_fact function would be:

```function(r) {
return function(n) {
return n < 2 ? 1 : n * r(n - 1);
};
}
```

We start our demonstration from the following statement:

```fact = notlike_fact(notlike_fact)
```

where notlike_fact is:

```def notlike_fact(r):
def f(n):
if n < 2:
return 1
else:
return n * (r(r))(n - 1)
return f
```

Now we rewrite the above statement using lambda:

```fact = (lambda f : f(f))(notlike_fact)
```

Now we can extract like_fact and rewrite the statement as (maybe the most difficult step):

```(lambda f : f(f)) (lambda f : like_fact(lambda x : (f(f)(x)))
```

We can now write the Y function:

```def Y(func):
return (lambda f : f(f))(lambda f : func(lambda x : (f(f))(x)))
```

And we have:

```fact = Y(like_fact)
assert fact(1) == 1
assert fact(2) == 2
assert fact(3) == 6
assert fact(4) == 24
assert fact(5) == 120
```

Cool, no?

Obviously Y applies to other recursive functions, as an example let's apply it to Fibonacci:

```def like_fibo(r):
def f(n):
if n <= 2:
return 1
else:
return r(n - 1) + r(n - 2)
return f

fibo = Y(like_fibo)
assert fibo(1) == 1
assert fibo(2) == 1
assert fibo(3) == 2
assert fibo(4) == 3
assert fibo(5) == 5
assert fibo(6) == 8
```