読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskell入門 パターン照合で並べ替え

1.思い出

昇順に並べ替える問題(ソート)は、カリフォルニア大学のバークレイ校で学んでいるときに、プログラミングの授業の中で出会った。とは言っても、今の時代のように、JavaやCなどの高級言語がない時代で、機械語に近いアセンブリ言語を用いてのプログラミングであった。コンピュータという機械の動作を意識しながら、プログラムを記述する。このため、現在のプログラミングと比べると、とても原始的であるが、その分だけ、コンピュータに親しむことができた。

アセンブリ言語でのプログラミングは、局所的な操作に目が向けられるため、全体的な動作が把握しにくい。そのため、ソートのような小さなものでさえ、プログラミングはなかなか大変である。これに対して、Haskellは、計算の方法ではなく、計算の構造を示せばよいので、大局的にプログラムを記述できる。もっとも、JavaやCなどの手続き型プログラミング言語になじんだ人にとっては、どのように計算がされているのか分かりにくいので、しっくりとはいかないであろう。

2.パターン照合

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でロードして用いることにする。

3.実行

それではこのプログラムを利用してみる。整数、文字、文字列について実行した結果は以下のとおりである。
f:id:bitterharvest:20140924085507p:plain

4.別記述

先ほどのプログラムは、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