クイックソート

Haskell でクイックソートを書くと、次のようになる。

Prelude> let qsort [] = []; qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)
Prelude> qsort [2,9,7,3]
[2,3,7,9]
Prelude> qsort "hello"
"ehllo"

あっけないほど短い。しかしそれだけでなく、クイックソートのアルゴリズムがよく分かるプログラムになっている。

１）　空リストは並べ替えても空リストである。

再帰的プログラムでは、停止の条件を決めておかないと、永遠に再帰状態が終わらなくなる。

２)　リストの左端の要素を取り出す。

２行目の (x:xs) というパターンは、リストの先頭の要素を x に、それ以降のリストを xs にバインドすることを示す。つまり、左端の要素を取り出すということ。

３）　x を取り出した残りの要素のリスト xs から、 x より小さい要素を集めて、(filter (<x) xs) というリストを作る。

４)　x を取り出した残りの要素のリスト xs から、 x 以上の要素を集めて、(filter (>=x) xs) というリストを作る。

５）　x を一つだけ入れたリスト [x] の左に、ｘ より小さいもののリストをソートしたものを連結し、[x] の右に x 以上のものを集めたリストをソートしたものを連結する。 [x] の両側の数列は再帰的に記述されている。再帰的な記述では qsort の引数はすでに確定していると仮定すると分かりやすい。実際には、再帰的な式の展開が機械によって行われるのだが、それも含めて確定していると考えるとイメージしやすくなる。

こういうアルゴリズムをそのまま記述しただけのようなプログラムが実際に動くというのが面白い。以前から、考えることを補助してくれるプログラム言語はないだろうかと思っていたが、現在のところ、Haskell がそれに一番近いような気がする。まだ慣れていないのでわからないが、何かアイディアを思いついたら先ず Haskell でプログラムして、それから、そのアイディアの足りないところをチェックしていくというような使い方ができるようになったら素敵だ。