１．思い出
昇順に並べ替える問題（ソート）は、カリフォルニア大学のバークレイ校で学んでいるときに、プログラミングの授業の中で出会った。とは言っても、今の時代のように、JavaやCなどの高級言語がない時代で、機械語に近いアセンブリ言語を用いてのプログラミングであった。コンピュータという機械の動作を意識しながら、プログラムを記述する。このため、現在のプログラミングと比べると、とても原始的であるが、その分だけ、コンピュータに親しむことができた。
アセンブリ言語でのプログラミングは、局所的な操作に目が向けられるため、全体的な動作が把握しにくい。そのため、ソートのような小さなものでさえ、プログラミングはなかなか大変である。これに対して、Haskellは、計算の方法ではなく、計算の構造を示せばよいので、大局的にプログラムを記述できる。もっとも、JavaやCなどの手続き型プログラミング言語になじんだ人にとっては、どのように計算がされているのか分かりにくいので、しっくりとはいかないであろう。
２．パターン照合
Haskellの特徴の一つはパターン照合である。論理型言語のPrologにはパターン照合機能があり便利に使ったことがある。ソートのプログラムでもこのパターン照合を用いることとする。ソートに渡されるのは、でたらめに並んだリストである。このリストをまず二つのパターンに分けることとする。一つは空のリスト、もう一つは空でないリストである。
空のリストについてはソートの必要なない。空でないリストについては、リストを、先頭の要素の部分xと、先頭の要素を取り除いたリストの部分xsとに分けることにする。これもパターン照合の一種で、リストをxとxsのパターンに分け、照合できるようにする。
ソートのプログラムは次のような構造とみなせる。リストを先頭の部分xと残りのリストの部分xsに分ける。残りのリストxsのそれぞれの要素をxより小さい集合smallerとそうでない集合largerにわける。集合smallerとlargerに対しても再帰的に同じことをする。Haskellでのプログラムはそのまま記述すればよいので、次のようになる。（なお、largerのほうには等しいものも入ることに注意）
quicksort [] = []
quicksort (x:xs) = quicksort smaller ++ [x] ++ quicksort larger
where
smaller = [a | a <- xs, a < x]
larger = [a | a <- xs, a >= x]上記のプログラムで、最初の行はリストが空の場合である。次の行以下は空でないリストに対する処理である。リストの構造はx:xsである。xが先頭の要素で、xsが残りのリストである。リストx:xsのクイックソートは、quicksort smaller ++ [x] ++ quicksort largerと同じである。ここで、++は二つのリストをつなぎ合わせ一つのリストにする。従って、quicksort smaller ++ [x] ++ quicksort largerは、リストであるquicksort smallerと[x]とquicksort largerを並べたものである。
smallerはxsの中でxより小さい要素を集めた集合なので、quicksort smallerはこの集合を昇順に並べたものである。quicksort largerについても同様である。
where以下は、smallerとlargerがどのようなものであるかを示している。それぞれ、リスト内包表記を用いてxより小さいものとそうでないものの集合と定めている。
上記のプログラムをquicksort.hsというファイルに格納し、Preludeでロードして用いることにする。
３．実行
それではこのプログラムを利用してみる。整数、文字、文字列について実行した結果は以下のとおりである。
４．別記述
先ほどのプログラムは、whereを用いてプログラムを記述したが、letを用いる方法もある。以下のとおりである。どちらを選ぶかは好みの問題である。
quicksort [] = []
quicksort (x:xs) =
let
smaller = [a | a <- xs, a < x]
larger = [a | a <- xs, a >= x]
in quicksort smaller ++ [x] ++ quicksort larger
