| Revision History | |
|---|---|
| Revision 1.0 | 2013年8月25日 |
| 初公開 | |
| Revision 1.1 | 2013年8月28日 |
| 非関数型言語のコードについて、部分リストへの要素追加を止めて リストを再構成するよう変更した | |
Abstract
この記事では、クイックソート・アルゴリズムの実装について、 様々な言語で書かれた関数型プログラミングのコードを紹介していますこの記事の目的は、 非関数型プログラミング言語における 関数型プログラミングの適性度評価の元になる材料を提供する ことです。 ただし、素材は提供しますが、それら言語の(主観的な)優劣については語りません。 それでも、 関数型言語もしくは関数型プログラミングというスタイルに興味を持った人にとって、 本記事が自分にはどんな言語が直感的に理解しやすいかを判断する ヒントになるとすれば幸いです。
なお、この記事の内容は、 2ちゃんねる掲示板 のプログラム板にあるスレッド 【PHP,Python】スクリプト, バトルロワイヤル36【Perl,Ruby】 で行われた議論を整理、加筆したものです。
以降の節では、まず最初に、論理型言語であるPrologのコードで クイックソート・アルゴリズムの定義を示します。 次に、この定義に従って、関数型言語、そして関数型には分類されない言語の順に コードを見ていきます。
Prologによるクイックソート・アルゴリズムを以下に示します:
% quicksort(Xs, Ys) ❶ quicksort([], []). ❷ quicksort([Pivot|Xs], Ys) :- ❸ partition(Xs, Pivot, Littles, Bigs), ❹ quicksort(Littles, Ls), ❺ quicksort(Bigs, Bs), append(Ls, [Pivot|Bs], Ys). ❻ % partition(Xs, N, Ys, Zs) partition([], _, [], []). partition([X|Xs], N, [X|Ys], Zs) :- X < N, !, partition(Xs, N, Ys, Zs). partition([X|Xs], N, Ys, [X|Zs]) :- X >= N, !, partition(Xs, N, Ys, Zs).
リスト | |
リストが空であれば、ソート結果も空である | |
リストが空でなければ、
その先頭要素を中心軸 | |
残りのリスト | |
リスト | |
ソートされた部分リスト |
以降の節では、ここで示したアルゴリズムを どれだけ素直に(=直感的に)コードで表現できるか？が、 関数型プログラミングの適性度を測る評価基準になるでしょう。
なお、言語によっては、
汎用的なpartition操作が標準で提供されているものがあります。
そこで
表現力の公平を期すため、
以降の節では、まず最初にpartition操作無しでコードを示し、
その後でpartition操作を用いるコードを示すことにします。
関数型言語が関数型プログラミングを何の苦もなく実践できるのは、当たり前の話です。
quicksort [] = []
quicksort (pivot:xs) = quicksort littles ++ pivot:(quicksort bigs)
where
f x (ls, bs) = if x < pivot then (x:ls, bs) else (ls, x:bs)
(littles, bigs) = foldr f ([], []) xs
標準関数partitionを使うと、より簡潔なコードが書けます。
quicksort [] = []
quicksort (pivot:xs) = quicksort littles ++ pivot:(quicksort bigs)
where (littles, bigs) = partition (< pivot) xs
このコードに関数partitionの定義を追加したものが、
最終版になります。
quicksort [] = []
quicksort (pivot:xs) = quicksort littles ++ pivot:(quicksort bigs)
where (littles, bigs) = partition (< pivot) xs
partition f = foldr g ([], [])
where g x (ys, zs) = if f x then (x:ys, zs) else (ys, x:zs)
fun quicksort [] = []
| quicksort (pivot::xs) = let
fun f (x, (ls, bs)) = if x < pivot then (x::ls, bs) else (ls, x::bs)
val (littles, bigs) = foldr f ([], []) xs
in
quicksort littles @ pivot::(quicksort bigs)
end
標準ライブラリ関数List.partitionを使うと、
より簡潔なコードが書けます。
fun quicksort [] = []
| quicksort (pivot::xs) = let
val (littles, bigs) = List.partition (fn x => x < pivot) xs
in
quicksort littles @ pivot::(quicksort bigs)
end
このコードに関数partitionの定義を追加したものが、
最終版になります。
fun partition f = let
fun g (x, (ys, zs)) = if f x then (x::ys, zs) else (ys, x::zs)
in
foldr g ([], [])
end
fun quicksort [] = []
| quicksort (pivot::xs) = let
val (littles, bigs) = partition (fn x => x < pivot) xs
in
quicksort littles @ pivot::(quicksort bigs)
end
前置きが長くなりましたが、ここからが本記事の本題になります。
この節で取り上げる Ruby, JavaScript, Python は どれも関数型言語には分類されていませんが、 関数型の特性を取り入れていると言われています。 そんな関数型の特性の一つが式指向であり、 これは 分岐や反復といった制御構造に関して if/case/while/for文を使わず分岐式と関数再帰だけで表現する ことを意味します。 したがって、以降の非関数型言語による関数型プログラミングでも 文指向の代わりに式指向で、 言い換えると if/case/while/for文を使用しないコード が求められます。
それでは、これら言語の関数型プログラミング・スタイルを 見ていくことにしましょう。
def quicksort(xs)
if xs.length <= 1
xs
else
pivot = xs[0]
littles, bigs = xs[1..-1].inject([[], []]) { |(ls, bs), x|
if x < pivot then [ls + [x], bs] else [ls, bs + [x]] end
}
quicksort(littles) + [pivot] + quicksort(bigs)
end
end
標準メソッドEnumerable#partitionを使うと、
より簡潔なコードが書けます。
def quicksort(xs)
if xs.length <= 1
xs
else
pivot = xs[0]
littles, bigs = xs[1..-1].partition { |x| x < pivot }
quicksort(littles) + [pivot] + quicksort(bigs)
end
end
このコードにメソッドpartitionの定義を追加したものが、
最終版になります。
def partition(xs)
xs.inject([[], []]) { |(ys, zs), x|
if yield(x) then [ys + [x], zs] else [ys, zs + [x]] end
}
end
def quicksort(xs)
if xs.length <= 1
xs
else
pivot = xs[0]
littles, bigs = partition(xs[1..-1]) { |x| x < pivot }
quicksort(littles) + [pivot] + quicksort(bigs)
end
end
function quicksort(xs) {
function f(xs) {
var pivot = xs[0];
function g(pair, x) {
var ls = pair[0], bs = pair[1]
return x < pivot ? [ls.concat([x]), bs] : [ls, bs.concat([x])];
}
var pair = xs.slice(1).reduce(g, [[], []]);
var littles = pair[0], bigs = pair[1];
return [].concat(
quicksort(littles), [pivot], quicksort(bigs)
);
}
return xs.length <= 1 ? xs : f(xs);
}
JavaScriptはpartition操作を標準で提供しませんが、
その操作を汎用的な関数として抽象化することで、
コードの意図はより明確になるでしょう。
function partition(xs, f) {
function g(pair, x) {
var ys = pair[0], zs = pair[1]
return f(x) ? [ys.concat([x]), zs] : [ys, zs.concat([x])];
}
return xs.reduce(g, [[], []]);
}
function quicksort(xs) {
function f(xs) {
var pivot = xs[0];
var pair = partition(xs.slice(1), function(x) { return x < pivot; });
var littles = pair[0], bigs = pair[1];
return [].concat(quicksort(littles), [pivot], quicksort(bigs));
}
return xs.length <= 1 ? xs : f(xs);
}
このコードを最終版とします。 なお、好みしだいで、ローカル関数宣言の代わりにラムダ式でも書けます。
function partition(xs, f) {
return xs.reduce(
function(pair, x) {
var ys = pair[0], zs = pair[1]
return f(x) ? [ys.concat([x]), zs] : [ys, zs.concat([x])];
},
[[], []]
);
}
function quicksort(xs) {
return xs.length <= 1 ? xs : (
function() {
var pivot = xs[0];
var pair = partition(xs.slice(1), function(x) { return x < pivot; });
var littles = pair[0], bigs = pair[1];
return [].concat(quicksort(littles), [pivot], quicksort(bigs));
}
)();
}
def quicksort(xs):
def f(xs):
pivot = xs[0]
def g(pair, x):
(ls, bs) = pair
return (ls + [x], bs) if x < pivot else (ls, bs + [x])
(littles, bigs) = reduce(g, xs[1:], ([], []))
return quicksort(littles) + [pivot] + quicksort(bigs)
return xs if len(xs) <= 1 else f(xs)
Pythonはpartition操作を標準で提供しませんが、
その操作を汎用的な関数として抽象化することで、
コードの意図はより明確になるでしょう。
def partition(xs, f):
def g(pair, x):
(ys, zs) = pair
return (ys + [x], zs) if f(x) else (ys, zs + [x])
return reduce(g, xs, ([], []))
def quicksort(xs):
def f(xs):
pivot = xs[0]
(littles, bigs) = partition(xs[1:], lambda x: x < pivot)
return quicksort(littles) + [pivot] + quicksort(bigs)
return xs if len(xs) <= 1 else f(xs)
このコードを最終版とします。 なお、好みしだいで、ローカル関数宣言の代わりにラムダ式でも書けます。
def partition(xs, f):
return reduce(
lambda pair, x:
(
lambda (ys, zs) = pair:
(ys + [x], zs) if f(x) else (ys, zs + [x])
)(),
xs, ([], [])
)
def quicksort(xs):
return xs if len(xs) <= 1 else (
lambda pivot = xs[0]:
(
lambda (littles, bigs) = partition(xs[1:], lambda x: x < pivot):
quicksort(littles) + [pivot] + quicksort(bigs)
)()
)()
本記事を終えるに当たって、 それぞれの言語の最終版コードをまとめて示します。
quicksort [] = []
quicksort (pivot:xs) = quicksort littles ++ pivot:(quicksort bigs)
where (littles, bigs) = partition (< pivot) xs
partition f = foldr g ([], [])
where g x (ys, zs) = if f x then (x:ys, zs) else (ys, x:zs)
fun partition f = let
fun g (x, (ys, zs)) = if f x then (x::ys, zs) else (ys, x::zs)
in
foldr g ([], [])
end
fun quicksort [] = []
| quicksort (pivot::xs) = let
val (littles, bigs) = partition (fn x => x < pivot) xs
in
quicksort littles @ pivot::(quicksort bigs)
end
def partition(xs)
xs.inject([[], []]) { |(ys, zs), x|
if yield(x) then [ys + [x], zs] else [ys, zs + [x]] end
}
end
def quicksort(xs)
if xs.length <= 1
xs
else
pivot = xs[0]
littles, bigs = partition(xs[1..-1]) { |x| x < pivot }
quicksort(littles) + [pivot] + quicksort(bigs)
end
end
function partition(xs, f) {
function g(pair, x) {
var ys = pair[0], zs = pair[1]
return f(x) ? [ys.concat([x]), zs] : [ys, zs.concat([x])];
}
return xs.reduce(g, [[], []]);
}
function quicksort(xs) {
function f(xs) {
var pivot = xs[0];
var pair = partition(xs.slice(1), function(x) { return x < pivot; });
var littles = pair[0], bigs = pair[1];
return [].concat(quicksort(littles), [pivot], quicksort(bigs));
}
return xs.length <= 1 ? xs : f(xs);
}
def partition(xs, f):
def g(pair, x):
(ys, zs) = pair
return (ys + [x], zs) if f(x) else (ys, zs + [x])
return reduce(g, xs, ([], []))
def quicksort(xs):
def f(xs):
pivot = xs[0]
(littles, bigs) = partition(xs[1:], lambda x: x < pivot)
return quicksort(littles) + [pivot] + quicksort(bigs)
return xs if len(xs) <= 1 else f(xs)
クイックソートという題材に限定されますが、 非関数型プログラミング言語である Ruby/JavaScript/Pythonともに、 それら言語の特徴を生かしたスタイルを貫けば (式指向 を含む) 関数型プログラミングの適性度 に明らかな差異は見らないと、 筆者は考えます。 あとはプログラマ個々の(主観的な) 好み で選べば いいのではないでしょうか。
さて、あなたは
どの言語が直感的に理解しやすいと感じましたか？
プログラミング生活の良きパートナとして、どの言語を選びますか？