Church计数和Lambda演算——不用“数”的自然数运算

试发一篇——

我们讨论一个语言的“原生态”的时候,喜欢去掉一切不相关和非必要的特性,追求一个轻的、朴素的核心,而搞数学的家伙更是乐于把不要的东西全全都去掉,这不,Church计数告诉我们,如何完全不使用“数“来进行自然数的定义与演算

var zero = function(f) {
    return function(x) {return x};
}

var one = function(f) {
    return function(x) {return f(x)};
}

var two = function(f) {
    return function(x) {return f(f(x))};
}

var add = function(n, m) {
    return function(f) {
        return function(x) {
            return n(f)(m(f)(x));
        }
    }
}

如果要翻译回普通“自然数”,可以用下面的

var inc = function(x) {
    return x ? ++x: 1;
}
alert(add(two, add(two, one))(inc)());

在这里,发现想用JavaScript“玩转”FP还是有很多不够优美的地方,事实上使用Scheme也许是更好的选择。在SICP的第二章里详细提到了Church计数,并且有相关的习题(习题2.6),具体内容可以参考

http://shellex.info/church-nurmal-and-lambda-calculus/

This entry was posted in 中文 and tagged , , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>