匿名递归

不动点组合子,f(fix(f)) = fix(f).
// 无类型 λ 演算,只有一种"类型",那就是单参函数。
// Lambda 演算可以被称为最小的通用程序设计语言。
柯里化(Currying)
转化和计算部分分离
function fact(n) {
return [1][n] || n * fact(n - 1);
}
var factgen = function(fact) {
return function(n) {
return (n === 0) ? 1 : n * fact(n-1); // calls argument, not self
};
};
// y 不动点组合子 Y是怎么通过 λ 演算找到的
var Y = function(proc) {
return (function(x) {
return proc(function(y) { return (x(x))(y);});
})(function(x) {
return proc(function(y) { return (x(x))(y);});
});
};
// or
var Y = function(proc) {
return (function(f) {
return f(f);
})(function(f) {
return proc(
function(x) { return (f(f))(x); }
);
});
}
console.log(Y(factgen)(6));
//===================
fn(Y(fn)) = Y(fn) // 返回一个以x为参数的函数
//===============
var Y = function(fn) {
return (function(f) {
return f(f);
})(function(f) {
return fn(
function(x) { return (f(f))(x); }
);
});
}
// ==>
Y(fn) = f(f);
// 其中
f = function(f) {
return fn(
function(x) { return (f(f))(x); }
);
};
//==>
Y(fn) = fn(
function(x) { return (f(f))(x); }
);
//==>
Y(fn) = fn(function(x) { return (Y(fn))(x));
//以数学等式表示?:
Y(fn) = fn(Y(fn));
//===================
Memoizing Fixed-point combinator
尾递归