46
從一個小例子出發之ruby、scheme和Erlang的簡單比較
Lich Ray寫了個帖子《函數式編程語言曲高和寡？》，用快速排序的例子來說明函數式編程在表達思想方麵比命令式語言更容易，其實這一點毋庸置疑，如果你正在讀或者讀過SICP的話。文中給了haskell、scheme和javascript的實現例子，我也湊趣寫了個Erlang版本，haskell我不了解就不說了，其他實現分別如下：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
最後更新：2017-05-17 16:01:26