JavaScript高阶函数进阶：从递归消除循环到链表实现

前言

在前文《JavaScript典型高阶函数应用》中，我们实现了几个典型的高阶函数。文章末尾曾提出一个疑问：为何这些实现与F#等纯函数式语言的风格存在差异？本文将尝试探索一种更具“函数式”特征的实现方式。

递归消除循环的实现

我们对之前的函数实现进行了调整，核心目标是移除显式的for循环。为了实现这一点，首先需要引入集合的归纳法定义概念。

根据归纳法定义，一个集合要么是空集，要么是由一个元素与另一个集合组成的数对。从这一定义可以看出，任何集合都可以被视为一个元素与剩余集合的配对。例如，集合{1,2,4,5}可以表示为元素1与集合{2,4,5}的配对，记作(1, {2,4,5})。递归地看，{2,4,5}又可表示为(2, {4,5})，最终归结为(5, Ø)。基于这种理解，我们可以通过递归方法消除循环，因为在分解过程中已经访问了每个数据项，且终止条件为空集。以下展示了filter函数的另一种实现，原函数名添加前缀f以作区分：

 
function ffilter(arr,callback){
var i=arguments[2] || 0,
out = arguments[3] || [];
if(!arr[i]) return arguments[3];
if(callback(arr[i]))
out.push(arr[i]);
return arguments.callee(arr,callback,++i,out);
} 

测试用例如下：

 
var arr = [1,2,3,4,5,6,7,8,9,10];
var even = function(item){
if(typeof item !== "number") return false;
return !(item & 1);
}; 
console.log(ffilter(arr,even));

运行结果：

[2, 4, 6, 8, 10] 这种消除循环后的实现更贴近数学的归纳定义，显得更为自然。同样地，我们来看ffold函数的实现：

 
var arr = [1,2,3,4,5,6,7,8,9,10];
var plus = function(a,b){
return a+b;
}; 
console.log(ffold(arr,plus,3));

输出结果：

58

其他函数也可采用相同的方法进行改造。这样的实现方式让人感觉更加Functional，但能否进一步贴近数学定义呢？我们将在后续尝试中解答。

==========2013.1.8 更新==================

链表与数学定义的极致接近

前文提到这些写法是否能与数学定义更加接近，下面尝试使用链表来实现。首先给出链表的定义：

 
var node = function(){
this.data = 0;
this.tail = null;
}; 

 
var n1 = new node(),n2 = new node(),n3 = new node(),n4 = new node(),n5 = new node();
n1.data=1,n1.tail=n2;
n2.data=2,n2.tail=n3;
n3.data=3,n3.tail=n4;
n4.data=4,n4.tail=n5;
n5.data=5,n5.tail=null;

链表版本的fold函数实现：

 
function lfold(head,callback,b){
if(!head) return b;
else return callback(head.data,arguments.callee(head.tail,callback,b));
} 

执行输出：

18

根据之前的定义，一个集合要么是空集，要么是由“头”与“尾”（即剩余集合）组成的数对。每次调用函数时，将其分解为head和tail，直到集合为空（写完上面的lfold函数后，真心感觉非常完美，简直就是对定义的直接翻译，如果程序都能这样，连注释都不需要了，真是一种享受）。这种形式可以说是最接近数学定义的表示。由于JavaScript不支持许多函数式语言中的模式匹配（match），因此无法“自动”分解，也就不能直接表示归纳定义。

除了上述内容，JavaScript还可以实现函数式编程中的偏函数应用（partial）。例如，Dojo框架中的hitch就实现了这一功能，这也是函数式编程贴近数学概念的另一个显著例子。我将在下一篇博客中对此进行详细讨论。