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 =lambdan: (1 color="#804040">ifn<2 color="#804040">elsen*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 =lambdaf: color="#804040">lambdan: (1 color="#804040">ifn<2 color="#804040">elsen*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 =lambdaf: ( color="#804040">lambdax: x(x))( color="#804040">lambday: f( color="#804040">lambdaz: 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 =lambdaf: ( color="#804040">lambdax: x(x))( color="#804040">lambday: f( color="#804040">lambdaz: y(y)(z)))

>>> fac = color="#804040">lambdaf: color="#804040">lambdan: (1 color="#804040">ifn<2 color="#804040">elsen*f(n-1))

>>> [ Y(fac)(i) color="#804040">fori color="#804040">inrange(10) ]

[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

>>> fib = color="#804040">lambdaf: color="#804040">lambdan: 0 color="#804040">ifn == 0 color="#804040">else(1 color="#804040">ifn == 1 color="#804040">elsef(n-1) + f(n-2))

>>> [ Y(fib)(i) color="#804040">fori color="#804040">inrange(10) ]

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

>>>

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

- Paddy

One of the problems Y combinator solves is naming and assignment. You can compute recursive functions totally anonymously, like this:

ReplyDelete>>> ( lambda func:

... ( lambda f: func(lambda x: (f(f))(x)) ) ( lambda f: func(lambda x: (f(f))(x)) )

... ) (lambda f: lambda n: 1 if n < 2 else n*f(n-1)) (10)

3628800

Neat post! I tried to wrap my head around Y a year or so ago. Definitely a mind-expanding experience :)

Thanks Steven, you're encouraging!

ReplyDeleteOne of the things that motivated me at the start, was that most of the explanations were in Lispy languages like scheme. from the start, I wanted to see how to do it in Python as well as gain an insight into the maths of the Y combinator.

- Paddy.

After some deliberation, I decided to turn the above into a task for Rosetta Code

ReplyDeletehere: http://www.rosettacode.org/wiki/Y_combinator

- Paddy.