# [BangPypers] Introducing the Y Combinator(Not the company)

Roshan Mathews rmathews at gmail.com
Thu Oct 15 20:55:51 CEST 2009

```On Thu, Oct 15, 2009 at 9:28 PM, Sidharth Kuruvila
<sidharth.kuruvila at gmail.com> wrote:
> AKA The Y Combinator in python. This is in response to Roshan Mathews'
> post that he got stuck with the Y Combinator.
>
Thanks, Sidharth, that was very interesting.  Can't say that
it has settled into my head, but the basic idea of passing
to the function Y a function F will return a function F'
that will have F' itself passed to itself as it's first
argument on subsequent calls, is a little less unclear.  The
last sentence barely makes sense to me. :-/

Anyways, in

square = ((lambda f: lambda g: f(g))
(lambda x: x*x))
print square(3)

we define a lambda (the one that takes f as argument) and
apply it to a value (the second lambda that takes x as
argument).  This clears up the meaning (syntax wise) of Y as
defined by you:

def Y(f):
return ((lambda g: lambda a: f(g(g), a))
(lambda g: lambda a: f(g(g), a)))
print Y(lambda factorial, a:
1 if a == 1
else a * factorial(a-1))(5)
print Y(lambda length, list:
0 if list == []
else (1+length(list[1:])))(range(5))
print Y(lambda fibonacci, n:
n if n < 2
else (fib(n-1) + fib(n-2)))(5)

factorial, length, fibonacci are magicaly filled in.

if we tweak Y just a tiny bit:

def Y(f):
return ((lambda g: lambda *a: f(g(g), *a))
(lambda g: lambda *a: f(g(g), *a)))
a if b == 0
print Y(lambda expt, a, b:
1 if b == 0
else (a * expt(a, b-1)))(3, 4)

we now get multi arg lambdas which are self aware!  Neat.
Do I understand it?  I'm not sure, maybe I'll know when I
think about it some more.  But thanks for the write-up, I'll
re-read chapter 9* of The Little Schemer again.

Roshan Mathews

* - available at
http://www.ccs.neu.edu/home/matthias/BTLS/sample.ps
(page "160", 13 of 26) is where the madness starts.
```