JavaScript内核系列 第9章 函数式的Javascript

 

第九章 函数式的Javascript

要说JavaScript和其他较为常用的语言最大的不同是什么，那无疑就是JavaScript是函数式的语言，函数式语言的特点如下：

函数为第一等的元素，即人们常说的一等公民。就是说，在函数式编程中，函数是不依赖于其他对象而独立存在的(对比与Java，函数必须依赖对象，方法是对象的方法)。

函数可以保持自己内部的数据，函数的运算对外部无副作用(修改了外部的全局变量的状态等)，关于函数可以保持自己内部的数据这一特性，称之为闭包。我们可以来看一个简单的例子：

 

var outter = function(){
    var x = 0;
    return function(){
       return x++;
    }
}
 
var a = outter();
print(a());
print(a());
 
var b = outter();
print(b());
print(b());

 

运行结果为：

0
1
0
1

 

变量a通过闭包引用outter的一个内部变量，每次调用a()就会改变此内部变量，应该注意的是，当调用a时，函数outter已经返回了，但是内部变量x的值仍然被保持。而变量b也引用了outter，但是是一个不同的闭包，所以b开始引用的x值不会随着a()被调用而改变，两者有不同的实例，这就相当于面向对象中的不同实例拥有不同的私有属性，互不干涉。

由于JavaScript支持函数式编程，我们随后会发现JavaScript许多优美而强大的能力，这些能力得力于以下主题：匿名函数，高阶函数，闭包及柯里化等。熟悉命令式语言的开发人员可能对此感到陌生，但是使用lisp, scheme等函数式语言的开发人员则觉得非常亲切。

9.1匿名函数

匿名函数在函数式编程语言中，术语成为lambda表达式。顾名思义，匿名函数就是没有名字的函数，这个是与日常开发中使用的语言有很大不同的，比如在C/Java中，函数和方法必须有名字才可以被调用。在JavaScript中，函数可以没有名字，而且这一个特点有着非凡的意义：

 

function func(){
    //do something
}
 
var func = function(){
    //do something
}

 

这两个语句的意义是一样的，它们都表示，为全局对象添加一个属性func，属性func的值为一个函数对象，而这个函数对象是匿名的。匿名函数的用途非常广泛，在JavaScript代码中，我们经常可以看到这样的代码：

 

var mapped = [1, 2, 3, 4, 5].map(function(x){return x * 2});
print(mapped);

 

应该注意的是，map这个函数的参数是一个匿名函数，你不需要显式的声明一个函数，然后将其作为参数传入，你只需要临时声明一个匿名的函数，这个函数被使用之后就别释放了。在高阶函数这一节中更可以看到这一点。

9.2高阶函数

通常，以一个或多个函数为参数的函数称之为高阶函数。高阶函数在命令式编程语言中有对应的实现，比如C语言中的函数指针，Java中的匿名类等，但是这些实现相对于命令式编程语言的其他概念，显得更为复杂。

9.2.1 JavaScript中的高阶函数

         Lisp中，对列表有一个map操作，map接受一个函数作为参数，map对列表中的所有元素应用该函数，最后返回处理后的列表(有的实现则会修改原列表)，我们在这一小节中分别用JavaScript/C/Java来对map操作进行实现，并对这些实现方式进行对比：

 

Array.prototype.map = function(func /*, obj */){
    var len = this.length;
    //check the argument
    if(typeof func != "function"){
       throw new Error("argument should be a function!");
    }
   
    var res = [];
    var obj = arguments[1];
    for(var i = 0; i < len; i++){
       //func.call(), apply the func to this[i]
       res[i] = func.call(obj, this[i], i, this);
    }
   
    return res;
}

 

 

我们对JavaScript的原生对象Array的原型进行扩展，函数map接受一个函数作为参数，然后对数组的每一个元素都应用该函数，最后返回一个新的数组，而不影响原数组。由于map函数接受的是一个函数作为参数，因此map是一个高阶函数。我们进行测试如下：

 

function double(x){
    return x * 2;
}
 
[1, 2, 3, 4, 5].map(double);//return [2, 4, 6, 8, 10]

 

应该注意的是double是一个函数。根据上一节中提到的匿名函数，我们可以为map传递一个匿名函数：

 

var mapped = [1, 2, 3, 4, 5].map(function(x){return x * 2});
print(mapped);

 

