ここでは、Haskellでバブルソート(bubble sort)を実装してみましょう。 バブルソートを知らない人は このページ を参照してください。最も素朴なバブルソートの実装は以下のようになります。
しかし、手続き脳的にはこれでは不十分に感じますよね。 手続き型言語でバブルソートを実装すれば、 要素の交換が行われなくなったらループを終了するようにできます。 ほとんどソート済みの系列をソートする場合など、この方が速くなります。 例えば C++ で実装すれば以下のようになります。
手続き脳で考えるなら、 最後に交換が行われた位置を憶えておく変数が必要で、 しかもその変数は交換が行われる毎に書き換える必要があります。 Haskell では変数の書き換えは出来ません。ではどうしたらよいでしょうか。 実は Haskell でも変数の書き換えモドキは実行可能です。 再帰呼び出しの戻り値は、 再帰から戻る度に新しい値に書き換えることができます。ですから、 書き換えたい変数があれば、それを再帰の戻り値にしてやればいいのです。 もちろん、本来返したい値も返す必要があるので、 必然的にタプルを使って複数の値を返すことになります。
要素の交換が行われなくなったらループを終了するバブルソートの Haskell による実装は以下のようになります。
残念ながらこのコードは乱数の系列をソートする場合、 素朴なバブルソートよりかなり遅くなります。 C++ の場合はこの工夫をすると速くなるんですけどね。 原因は多分、(++)演算子を濫用しているからでしょう。