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

引用

看到作者 lichray 忙于研究数理逻辑，其父发出了由衷的感叹：你学的东西没人用啊。“谁说没人用？自己看不懂罢了。Haskell 的语法是‘写意’了点，但其中的思想清澈见底。”

引用

本文以一个函数式风格的快速排序算法为例，把它从 Haskell 代码改写为 大家所熟知的 JavaScript 代码，试图说明 FP 绝对是表达思想的最强工具。不要被那些 FP 语言们的语法所迷惑。终有一天，你会发现，原来这才是编程啊。

下面是一个 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 的一个重要原因。

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

评论

14 楼 yakamoz 2007-12-31  

function currying(func)   
{   
    return function()   
    {   
        var args = Array.prototype.slice.call(arguments,0);      
        if(args.length<func.length)   
        {                        
            return function(){   
                var _args = args.concat(Array.prototype.slice.call(arguments,0));      
                return currying(func).apply(this,_args);   
            }   
        }   
        else return func.apply(this,args);   
    }   
}  

13 楼 Trustno1 2007-08-03  

厌倦发呆 写道

oxware 写道

Elminster 写道

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

FP远比图灵机模型适合描述算法
很多讨论都在图灵机展开，是因为人类目前的制造水平只能造出类似图灵机的冯诺依曼机器……或者说历史和产业的契机看中了冯诺依曼机器

所谓"算法",并非仅仅指若干数学公式,还包括该算法应用于不同问题时,其在空间和时间的成本花销的评估.FP适合描述公式，即如何求值，但描述时间和空间成本上的花销就不是很方便了。另外，非冯诺依曼计算机很早就存在，只不过没有推广开。

算法涉及两个方面:1.可计算性,2.复杂性.
对于第一个问题来说,不是所有的数学问题都是可计算的,在这个领域里,lambda caculus与图林机相比有优势.要证明数学问题是否可递归化,要比用图林机方便的多.但是这个领域基本上就是纯粹的数学分析,递归化只不过是一个证明的目标.FP恐怕连工具都算不上,仅仅是在最后实现算法的时候,用FP表述递归函数更简便一些.

第二个问题,基本上是图林系统了.

12 楼 厌倦发呆 2007-08-03  

oxware 写道

Elminster 写道

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

FP远比图灵机模型适合描述算法
很多讨论都在图灵机展开，是因为人类目前的制造水平只能造出类似图灵机的冯诺依曼机器……或者说历史和产业的契机看中了冯诺依曼机器

所谓"算法",并非仅仅指若干数学公式,还包括该算法应用于不同问题时,其在空间和时间的成本花销的评估.FP适合描述公式，即如何求值，但描述时间和空间成本上的花销就不是很方便了。另外，非冯诺依曼计算机很早就存在，只不过没有推广开。

11 楼 oxware 2007-08-03  

Elminster 写道

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

FP远比图灵机模型适合描述算法
很多讨论都在图灵机展开，是因为人类目前的制造水平只能造出类似图灵机的冯诺依曼机器……或者说历史和产业的契机看中了冯诺依曼机器

10 楼 mathgl 2007-07-18  

haskell是个不错的冬冬

正在学

9 楼 whisper 2007-07-18  

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

8 楼 coderplay 2007-07-15  

erlang用上list comprehension

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

7 楼 dennis_zane 2007-07-15  

cookoo 写道

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

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差不多了

6 楼 Elminster 2007-07-15  

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

5 楼 Lich_Ray 2007-07-15  

cookoo 写道

这个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 版，还可以利用一下基于对象模型，命令式的风格搞不好效率更高。

4 楼 cookoo 2007-07-15  

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

3 楼 simohayha 2007-07-14  

dennis_zane 写道

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

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

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

2 楼 tysw 2007-07-14  

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

1 楼 dennis_zane 2007-07-14  

语言是其次，只是表达思想的工具罢了，说的好，来个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不了解