这个示例的代码与上例的作用是一样的，不过我们不需要显式的定义一个double函数，只需要为map函数传递一个“可以将传入参数乘2并返回”的代码块即可。再来看一个例子：

 

[
    {id : "item1"},
    {id : "item2"},
    {id : "item3"}
].map(function(current){
    print(current.id);
});

将会打印：

 

item1
item2
item3

 

 

也就是说，这个map的作用是将传入的参数(处理器)应用在数组中的每个元素上，而不关注数组元素的数据类型，数组的长度，以及处理函数的具体内容。

9.2.2 C语言中的高阶函数

C语言中的函数指针，很容易实现一个高阶函数。我们还以map为例，说明在C语言中如何实现：

 

//prototype of function
void map(int* array, int length, int (*func)(int));

 

 

map函数的第三个参数为一个函数指针，接受一个整型的参数，返回一个整型参数，我们来看看其实现：

 

//implement of function map
void map(int* array, int length, int (*func)(int)){
    int i = 0;
    for(i = 0; i < length; i++){
       array[i] = func(array[i]);
    }
}

 

 

我们在这里实现两个小函数，分别计算传入参数的乘2的值，和乘3的值，然后进行测试：

 

int twice(int num) { return num * 2; }
int triple(int num){ return num * 3; }
 
//function main
int main(int argc, char** argv){
    int array[5] = {1, 2, 3, 4, 5};
    int i = 0;
    int len = 5;
 
    //print the orignal array
    printArray(array, len);
 
    //mapped by twice
    map(array, len, twice);
    printArray(array, len);
 
    //mapped by twice, then triple
    map(array, len, triple);
    printArray(array, len);
 
    return 0;
}

 

运行结果如下：

 

1 2 3 4 5
2 4 6 8 10
6 12 18 24 30

 

 

应该注意的是map的使用方法，如map(array, len, twice)中，最后的参数为twice，而twice为一个函数。因为C语言中，函数的定义不能嵌套，因此不能采用诸如JavaScript中的匿名函数那样的简洁写法。

         虽然在C语言中可以通过函数指针的方式来实现高阶函数，但是随着高阶函数的“阶”的增高，指针层次势必要跟着变得很复杂，那样会增加代码的复杂度，而且由于C语言是强类型的，因此在数据类型方面必然有很大的限制。

9.2.3 Java中的高阶函数

Java中的匿名类，事实上可以理解成一个教笨重的闭包(可执行单元)，我们可以通过Java的匿名类来实现上述的map操作，首先，我们需要一个对函数的抽象：

 

    interface Function{
       int execute(int x);
    }

 

我们假设Function接口中有一个方法execute，接受一个整型参数，返回一个整型参数，然后我们在类List中，实现map操作：

 

    private int[] array;
   
    public List(int[] array){
       this.array = array;
    }
   
    public void map(Function func){
       for(int i = 0, len = this.array.length; i < len; i++){
           this.array[i] = func.execute(this.array[i]); 
       }
    }

 

map接受一个实现了Function接口的类的实例，并调用这个对象上的execute方法来处理数组中的每一个元素。我们这里直接修改了私有成员array，而并没有创建一个新的数组。好了，我们来做个测试：

 

    public static void main(String[] args){
       List list = new List(new int[]{1, 2, 3, 4, 5});
       list.print();
       list.map(new Function(){
           public int execute(int x){
              return x * 2;
           }
       });
       list.print();
      
       list.map(new Function(){
           public int execute(int x){
              return x * 3;
           }
       });
       list.print();
    }

 

 

同前边的两个例子一样，这个程序会打印：

 

1 2 3 4 5
2 4 6 8 10
6 12 18 24 30

 

 

灰色背景色的部分即为创建一个匿名类，从而实现高阶函数。很明显，我们需要传递给map的是一个可以执行execute方法的代码。而由于Java是命令式的编程语言，函数并非第一位的，函数必须依赖于对象，附属于对象，因此我们不得不创建一个匿名类来包装这个execute方法。而在JavaScript中，我们只需要传递函数本身即可，这样完全合法，而且代码更容易被人理解。

 

 

9.3闭包与柯里化

闭包和柯里化都是JavaScript经常用到而且比较高级的技巧，所有的函数式编程语言都支持这两个概念，因此，我们想要充分发挥出JavaScript中的函数式编程特征，就需要深入的了解这两个概念，我们在第七章中详细的讨论了闭包及其特征，闭包事实上更是柯里化所不可缺少的基础。

