Y Combinator in Python

I've been thinking again, and it hurts (its a good hurt though).



Somehow I came across the term 'Y combinator' again and this time
followed it up. It seems that it is a way to create a function
 that adds recursion to functions that don't have recursion in
their definition.



I am still learning from mainly href="http://mvanier.livejournal.com/2897.html">this
explanation 'The Y Combinator (Slight Return)' by Mike Vanier. but I've
managed to follow some things.



Here is a definition of a factorial function in Python:

factorial = lambda n: (1  color="#804040">if n<2  color="#804040">else n*factorial(n-1))

it is easy to see that it is recursive as the lambda expression is
assigned to a name and the name, fibonacci, is used in the lambda
expression.

We can mechanically generate a related function by calling the recursed
call 'f' and by wrapping the expression in an outer lambda expression
of f:

fac = lambda f:  color="#804040">lambda n: (1  color="#804040">if n<2  color="#804040">else n*f(n-1))

Notice that fac is not a recursive function as fac is not called inside
its definition. The fac function does not, in itself, compute the
factirial, but wrapping it in the Y combinator function Y produces a
function that computes a factorial, i.e:

Y(fac)(i) == factorial(i)

 

I am not too clear on the whole derivation of Y but Y,is itself a non
recursive function and, in Python is given by:

Y = lambda f: ( color="#804040">lambda x: x(x))( color="#804040">lambda y: f( color="#804040">lambda z: y(y)(z)))

here follows my interactive session where I am using it to compute
factorials and fibonacci numbers by adding recursion to non-recursive
functions:

>>> Y = lambda f: ( color="#804040">lambda x: x(x))( color="#804040">lambda y: f( color="#804040">lambda z: y(y)(z)))
>>> fac =  color="#804040">lambda f:  color="#804040">lambda n: (1  color="#804040">if n<2  color="#804040">else n*f(n-1))
>>> [ Y(fac)(i)  color="#804040">for i  color="#804040">in range(10) ]
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
>>> fib =  color="#804040">lambda f:  color="#804040">lambda n: 0  color="#804040">if n == 0  color="#804040">else (1  color="#804040">if n == 1  color="#804040">else f(n-1) + f(n-2))
>>> [ Y(fib)(i)  color="#804040">for i  color="#804040">in range(10) ]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>>

I need to set this investigation aside, then come back to it.



- Paddy