高阶函数学习(JavaScript)

大家不要被这个名字诱惑，我讲的是javascript的高阶函数的概念，而不是说本教程为高阶教程。

最近研究SICP，对其中的高阶函数抽象有了一些体会，并用javascript中进行了一些实验，现在把这些实验分析一下，希望对大家有所帮助。

高阶函数思想由来已久，最早可能要追溯到可计算理论的初期，在lambda演算理论中就有了这个思想了。最早的实现可能算是lisp语言。可以说，这个运算模型跟图灵机的计算能力是相当的。只不过后来历史选择了冯诺依曼体系。而lambda只好作为一个虚拟的实现运行在具有同等计算能力的图灵机上。

更高层次的抽象

抽象具有层次，比如，将一个小的运算封装成一个函数，就是一层抽象，而在这个抽象的基础上，再进行一次抽象，即为高阶抽象。在lisp之类的函数编程语言中这个概念是比较基本的。而在其他的命令式编程语言，如C，java等中，提供的是模板或者接口这样的概念。

 

比如，我们每次需要计算一个数的立方数时，都需要写成x*x*x的形式，如果一个运算中有很多地方要用到立方这种运算的话，可能编码会非常麻烦，而且代码也不清晰，于是，我们可以将立方运算抽象成一个函数,这个函数接受一个输入，并返回这个输入的立方数。
比如：

function cube(x){return x*x*x;}

 

这样，我们就有了一个独立的模块，用以计算“立方”，并且通过扩展语言的原生语句，我们可以表达“立方”这个概念。这种抽象是容易理解的，像C，java等语言也提供此类的抽象。

下面再看一个例子：

我们先编写一个函数，这个函数的功能如下：

1. 输入一个范围[a,b]
2. 输出为这个范围中的数的和。

如输入[1,100]，输出5050.

这个函数通过递归的形式比较容易实现，如：

function intSum(a, b){
    function inc(x){ return x + 1; }
    function identity(x){ return x; }
   
    if(a > b){
        return 0;
    }else{
        return intSum( inc(a) , b) + identity(a);
    }
}

 

当然，其中的内部函数inc,identity实在太简单，完全可以忽略，但是考虑到后边要用到，就先写成这种形式。

这个函数可以很好的工作，但是，随着项目的增大，我们需要另外一个函数来计算某个范围内数的立方和。

1. 输入一个范围[a,b]
2. 输出为这个范围中的数的立方和

如输入[1,4]，输出100:1^3+2^3+3^3+4^3 = 1 + 8 + 27 + 64 = 100

这时候，我们同样可以用一个递归来实现这个函数：

function cubeSum(a, b){
    function inc(x){ return x + 1; }
    function cube(x){ return x * x * x; }
    if(a > b){
        return 0;
    }else{
        return cubeSum( inc(a) , b) + cube(a);
    }
}

 

 

随着项目的进一步增长，我们现在需要实现第三个函数，来对这样一个数列进行求和输入同样为[a,b]的一个范围，计算1/x*(x+2),且步长为4，这个数列的前n项的和有个性质，就是无限的接近pi/8这个数列当然是有用的，比如计算Pi值，我们给定一个比较大的范围如[1,10000]然后给这个值乘8，即可近似的计算出pi来。

我用mathematica 计算了一下，可以看出这个求和确实是极限于PI/8.

同样用递归可以实现这个函数：

function piSum(a, b){
    function piTerm(x){ return 1/((x+2)*x); }
    function piNext(x){ return x+4; }
   
    if(a > b){
        return 0;
    }else{
        return piSum( piNext(a) , b) + piTerm(a);
    }
}

 

 

现在，让我们比较一下这三个函数，很快我们就会发现，这三个函数太相似了,都是：

1. 比较范围的下标，如果a>b，返回0，否则，转2
2. 改变a的值，并对a作一定的运算，然后递归调用自身

可以写成下面的这种伪码形式：

function <funcName>(a, b){
    if(a > b){
        return 0;
    }else{
        return <funcName>(<next>(a), b) + <func>(a);
    }
}

 

其中，funcName为函数名，next为取下一个a的值(根据“步长”走一步)，func计算a。

我们很容易将这个代码翻译成javascript代码：

function sum(term, a, next, b){
    if(a > b){
        return 0;
    }else{
        return sum(term, next(a), next, b) + term(a);
    }
}

 

这时候，如果我们传递给sum这个函数两个额外的参数term,和next，我们就可以得到想要的结果.
现在，我们的求和函数就可以写成这种形式：

function intSum(a, b){
    function inc(x){return x + 1;}
    function identity(x){return x;}

    return sum(identity, a, inc, b);
}

 

同样，立方和的函数可以写成这样：

function cubeSum(a, b){
    function inc(x){return x + 1;}
    function cube(x){return x * x * x;}

    return sum(cube, a, inc, b);
}

 

最后一个

function piSum(a, b){
    function piTerm(x){ return 1/((x+2)*x); }
    function piNext(x){ return x+4; }

    return sum(piTerm, a, piNext, b);
}

 

可以看到，我们只需要传递给sum一个真正的计算算子和一个计算步长的算子就可以了。

现在给出一个简单的测试函数：

function sumTester(){
    print(intSum(1, 100));      //  should print 5050
    print(cubeSum(1, 4));       //  should print 100
    print(piSum(1, 10000)*8);   //  should print PI
} 

 

两者的运行结果都如下：

写道

js> sumTester()
5050
100
3.141392653591793

 

顺便说一下，这些例子均在rhino下测试，在浏览器中没有做过测试，如最后的测试函数中的print，估计浏览器中嵌入的js引擎不能正确解析。关于rhino，javaeye里有相关的文章，可以找找看。

使用高阶函数，我们可以在第一阶抽象的基础上再做一次抽象，生成一个函数的产生器，传递给一定的算子，即可完成各个相似的计算。

评论

5 楼 abruzzi 2009-12-15  

check 写道

既然讲这些，是不是应该至少加入curry/uncurry的内容？

curry不属于高阶函数吧？curry是函数式程序设计的一部分，但是高阶函数主要涉及对函数的多级抽象，curry则体现了“函数为一等公民”。

4 楼 check 2009-12-15  

既然讲这些，是不是应该至少加入curry/uncurry的内容？

3 楼 abruzzi 2009-12-14  

szcjlssx 写道

个人使用的真实感觉就是,当传递一个函数作为参数的时候,就像派了一个人去处理一样,顿时生动了,呵呵

不错，所以这个被作为参数使用的函数被叫做“算子”，即用以执行某项任务的计算单元。函数式编程的重点正在与此！

2 楼 szcjlssx 2009-12-14  

个人使用的真实感觉就是,当传递一个函数作为参数的时候,就像派了一个人去处理一样,顿时生动了,呵呵

1 楼 abruzzi 2009-04-17  

函数抽象成这个层次还是不够，比如要表达一个对象的概念。某对象上的某操作，如OO语言中的:

<code>object.method();</code>

这种情况，需要提供更高级的抽象方式，在函数式编程中，这个“高级”的过程是可以迭代的，所以，你可以通过函数进行任意层次的抽象。