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
. Anyway I thought an answer to that question could make a post on my blog. There it is.