函数式编程语言曲高和寡？

下面是一个 Haskell 写的快速排序算法，一共四行（想想学校里教的一般是多少行~）：

qsort [] = []
qsort (x:xs) = qsort lt ++ [x] ++ qsort st
	where lt = [y | y <- xs, y < x]
		st = [y | y <- xs, y >= x]

想理解它是再简单不过的事：首先确定递归下界——排序空列表的结果为空列表本身。
qsort [] = []
然后把快速排序算法的目的描述一下：
把一个选出的元素（这里是第一个元素 x）作为“中间元素”，同时把剩余元素组成的列表记作 xs，将所有小于中间元素的元素组成的列表排序 qsort lt 连接上 ++ 这个元素“组成的列表”[x] 再连接上 ++ 所有大于等于这个元素的其它元素排序后的列表 qsort st；这里用到的 where 变量 it 指的是 = 所有小于它的元素组成的列表 [y | y <- xs, y < x]，st 指的是 = 所有大于等于这个元素的其它元素的列表 [y | y <- xs, y >= x]。

下面把它转换为较低级的 Scheme 代码。先分析一下这里用到的 Haskell 语言的特性：

1. 第一句，指定函数取值点。相对于数学中描述函数在某点取值的语法。对于普通的语言，可以用 if 语句代替。
2. 参数 (x:xs)，是参数领悟特性。指的是，此参数是一个由元素 x 开头，剩余部分为 xs 组成的列表。对于普通的语言，可以用在函数内部绑定参数的分解结果的方法代替。
3. 列表连接运算符 ++，用 append 函数代替。
4. where 语句，后置变量说明。用前置 let 绑定代替。
5. 类似 [y | y <- xs, y < x] 的列表领悟。对于单元素的领悟，用 filter 函数过滤，过滤规则表示为 lambda 函数，它对于 y < x 返回 true。

下面是转换后的 Scheme 版本的程序：

;; 使用 SICP 中描述的 filter 函数，就不抄在这儿了
(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))))))

下面把它转换为我们需要的 JavaScript 代码。先分析一下这里用到的 Scheme 语言的能力：

1. 取列表首项函数 car，用 Array[0] 代替。
2. 取列表剩余项函数 cdr，用 Array.slice(1) 代替。
3. 判断列表是否为空函数 null?，用 ls == false 代替（JS 的特殊之处）。
4. 变量绑定语法 let，仅用声明变量语法 var 代替（千万不能不用）。// 在 JavaScript 1.6 中加入了 let 关键字，爽一点；还有列表领悟，无语了！
5. 过滤器函数 filter。为快一点起见，自己用命令式风格写一个绑定在 Array.prototype 上。
6. 匿名函数 lambda，不就是匿名 function 嘛！
7. 列表连接函数 append，用 Array.concat() 代替。

OK。下面是要用到的、对 JavaScript 1.5 作出的扩展：

// 把要用到的表达式抽象出来
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;
}

这样就可以写出转换后的 JavaScript 代码了：

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())
}

最后试一下：
js> [4,7,9,1,3,5].qsort()
1,3,4,5,7,9
是不是有一种“终于找到组织了”的感觉呢？

题外话：
对比一下用命令式方法写成的 JavaScript 版的快速排序：

function qsort (arr, l, u) {
    l = l || 0;
    u = ((u != 0) && (u == undefined)) ? arr.length : u;
    if (l >= u) return;
    var m = l;
    for (var i = l+1; i <= u; i++)
	if (arr[i] < arr[l])
	    arr.swap(++m, i);
    arr.swap(l, m);
    qsort(arr, l, m-1);
    qsort(arr, m+1, u);
}

代码好像少一点，但我没看懂——虽然是我自己写的，3 个月前写的——要是有 bug 我就直接 faint 了...
JavaScript 真是一个站在函数式编程语言与命令式编程语言之间的奇特生物——包容任何思想，这也是我钟爱 JavaScript 的一个重要原因。

函数式编程语言曲高和寡，谁说的？掌握其思想是重要的，也是容易的；语言是其次，只是表达思想的工具罢了。

语言是其次，只是表达思想的工具罢了，说的好，来个Erlang版本的：

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),[H|qsort(St)]).

有个疑问，qsort (x:xs)与qsort([H|T])应该都是模式匹配吧？我对haskell不了解

只是一个习惯性问题, 看惯了命令式语言写的程序, 咋一看函数式的肯定不习惯

呵呵，恩 都是模式匹配。 我觉得FP中 的模式匹配，就是为了更好的使用递归.

PS:感觉有模式匹配的语言真是起来舒服的说，呵呵。

这个qsort实现partition时多搜了一次全表，性能差了点

这个确实。相比之下，命令式语言可以利用同时给两个数组赋值的办法解决这个问题。FP 中想这么干，用 unzip [(y,z) | y <- xs, z <- xs, y < x, z >= x] 倒是可以，但那样会用到矩阵转置，要不是因为有元组的访问效率的话，恐怕就得不偿失了。用 filter 也是类似的。看来只能修改 filter 了，使它返回一个由两个列表组成的元组，前者是过滤结果，后者是剩余结果。

part [] _ = ([], [])
part (x:xs) func =
	if func x
	then (x : fst (part xs func), snd (part xs func))
	else (fst (part xs func), x : snd (part xs func))

现在就可以令

(lt,st) = part xs (<x)

差不多了吧。感觉是可以了。part 函数中的 fst，snd 函数费时应该可以忽略不计。part 很有用的样子…如果写成 JavaScript 版，还可以利用一下基于对象模型，命令式的风格搞不好效率更高。

FP 并不适于描述算法，你看所有关于时间空间复杂度的严肃讨论都是在图灵机模型上展开的，就知道了。

ruby倒是直接支持partition，方便很多：

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

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]).

模式匹配就体现的更充分了。当然Erlang也是有支持partition，这样写出来就跟ruby差不多了

erlang用上list comprehension

qsort([]) ->
    [];
qsort([H | T]) ->
    qsort([ X || X <- T, X < H ]) ++ [H] ++ qsort([ X || X <- T, X >= H ]).

当年就是靠个haskell的快排把面试官忽悠过去的
现在我一说haskell，就接近被K