Darkside of the Haskell -- 副作用版 分布数えソート

　分布数えソート(計数ソート、counting sort)は配列の副作用を前提にして いると、分布数えソートのページ で書き ました。そんなわけで、実際に副作用ありの配列を使って実装してみました。 Haskell による副作用を使った分布数えソートは以下のようになります。

　コードは副作用なし版より長くなってしまいましたが、何をやっているかは 手続き脳の私にはむしろ明確に書けたと思います。何より、その速度は ブッチギリで、バケットソート を凌駕します。ビバ！副作用(^o^)/ ただし、定義域の自由度は下がって、 ソートのキーは、0 以上の十分小さな整数でなければなりません。

　ところで、UM.unsafeRead, UM.unsafeWrite って何？普通の unsafeRead, unsafeWrite とは違うの？という人もいるかもしれ ません。Haskell の配列は普通は Java でいうところの参照型の配列のように 汎用的な配列になっています。しかし、これは速度の面では不利です。そこで、 Java でいうところのプリミティブ型の配列である Unboxed 配列が用意されて います。これは入れられる要素の型に制限がありますが、その分高速に動作 します。hs は整数(Int)が入れば十分なので、 Unboxed にしてあります。UM はこの Unboxed な配列に対する 操作であることを意味しています。

　また、new は新しい配列を作る関数です。n 個の 要素を持つ配列を生成します。同様に UM.replicate も要素が m + 1 個の配列を作りますが、こちらは UM が 付いていることからも分かるように Unboxed 配列の各要素を 0 で初期化して 作ります。