Lich Ray写了个帖子《
函数式编程语言曲高和寡？》，用快速排序的例子来说明函数式编程在表达思想方面比命令式语言更容易，其实这一点毋庸置疑，如果你正在读或者读过SICP的话。文中给了haskell、scheme和javascript的实现例子，我也凑趣写了个Erlang版本，haskell我不了解就不说了，其他实现分别如下：
scheme：
javascript:
扯远些可以谈到模式匹配是以“like-a”来代替消息分派在传统命令式语言中严格的“is-a”，这也跟现实世界的情况更为符合，现实世界中我们对事物的判断都是模糊。而这一点，不正是“Duck-Typing”？传统语言对于对象的类型(type)判断来源于严格确定对象是什么类（class），不是这个类它就没有相应的方法，而事实上类与类型这两个概念并不是一致的，对象的类型更应该根据对象能够做什么来决定。扯远了，这只是我读《 失踪的链环》得来的感受，如果对模式匹配还有怀疑的话，让我们回到这个例子的Erlang版本，代码中我们调用了两次filter进行全表扫描，以便得到根据H切割的大小两个部分，这在性能上有不小的影响，那么我们能不能只进行一次全表扫描呢，返回结果是“大小”两个部分，看看Erlang应该怎么写：
这几行代码充分展现了模式匹配的威力，不过Erlang其实有内置的方法partition用于切割list的，这里只是为了展现模式匹配，因此上面的代码可以改为：
同样的代码改写为ruby版本：
scheme：
(define (qsort ls)
( if (null ? ls) ' ()
(let
((x (car ls))
(xs (cdr ls)))
(let
((lt (filter (lambda (y) (< y x)) xs))
(st (filter (lambda (y) (>= y x)) xs)))
(append (qsort lt) (list x) (qsort st))))))
( if (null ? ls) ' ()
(let
((x (car ls))
(xs (cdr ls)))
(let
((lt (filter (lambda (y) (< y x)) xs))
(st (filter (lambda (y) (>= y x)) xs)))
(append (qsort lt) (list x) (qsort st))))))
javascript:
//
把要用到的表达式抽象出来
Array . prototype . head = function () {
return this[ 0 ];
}
Array . prototype . tail = function () {
return this . slice( 1 );
}
Array . prototype . filter = function (proc) {
var tmpArr = [];
for (var i = 0 ; i < this . length ; i ++ )
if (proc(this[i]) == true)
tmpArr . push (this[i]);
return tmpArr;
}
Array . prototype . qsort = function () {
if (this == false) return []
var x , xs , lt , st
x = this . head()
xs = this . tail()
lt = xs . filter(function (y) { return y < x})
st = xs . filter(function (y) { return y >= x})
return lt . qsort() . concat([x] , st . qsort())
}
用Erlang的话，Erlang的list其实跟scheme的list是一样的，甚至连定义的基本高阶函数都一样：map,filter，append等等,利用lists模块提供的filter和append，我们可以写出：
Array . prototype . head = function () {
return this[ 0 ];
}
Array . prototype . tail = function () {
return this . slice( 1 );
}
Array . prototype . filter = function (proc) {
var tmpArr = [];
for (var i = 0 ; i < this . length ; i ++ )
if (proc(this[i]) == true)
tmpArr . push (this[i]);
return tmpArr;
}
Array . prototype . qsort = function () {
if (this == false) return []
var x , xs , lt , st
x = this . head()
xs = this . tail()
lt = xs . filter(function (y) { return y < x})
st = xs . filter(function (y) { return y >= x})
return lt . qsort() . concat([x] , st . qsort())
}
qsort([])
->
[];
qsort([H | T]) ->
Lt = lists : filter(fun(E) -> E < H end , T) ,
St = lists : filter(fun(E) -> E >= H end , T) ,
lists : append(qsort(Lt) , lists : append([H] , qsort(St))) .
我们来比较下scheme和Erlang版本，两者最显著的不同是，scheme使用了条件语句if，而Erlang却是通过模式匹配来代替条件分支判断。同样，在list的分解上面，Erlang也是利用了规则匹配来代替car,cdr函数，从这里可以看出规则匹配在Erlang中的主要作用：分解复杂数据结构以便赋值和条件分支的分派。
qsort([H | T]) ->
Lt = lists : filter(fun(E) -> E < H end , T) ,
St = lists : filter(fun(E) -> E >= H end , T) ,
lists : append(qsort(Lt) , lists : append([H] , qsort(St))) .
扯远些可以谈到模式匹配是以“like-a”来代替消息分派在传统命令式语言中严格的“is-a”，这也跟现实世界的情况更为符合，现实世界中我们对事物的判断都是模糊。而这一点，不正是“Duck-Typing”？传统语言对于对象的类型(type)判断来源于严格确定对象是什么类（class），不是这个类它就没有相应的方法，而事实上类与类型这两个概念并不是一致的，对象的类型更应该根据对象能够做什么来决定。扯远了，这只是我读《 失踪的链环》得来的感受，如果对模式匹配还有怀疑的话，让我们回到这个例子的Erlang版本，代码中我们调用了两次filter进行全表扫描，以便得到根据H切割的大小两个部分，这在性能上有不小的影响，那么我们能不能只进行一次全表扫描呢，返回结果是“大小”两个部分，看看Erlang应该怎么写：
sort([]) -> [];
sort([Pivot|Rest]) ->
{Smaller, Bigger} = split(Pivot, Rest),
lists:append(sort(Smaller), [Pivot|sort(Bigger)]).
split (Pivot , L) ->
split (Pivot , L , [] , []) .
split (Pivot , [] , Smaller , Bigger) ->
{Smaller , Bigger};
split (Pivot , [H | T] , Smaller , Bigger) when H < Pivot ->
split (Pivot , T , [H | Smaller] , Bigger);
split (Pivot , [H | T] , Smaller , Bigger) when H >= Pivot ->
split (Pivot , T , Smaller , [H | Bigger]) .
sort([Pivot|Rest]) ->
{Smaller, Bigger} = split(Pivot, Rest),
lists:append(sort(Smaller), [Pivot|sort(Bigger)]).
split (Pivot , L) ->
split (Pivot , L , [] , []) .
split (Pivot , [] , Smaller , Bigger) ->
{Smaller , Bigger};
split (Pivot , [H | T] , Smaller , Bigger) when H < Pivot ->
split (Pivot , T , [H | Smaller] , Bigger);
split (Pivot , [H | T] , Smaller , Bigger) when H >= Pivot ->
split (Pivot , T , Smaller , [H | Bigger]) .
这几行代码充分展现了模式匹配的威力，不过Erlang其实有内置的方法partition用于切割list的，这里只是为了展现模式匹配，因此上面的代码可以改为：
sort
([])
->
[];
sort ([Pivot | Rest]) ->
{Smaller , Bigger} = lists : partition(fun(E) -> E < Pivot end , Rest) ,
lists : append( sort (Smaller) , [Pivot | sort (Bigger)]) .
sort ([Pivot | Rest]) ->
{Smaller , Bigger} = lists : partition(fun(E) -> E < Pivot end , Rest) ,
lists : append( sort (Smaller) , [Pivot | sort (Bigger)]) .
同样的代码改写为ruby版本：
def qsort(array)
arr=array.dup
if arr == []
[]
else
x = arr . shift
smaller , bigger = arr . partition{ | e | e <= x}
qsort(smaller) + [x] + qsort(bigger)
end
end
arr=array.dup
if arr == []
[]
else
x = arr . shift
smaller , bigger = arr . partition{ | e | e <= x}
qsort(smaller) + [x] + qsort(bigger)
end
end
ruby与Erlang都有并行赋值，但是ruby不支持模式匹配。请注意ruby并没有尾递归优化，因此上面的代码在数组比较大的时候会导致栈溢出，想用ruby做函数式编程应该尽量多使用循环和map,filter,collect等辅助高阶函数。
另外一个Erlang与ruby、scheme比较重要的区别是Erlang的变量只能赋值一次（或者说绑定），也就是single assignment。这个特点与Erlang所要满足的运行场景有紧密关系，当系统发生错误时，就可以从原来的值重新启动任务，而不用担心由于变量值的变化导致系统恢复困难
。文章转自庄周梦蝶 ，原文发布时间2007 7 15