9.3.1柯里化的概念

闭包的我们之前已经接触到，先说说柯里化。柯里化就是预先将函数的某些参数传入，得到一个简单的函数，但是预先传入的参数被保存在闭包中，因此会有一些奇特的特性。比如：

 

var adder = function(num){
    return function(y){
       return num + y;  
    }
}
 
var inc = adder(1);
var dec = adder(-1);

 

这里的inc/dec两个变量事实上是两个新的函数，可以通过括号来调用，比如下例中的用法：

 

//inc, dec现在是两个新的函数，作用是将传入的参数值(+/-)1
print(inc(99));//100
print(dec(101));//100
 
print(adder(100)(2));//102
print(adder(2)(100));//102

 

9.3.2柯里化的应用

根据柯里化的特性，我们可以写出更有意思的代码，比如在前端开发中经常会遇到这样的情况，当请求从服务端返回后，我们需要更新一些特定的页面元素，也就是局部刷新的概念。使用局部刷新非常简单，但是代码很容易写成一团乱麻。而如果使用柯里化，则可以很大程度上美化我们的代码，使之更容易维护。我们来看一个例子：

 

//update会返回一个函数，这个函数可以设置id属性为item的web元素的内容
function update(item){
    return function(text){
       $("div#"+item).html(text);
    }
}
 
//Ajax请求，当成功是调用参数callback
function refresh(url, callback){
    var params = {
       type : "echo",
       data : ""
    };
 
    $.ajax({
       type:"post",
       url:url,
       cache:false,
       async:true,
       dataType:"json",
       data:params,
      
       //当异步请求成功时调用
       success: function(data, status){
           callback(data);
       },
      
       //当请求出现错误时调用
       error: function(err){
           alert("error : "+err);
       }
    });
}
 
refresh("action.do?target=news", update("newsPanel"));
refresh("action.do?target=articles", update("articlePanel"));
refresh("action.do?target=pictures", update("picturePanel"));

 

 

其中，update函数即为柯里化的一个实例，它会返回一个函数，即：

 

update("newsPanel") = function(text){
    $("div#newsPanel").html(text);
}

由于update(“newsPanel”)的返回值为一个函数，需要的参数为一个字符串，因此在refresh的Ajax调用中，当success时，会给callback传入服务器端返回的数据信息，从而实现newsPanel面板的刷新，其他的文章面板articlePanel,图片面板picturePanel的刷新均采取这种方式，这样，代码的可读性，可维护性均得到了提高。

9.4一些例子

9.4.1函数式编程风格

通常来讲，函数式编程的谓词(关系运算符，如大于，小于，等于的判断等)，以及运算(如加减乘数等)都会以函数的形式出现，比如：

 

a > b

 

通常表示为：

 

gt(a, b)//great than

 

因此，可以首先对这些常见的操作进行一些包装，以便于我们的代码更具有“函数式”风格：

 

function abs(x){ return x>0?x:-x;}
function add(a, b){ return a+b; }
function sub(a, b){ return a-b; }
function mul(a, b){ return a*b; }
function div(a, b){ return a/b; }
function rem(a, b){ return a%b; }
function inc(x){ return x + 1; }
function dec(x){ return x - 1; }
function equal(a, b){ return a==b; }
function great(a, b){ return a>b; }
function less(a, b){ return a<b; }
function negative(x){ return x<0; }
function positive(x){ return x>0; }
function sin(x){ return Math.sin(x); }
function cos(x){ return Math.cos(x); }

 

如果我们之前的编码风格是这样：

// n*(n-1)*(n-2)*...*3*2*1
function factorial(n){
    if(n == 1){
        return 1;
    }else{
        return n * factorial(n - 1);
    }
}

 

 

在函数式风格下，就应该是这样了：

 

function factorial(n){
    if(equal(n, 1)){
        return 1;
    }else{
        return mul(n, factorial(dec(n)));
    }
}

 

函数式编程的特点当然不在于编码风格的转变，而是由更深层次的意义。比如，下面是另外一个版本的阶乘实现：

 

/*
 *  product <- counter * product
 *  counter <- counter + 1
 * */
 
function factorial(n){
    function fact_iter(product, counter, max){
        if(great(counter, max)){
            return product;
        }else{
            fact_iter(mul(counter, product), inc(counter), max);
        }
    }
 
    return fact_iter(1, 1, n);
}

 

 

