クィックソートで比較しようか

さて、このところ「面白い本」の出版が目白押しで困ってます....

3/14 には、例の「プログラミングgacuche」が出るようです。ちょっと関数型言語のプチブームが起きている感じがありますよね。で、少しづつですが、Erlang の勉強（Armstrong）もしています（仕事が少し忙しい....）。

Erlang のイイところ、というのはやはり簡潔さ、です。まあ、関数型言語は一般に「プログラムが簡潔」という利点があるのですが、Erlang はまたかなり特別なくらいに「簡潔」なのです。でまあ、「関数型言語の簡潔さ」をちょっと体験してみようか....という企画ものです。

比較対象は例によってクィックソートです。アルゴリズムとしてはとびきり有名ですし、おもちゃとは言えない実用性もありますからね。言語は

1. 1. Scheme(Gauche)
2. 2. Prolog
3. 3. Haskell
4. 4. Erlang

というくらいにしましょうか。Prolog は関数型言語じゃありませんが、Erlang に影響が強い非手続型言語（論理型言語）ですから、これに含めます。ソースを載せますが、別にちゃんと理解しなくてもいいですよ！ 単に「どうやって簡潔に書くか？」を追求し、そのスタイルを比較して入門する人の参考にまで....と思うだけです。

1. Scheme

まずはクラシックに Scheme から。

(define (sort1 x)
  (cond ((null? x) ())
    (else (append (sort1 (left (car x) (cdr x)))
              (cons (car x) (sort1 (right (car x) (cdr x))))))))
(define (left a x)
  (cond ((null? x) ())
     ((>= a (car x)) (cons (car x) (left a (cdr x))))
     (else (left a (cdr x)))))

(define (right a x)
  (cond ((null? x) ())
     ((< a (car x)) (cons (car x) (right a (cdr x))))
     (else (right a (cdr x)))))

まあ古典的にはこんな感じでしょう。ただ、left と right が同じような関数になるのが気持ち悪いです....で、今熱い(かな？) gauche だと、コレクションフレームワークに filter 関数があって、これを使うともうちょい簡潔で「Lispっぽい」プログラムにできます。

(use gauche.collection)
(define (sort2 x)
  (cond ((null? x) ())
    (else
     (append (sort2 (filter (lambda (y) (>= (car x) y)) (cdr x)))
         (cons (car x)
               (sort2 (filter (lambda (y) (< (car x) y)) (cdr x)))))))

けど、lambda でカリー化無名関数を作って....というあたり少し難しいかな。

2. Prolog

次は Prolog です。

sort1([],[]).
sort1([X1|X2],Y) :- partition(X1,X2,P1,P2),
    sort1(P1,S1), sort1(P2,S2),
    append(S1,[X1|S2],Y).

partition(X,[],[],[]).
partition(X,[Y|Z],[Y|P1],P2) :- X >= Y, partition(X,Z,P1,P2).
partition(X,[Y|Z],P1,[Y|P2]) :- X < Y, partition(X,Z,P1,P2).

どうしても partition という左右分離述語が必要な感じです。ただし、組み込み述語で持っている append  を使って結果を連結する部分は、いわゆる「差分リスト」（解説）を使うともう少し簡潔にできます。

sort2(X,Y) :- sort2sub(X, Y,[] ).
sort2sub([], Y,Y ).
sort2sub([X1|X2], Y1,Y2 ) :- partition(X1,X2,P1,P2),
    sort2sub(P1, Y1,[X1|S] ), sort2sub(P2, S,Y2 ).

とはいえ、関数型言語ではない Prolog だと、引数に相当する変数と戻り値に相当する変数が区別されない(それが特徴ですが...)ので、読んで理解するには結構コツが要ります....

3. Haskell

sort1 [] = []
sort1 (x:xs) = sort1 [e | e <- xs, e < x] ++ [x] ++ sort1 [e | e <- xs, e >= x]

おお、これは簡潔です！！ しかし、Haskell ってインデントによるブロック制御がある（Pythonと同様に...）ので、私はちょっとこれ苦手なスタイルだったりします。でも、いわゆる「リスト内包表記（数学の集合定義みたいに[e|e <- xs, e < x] とやる部分）」と、リスト連結に ++ 演算子が使えるのが Good ですよね！ この２つがあるために、余計な partition(left,right) とか要りませんし、append も要りません。

4. Erlang

真打Erlang。

sort1([]) -> [];
sort1([Pivot|T]) -> sort1([X || X <- T, X < Pivot])
    ++ [Pivot] ++
    sort1([X || X <- T, X >= Pivot]).

これもリスト内包表記を持ち、++ によるリスト連結があります。しかも、インデントによるブロック制御ではなく、終端子として「;」（関数定義が終わらずに次の節が続く）か「.」（関数定義終わり）が使われ、フリーフォーマットな言語です。

どっちか言えば、Erlang は関数型言語の仕様としては、Haskell での「面白いけど言語的に難しい要素」（型推論、モナド、遅延評価）を取り除き、Prolog 風にパターンマッチを強化したもの(とはいえ差分リストは使えません....バックトラックしないからね。出来たら凄いのに)というニュアンスがあります。ですから、「Haskell のエレガンスを大体保持して、ぐっとやさしく実用的にしたモダンな関数型言語」というくらいかな。

ですから、よく「変数は書きかえれない！」というのが大きな特徴として言われますが、実際には「呼ばれるたびに状態が変わる関数」を作ることがちゃんとできます（プロセスディクショナリと言うErlangプロセスと結びついた Map（って Java の ThreadLocal みたいなもの...苦笑） とか ets という一種のデータベースを使います....）。ですから、「副作用がない」と言われますけども、現実的には「副作用のある関数」を書けますし、Haskell のように

たとえば putStr のように、（一般に）戻り値がなくコンソールに出力する（という副作用を持つ）関数を、IO Monad を返す（理論上）副作用のない関数として実装する

というようなややこしい部分はナシのわけです（まあ、コレがあるから Haskell は Haskell なんですけどね）。

Erlang に慣れれば、「Haskell への入門」みたいな感じでも使える...ということにどうやらなりそうです。関数型プログラミング言語へのとっかかりとしても、有用なのかもしれませんね。