y combinator simple derivation in javascript & python

y-combinator.js

// Y combinator：http://yaodanzhang.com/blog/2015/06/11/functional-programming-fundamental-y-combinator/
// lambda 演算：http://liujiacai.net/blog/2014/10/12/lambda-calculus-introduction/
// Jim Weirich: Adventures in Functional Programming：https://vimeo.com/45140590

// original recursive function

var factorial = function (n) {
    return n == 1 ? 1 : n * factorial(n - 1);
};

console.log(factorial(5));  // 120

// invoke self

var factorial = function (f, n) {
    return n == 1 ? 1 : n * factorial(f, n - 1);
};

console.log(factorial(factorial, 5));  // 120

// currying

var factorial = function (f) {
    return function (n) {
        return n == 1 ? 1 : n * f(f)(n - 1);
    }
};

console.log(factorial(factorial)(5));  // 120

// self invoke

var self_invoke = function (f) {
    return f(f);
};

var factorial = self_invoke(function (f) {
    return function (n) {
        return n == 1 ? 1 : n * self_invoke(f)(n - 1);
    };
});

console.log(factorial(5)); // 120

// inline

var factorial = (function (self_invoke) {
    return self_invoke(function (f) {
        return function (n) {
            return n == 1 ? 1 : n * self_invoke(f)(n - 1);
        };
    });
})(function (f) {
    return f(f);
});

console.log(factorial(5)); // 120

// What do we get last?
// Can u believe it? What the fuck ...

console.log((function (self_invoke) {
    return self_invoke(function (f) {
        return function (n) {
            return n == 1 ? 1 : n * self_invoke(f)(n - 1);
        };
    });
})(function (f) {
    return f(f);
})(5));  // 120

/*
function (n) {
    return n == 1 ? 1 : n * self_invoke(f)(n - 1);
}

=>

(function (self) {
    return function (n) {
        return n == 1 ? 1 : n * self(n - 1);
    };
})(function (m) {
    return self_invoke(f)(m);
})
*/

console.log((function (self_invoke) {
    return self_invoke(function (f) {
        return (function (self) {
            return function (n) {
                return n == 1 ? 1 : n * self(n - 1);
            };
        })(function (m) {
            return self_invoke(f)(m);
        });
    });
})(function (f) {
    return f(f);
})(5));  // 120

// 传入参数抽象出来
/*
function (self) {
    return function (n) {
        return n == 1 ? 1 : n * self(n - 1);
    };
}
 */

// y combinator
var y = function(r){
    return (function (self_invoke) {
        return self_invoke(function (f) {
            return r(function (m) {
                return self_invoke(f)(m);
            });
        });
    })(function (f) {
        return f(f);
    });
};

var f = function (self) {
    return function (n) {
        return n == 1 ? 1 : n * self(n - 1);
    };
};

console.log(y(f)(5));

// simplify the y combinator
// replace self_invoke as inline anonymous function

var y = function (r) {
    return (function (f) {
        return f(f);
    })(function (f) {
        return r(function (m) {
            return f(f)(m);
        });
    });
};

var f = function (self) {
    return function (n) {
        return n == 1 ? 1 : n * self(n - 1);
    };
};

console.log(y(f)(5));

y-combinator.py

#!/usr/bin/env python2.7
# encoding: utf-8

# tail recursion
def factorial(n):
    def _f(n, s):
        return s if n == 1 else _f(n-1, s*n)
    return _f(n, 1)

print factorial(5)

# 1

def factorial(n):
    return 1 if n == 1 else n * factorial(n-1)

print factorial(5)

# add self

def factorial(f, n):
    return 1 if n == 1 else n * factorial(f, n-1)

print factorial(factorial, 5)

# currying

def factorial(f):
    def inner(n):
        return 1 if n == 1 else n * factorial(f)(n-1)
    return inner

print factorial(factorial)(5)

# self_invoke

def factorial(n):
    def _f3(self_invoke=lambda f: f(f)):
        def _f2(f):
            def _f1(n):
                return 1 if n == 1 else n * self_invoke(f)(n-1)
            return _f1
        return self_invoke(_f2)
    return _f3()(n)

print factorial(5)


# add self
def factorial(n):
    self_invoke = lambda f: f(f)
    def _f3(f):
        def _f2(self):
            def _f1(n):
                return 1 if n == 1 else n * self(n-1)
            return _f1
        return _f2(lambda m: self_invoke(f)(m))
    return self_invoke(_f3)(n)

print factorial(5)


# inline
def factorial(n):
    def _f3(f):
        def _f2(self):
            def _f1(n):
                return 1 if n == 1 else n * self(n-1)
            return _f1
        return _f2(lambda m: (lambda g: g(g))(f)(m))
    return (lambda g: g(g))(_f3)(n)

print factorial(5)


# extract
factorial = lambda self: lambda n: (1 if n == 1 else n * self(n - 1))
Y = lambda r: (lambda g: g(g))(lambda f: r(lambda m: (lambda g: g(g))(f)(m)))

print Y(factorial)(5)

# brief
Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
fac = lambda f: lambda n: (1 if n<2 else n*f(n-1))
print Y(fac)(5)