JavsScript中的函数式编程

在这篇文章中,我会简单介绍JavaScript中的函数式编程,包括递归的概念、map/reduce/filter函数、Currying以及流的应用。

当初Brendan Eich在设计JavaScript的时候实际上借鉴了Scheme对函数的处理,给予函数以first order的地位,也就是函数和其他类型的值一样,可以被赋予给变量,也以作为返回值,或作为参数传给函数。正是这样的设计,给JavaScript带来了强大的表达能力。

一、递归

递归是函数式编程的常用范式,也是核心思想之一。在ES6之前,各家JavaScript解释器并没有尾递归优化,因而当函数的调用栈增长超过一定数量后程序便会崩溃,然而在ES6标准中,为JavaScript加入了尾递归优化,同时V8等运行时环境也进行了实现。

顺带解释一下尾递归和尾递归优化。我们知道函数的调用实际上是对函数栈的操作,每次调用函数都会把函数及上下文作为一个帧压入栈中。尾递归则是指函数返回之前的最后一个操作是递归调用,也就是调用自己,而除了调用自己没有别的操作。所谓尾递归优化是指,编译器或解释器会把尾递归的函数调用直接在当前帧的位置进行运算,而不会创建新的帧并压入栈。

以fact函数为例,第一个中返回了n * fact(n-1)不是尾递归,而第二个返回了tail_fact(n-1, n*acc)则是尾递归。

var fact = function(n) {
    if (n <= 1) {
        return 1;
    }
    return n * fact(n-1);
};

var tail_fact = function(n, acc) {
    if (n == 0) {     
        return 1;
    } else if (n == 1) {
        return acc;
    }   
    return tail_fact(n-1, n*acc);
};

通过使用递归,我们可以完全等价地实现迭代的功能。例如检查一个元素是否在列表中:

var member = function(x, list) {
    if (list.length === 0) return false;
    if (x === list.shift()) return true;
    return member(x, list);
};

二、Map/Reduce/Filter

2.1 Map

Map用于对数组中的每一个元素应用传入的函数,并将结果作为一个新的数组返回。我第一次接触Map函数是在Pike语言中,当时在一家移动互联网领域的初创公司实习,公司的服务器端是使用Pike写的,想起来那时我对函数式编程还一无所知呢。

先来看看Map函数的递归实现:

var map = function(fn, xs) {
    if (xs.length === 0)
        return []; 
    return [fn(xs.shift())].concat(map(fn, xs));
};

上面的代码中shift()函数的作用是把数组中的第一个元素从数组中移除,并作为值返回。concat()函数则作用是把两个数组连接起来。

我们这里的Map函数接受两个参数,第一个是一个函数fn,第二个是要被处理的数组。其中fn是一个接受一个参数的函数。Map内部首先对当前传入的数组xs的长度进行判断,如果为0则是已经处理完数组中所有元素的情况,返回空数组;否则对数组的第一个元素应用fn,并对剩下的元素进行map,最后连接成一个数组返回。

例如我们想对数组中的每一个元素加一:

var res = map(function(x) {
    return x+1;
}, [1, 2, 3, 4, 5, 6]);
console.log(res); // [2, 3, 4, 5, 6, 7]

我们可以看到使用Map函数最大的好处是处理数组时基本不需要写for这样的循环语句了。

上面的递归实现十分简洁明了,但是因为JavaScript中对函数栈深度的限制,ECMA标准中的推荐实现实际上是基于迭代的,在生产环境中也可以放心使用。

Array.prototype.map = function(fun) {
    if (this === void 0 || this === null)
        throw new TypeError();

    var t = Object(this);
    var len = t.length >>> 0;
    if (typeof fun !== "function")
        throw new TypeError();

    var res = new Array(len);
    var thisArg = arguments.length >= 2 ? arguments[1] : void 0;
    for (var i = 0; i < len; i++) {
        if (i in t)
            res[i] = fun.call(thisArg, t[i], i, t); 
    }   
    return res;
};

// Use the build-in map
var res = [1, 2, 3, 4, 5].map(function(x) {
    return x+1;
};

关键的代码其实就是那5行for循环。

2.2 Reduce

Reduce在其他函数式语言中又被称作fold,

基于递归的实现如下:

var reduce = function(f, xs, acc) {
    if (acc === void 0)
        acc = 0;
    if (xs.length === 0)
        return acc;
    return reduce(f, xs.slice(1), f(acc, xs.shift()));
};

类似Map,ECMA的推荐实现并没有使用递归,可以在Mozilla的参考页面看到详细实现。

基于reduce我们可以做很多事情,后面的pipeline也使用到了reduce。

例如对整个数组进行求和:

var res = reduce(function(x, y) {
    return x+y;
}, [1, 2, 3, 4, 5], 0);

在上面的代码中我们并没有给出初始的acc值,在reduce内部会默认作为0处理。

通过给定初始的acc值,也可以用来判断是不是数组中的所有的元素都大于0:

var res = reduce(function(x, y) {
    return x && y>= 0;
}, [1, -2, 3, -4, 5], true);

更一般的,在reduce的基础上我们可以编写一个函数,来判断数组中的所有元素是否符合某个条件:

var checkArray = function(g, xs) {
    return reduce(function(x, y) {
        return x && g(y);
    }, xs, true);
};

例如判断数组中的所有字符串的长度是否均小于等于5:

var t = checkArray(function(x) {
    return x.length <= 5;
}, ['hello', 'javascript']); // false

我们再来看一下基于Reduce如何统计数组中元素在某个范围内的数量:

var numberInRange = function(xs, low, high) {
    return reduce(function(x, y) {
        if (y >= low && y <= high) {
            return x + 1;
        }
        return x;
    }, xs);
};

console.log(numberInRange([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3, 8)); // 6

2.3 Filter

Filter顾名思义就是对数组中的元素进行过滤,留下符合条件的元素组成新数组返回。

递归实现如下:

var filter = function(fn, xs) {
    if (xs.length === 0)
        return []; 
    if (fn(x = xs.shift()))
        return [x].concat(filter(fn, xs));
    return filter(fn, xs);
}

Filter对数组中每一个元素使用fn进行判断,只有判断结果为true的元素才会保留下来。
过滤出数组中的偶数:

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
res = myfilter(function(x) {
    return x%2===0;
}, arr);
console.log(res); // [2, 4, 6, 8, 10]

通过对Map/Reduce/Filter的使用,我们基本上可以避免使用迭代循环语句,而且由于High Order Function的特性,可以把怎么做做什么相分离,在map/reduce/filter中描述做什么,在所传入的函数中描述怎么做,代码更加简洁。

三、Currying

作为一门十分不纯的函数式语言,JavaScript并没有直接支持Curry化的方法,所以我们需要自己来编写Curry化的代码。

Function.prototype.curry = function() {
    var slice = Array.prototype.slice,
        args = slice.apply(arguments),
        that = this;
    return function() {
        return that.apply(null, args.concat(slice.apply(arguments)));
    }; 
};

四、Stream

五、Pipeline

六、Memoization