虽然代码中已经没有诸如+/-/*//之类的操作符，也没有>,<,==,之类的谓词，但是，这个函数仍然算不上具有函数式编程风格，我们可以改进一下：

function factorial(n){
    return (function factiter(product, counter, max){
       if(great(counter, max)){
           return product;
       }else{
           return factiter(mul(counter, product), inc(counter), max);
       }
    })(1, 1, n);
}
 
factorial(10);

 

通过一个立即运行的函数factiter，将外部的n传递进去，并立即参与计算，最终返回运算结果。

9.4.2 Y-结合子

提到递归，函数式语言中还有一个很有意思的主题，即：如果一个函数是匿名函数，能不能进行递归操作呢？如何可以，怎么做？我们还是来看阶乘的例子：

 

function factorial(x){
    return x == 0 ? 1 : x * factorial(x-1);  
}

 

factorial函数中，如果x值为0，则返回1，否则递归调用factorial，参数为x减1，最后当x等于0时进行规约，最终得到函数值(事实上，命令式程序语言中的递归的概念最早即来源于函数式编程中)。现在考虑：将factorial定义为一个匿名函数，那么在函数内部，在代码x*factorial(x-1)的地方，这个factorial用什么来替代呢？

lambda演算的先驱们，天才的发明了一个神奇的函数，成为Y-结合子。使用Y-结合子，可以做到对匿名函数使用递归。关于Y-结合子的发现及推导过程的讨论已经超出了本部分的范围，有兴趣的读者可以参考附录中的资料。我们来看看这个神奇的Y-结合子：

 

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

 

我们来看看如何运用Y-结合子，依旧是阶乘这个例子：

 

var factorial = Y(function(func){
    return function(x){
       return x == 0 ? 1 : x * func(x-1);
    }
});
 
factorial(10);

 

或者：

 

Y(function(func){
    return function(x){
       return x == 0 ? 1 : x * func(x-1);
    }
})(10);

 

 

不要被上边提到的Y-结合子的表达式吓到，事实上，在JavaScript中，我们有一种简单的方法来实现Y-结合子：

 

    var fact = function(x){
       return x == 0 : 1 : x * arguments.callee(x-1);
    }
   
    fact(10);

 

或者：

 

    (function(x){
       return x == 0 ? 1 : x * arguments.callee(x-1);
    })(10);//3628800

 

其中，arguments.callee表示函数的调用者，因此省去了很多复杂的步骤。

9.4.3其他实例

下面的代码则颇有些“开发智力”之功效：

 

//函数的不动点
function fixedPoint(fx, first){
    var tolerance = 0.00001;
    function closeEnough(x, y){return less( abs( sub(x, y) ), tolerance)};
    function Try(guess){//try 是javascript中的关键字，因此这个函数名为大写
        var next = fx(guess);
        //print(next+" "+guess);
        if(closeEnough(guess, next)){
            return next;
        }else{
            return Try(next);
        }
    };
    return Try(first);
}

 

 

 

// 数层嵌套函数，
function sqrt(x){
    return fixedPoint(
        function(y){
            return function(a, b){ return div(add(a, b),2);}(y, div(x, y));
        },
        1.0);
}
 
print(sqrt(100));

 

 

fiexedPoint求函数的不动点，而sqrt计算数值的平方根。这些例子来源于《计算机程序的构造和解释》，其中列举了大量的计算实例，不过该书使用的是scheme语言，在本书中，例子均被翻译为JavaScript。

 

 附：由于作者本身水平有限，文中难免有纰漏错误等，或者语言本身有不妥当之处，欢迎及时 指正，提出建议，参与讨论，谢谢大家！

评论

5 楼 nature_park 2010-05-14  

楼主很厉害，看的很迷糊

4 楼 childrentown 2010-05-14  

内容很详实，没有白等，希望再接再厉。

3 楼 abruzzi 2010-05-14  

weiqingfei 写道

个人感觉，只要涉及到递归的地方，都尽量写成尾递归的形式比较好，容易养成良好的习惯。

嗯，如果递归层次深的话，不使用尾递归估计很快就抛掉了。

2 楼 weiqingfei 2010-05-14  

个人感觉，只要涉及到递归的地方，都尽量写成尾递归的形式比较好，容易养成良好的习惯。

1 楼 smithsun 2010-05-14  

哈，第九章终于出来了，不过内容看着很抽象啊。