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

[Roshan Mathews]

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)))
print Y(lambda add, a, b:
            a if b == 0
        else add(a+1, b-1))(3, 4)
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.