Haskellでクイックソート

Haskellに限らず関数型言語の紹介では、プログラムの簡潔さを表すのにクイックソートがよく使われます。Haskellでクイックソートを書くとこんな風になります。

--qsort.hs
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x]
               ++
               [x]
               ++
               qsort [y | y <- xs, y >= x]

main = print (qsort [1, 3, 2, 5, 4])

Haskellではリスト xs の先頭に要素 x を付け加えたリストを生成する操作を x : xs と書くのですが、qsortの2行目では受け取ったリストを逆にパターンマッチで先頭 x とそれ以降 xs に分割しています。
その後、

• xs の中から順に要素を取り出して y として、y < x を満たす y で作ったリストをqsortする
• x をそのままリストにする
• xs の中から順に要素を取り出して y として、y >= x を満たす y で作ったリストをqsortする

ということをしてから++で連結しています。[ ]で書かれた内包表記はほとんど数学の集合の表記そのままになっています。

これを実行すると、

$ ghc qsort.hs -o qsort
$ ./qsort
[1,2,3,4,5]

となり、確かにソートされていることが分かります。C言語などで書くと複雑になるクイックソートをとても見通しよく書くことができました。