ソート - haskell-shoen

ソート

列を定められた順序によって並び替える操作。値がソートされているかどうかは以下のような式で判定できる(foldrトリック):

code:haskell

isSorted :: (Foldable f, Ord a) => f a -> Bool

isSorted xs = foldr (\x r prev -> all (<=x) prev && r (Just x)) (const True) xs Nothing

リストのソート

Data.Listにはマージソートの一種であるsortと、各要素を関数に適用した結果によって比較するsortOn、自前の比較関数でソートするsortByがある。sortOn fはあらかじめmap f相当の処理を実行するので、fの計算量が小さい場合はsortBy (Data.Ord.comparing f)のほうがよい。

code:haskell

sort :: Ord a => a -> a

sortOn :: Ord b => (a -> b) -> a -> a

sortBy :: (a -> a -> Comparing) -> a -> a

vectorのソート

vector-algorithmsパッケージで配列用の各種ソートアルゴリズムが用意されている。迷ったらData.Vector.Algorithms.Introを使っておけば問題ない。

code:haskell

Prelude> import qualified Data.Vector.Unboxed as V

Prelude V> import qualified Data.Vector.Algorithms.Intro as V

Prelude V V> :set -XOverloadedLists

Prelude V V> V.modify V.sort 11, 45, 23, 68 :: Int

11,23,45,68

任意の構造のソート

特殊な構造を活用すれば実現できる。Compose (Writer (Heap a)) (State (Heap a))は、まずヒープを構築し、最後にヒープを消費するようなアクションを表し、Applicativeのインスタンスによって合成できるので、traverseの引数として与えることでヒープソートが実現できる。このアイデアの実装としてsort-traversableというパッケージがある。

ヒープの利用

ビームサーチのように、ソート済みのデータ構造から値を一つずつ追加したり取り出したいときはヒープが便利だ。heapsパッケージが効率のよい実装をしている。