ソート
列を定められた順序によって並び替える操作。値がソートされているかどうかは以下のような式で判定できる(
foldrトリック):
haskellisSorted :: (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) のほうがよい。
haskellsort :: Ord a => [a] -> [a]
sortOn :: Ord b => (a -> b) -> [a] -> [a]
sortBy :: (a -> a -> Comparing) -> [a] -> [a]
vector-algorithmsパッケージで配列用の各種ソートアルゴリズムが用意されている。迷ったらData.Vector.Algorithms.Introを使っておけば問題ない。
haskellPrelude> 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パッケージが効率のよい実装をしている。