ここでは、Haskell で選択ソート(selection sort)を実装してみましょう。 選択ソートを知らない人は このページ を参照してください。
私は長い間、 Haskell による選択ソートの簡単な実装を思いつきませんでした。 未ソート領域の最小値と先頭の要素との交換にこだわっていたためです。 しかし、何のことはない。 要は最小値を未ソート領域から取り除くことさえできれば、 選択ソートは簡単に実装できます。 Haskell による選択ソートの実装は以下のようになります。
関数型で簡単に実装できるやり方を選んだおかげで、 思わぬ副産物が得られました。 上記の実装は選択ソートですが安定ソートなのです。 選択ソートを不安定にしていた原因は要素の交換で、 要素の delete にしてやれば安定になります。
さて、上記の実装を見て、unfoldr とは何ぞやという人もいるでしょう。 「普通にやれ、普通に！」 をスローガンにしておきながら、 unfoldr などという気取った関数を使うとは何事かと思われるかもしれません。 しかし、 これには訳があります。確かに選択ソートはもっと簡単に実装できます。 以下のようになります。
挿入ソートに迫る簡単さですが、 このコードは遅いんです。そこで、 安定ソートであることを確認できるようにするために、 比較器(cmp)を導入するのと一緒に unfoldr を使って高速化してあります。