codewarsでHaskellの問題を解きながらHaskellのソートについてまとめています（随時更新中）
(種々、訳あって再投稿しました。元記事にいいねしてくださった方、申し訳ありませんでした）
sortとsortBy (compare,comparing)
sort
sort :: Ord a => [a] -> [a]
Data.Listで定義されている。実体はsortByの特別形でsortBy compare
compare
compare :: Ord a => a -> a -> Ordering
Ordクラスのメソッド。順序のある要素を比較して、結果としてLT|EQ|GTのいずれかを返す関数
第一引数を主に、第二引数と比較。代数型データは、より左（先）に定義された方が小さい。
sortBy
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortByは二つの引数を比較して大小関係を返す関数（たとえばcompare）を引数にして、リストを並べ替える。したがって、ここに指定する関数によってリストを任意の方法で並べ替えることが可能。
##sortBy compare = sort
つまり、sortBy compareは型で定義された大小関係に基づく昇順ソートとなり、これが関数sortの仕様である。
comparing
comparing :: Ord a => (b -> a) -> b -> b -> Ordering
comparing p x y = compare (p x) (p y)
comparingはData.Ordの関数。
比較する二要素（第二・第三引数）に対して、直接の大小ではなく事前に各々に第一引数の関数を適用した状態で大小判定結果を戻す。
たとえば、comparing fstは、部分適用によりタプルの先頭要素の大小比較結果を返す関数となるので、sortBy (comparing fst)はタプルの先頭要素を使って、タプル自体を昇順ソートする関数になる。
同様の方法で、Data.ListのxxxByファミリの関数と組み合わせて使用できる。(sortBy,insertBy,maximumBy,minimumBy)
on (compare on とcomparing）
on
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
onはData.Functionの関数。こんな感じになる。
(*) on f = \x y -> f x * f y.
- 第一引数は本処理となる関数、第二引数は前処理となる関数。
- 本処理は引数２つの関数なので、まず第二引数の関数で処理した値を、第一引数の関数に適用する。
##comparingとonの比較
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
comparing :: Ord b => (a -> b) -> a -> a -> Ordering
ここでcがOrderingの場合、bは自然とOrdになるので、結局、
comparing = on compare = compare `on` となる。
（onに本処理としてcompareを指定し、「前処理」と「比較する２つの項目」を引数として取れる関数にしたものがcomparingとなり、onの大小比較用特殊形ということ）
-- 第一項を比較して並べ替える（3つは全て同じ）
sortBy (comparing fst) [(3,2),(5,2),(1,2)]
sortBy (compare `on` fst) [(3,2),(5,2),(1,2)]
sortBy (on compare fst) [(3,2),(5,2),(1,2)]
[(1,2),(3,2),(5,2)]
sortOn
sortOn :: Ord b => (a -> b) -> [a] -> [a]
sortOnは型からわかるとおり、リストの各要素に対して関数適用した結果に基づいてソートを行うが、欲しい結果は関数適用後の要素のリストではなく、元の要素のリストである場合に使う。
sortOn fはsortBy (comparing f)と同等だが、シュワルツ（シュウォーツ）変換 と呼ばれる方法を使って入力リストの各要素に対してfを1回だけ評価することでパフォーマンス上の利点がある、との記述がGHCのコメントにはある。
（その分一時作業用のメモリは多く消費する。sortOnのパフォーマンスについては後にもう一度議論がある）
-- 第一項を比較して並べ替える（4つは全て同じ）
sortBy (comparing fst) [(3,2),(5,2),(1,2)]
sortBy (compare `on` fst) [(3,2),(5,2),(1,2)]
sortBy (on compare fst) [(3,2),(5,2),(1,2)]
sortOn fst [(3,2),(5,2),(1,2)]
[(1,2),(3,2),(5,2)]
降順ソート(flip,Down)
flip
compareにfilpを使い、比較する引数の順序を逆転させると比較結果も逆転する。これにより、sortByの引数にflip compareを使うことで降順ソートとすることができる。
またsortByとflipの合成関数を、sortByの代わりに指定することでも同じことができる。
sortDict :: Ord v => [(k,v)] -> [(k,v)]
sortDict = sortBy (flip compare `on` snd)
sortDict = sortBy (\a b -> compare (snd b) (snd a))
sortDict = sortBy (\a b -> (snd b) `compare` (snd a))
sortDict = (sortBy.flip) (comparing snd)
Down
Downは降順をシンプルに実現するためのnewtype。
sortOn Down [1,2,3,4]
[4,3,2,1]
sortDict :: Ord v => [(k,v)] -> [(k,v)]
sortDict = sortBy (flip compare `on` snd)
sortDict = sortBy (\a b -> compare (snd b) (snd a))
sortDict = sortBy (\a b -> (snd b) `compare` (snd a))
sortDict = (sortBy.flip) (comparing snd)
sortDict = sortBy (comparing (Down . snd))
sortDict = sortBy (compare `on` Down . snd)
sortDict = sortBy (compare `on` Down . snd)
sortDict = sortOn (Down . snd)
Down . snd :: (a, b) -> Down b
-- ペアをとって、第二要素のリスト（降順比較）を得る
snd :: (a, b) -> b
Down :: b -> Down b
なお、Down . sndをDown.sndと書くとエラーになる。
A.xを空白を入れずに書くと修飾名(qualified name)扱いとなるため。
空白を一つでも入れれば(.)は関数合成として扱われる。
sortOn Down
ここまでとほぼ同内容を簡潔に説明しているサイトをみつけた（速度検証等もあり素晴らしい内容。こちらを読んでいただければ、私の、この文書は不要かも）
Descending sort in Haskell
このサイトの検証によれば、sortOn Downによる降順ソートはsortBy (comparing Down)によるものより７倍も遅いという。理由はDownは単なるnewtypeで本処理ではないため、sortOnがシュワルツ変換の複雑なロジックになっている分が逆にオーバーヘッドになってしまうから、とのこと。
Data.Ordの定義
module Data.Ord (
Ord(..),
Ordering(..),
Down(..),
comparing,
) where
import GHC.Base
import GHC.Show
import GHC.Read
comparing :: (Ord a) => (b -> a) -> b -> b -> Ordering
comparing p x y = compare (p x) (p y)
newtype Down a = Down a deriving (Eq, Show, Read)
instance Ord a => Ord (Down a) where
compare (Down x) (Down y) = y `compare` x
番外編：sortWith
sortWithはGHC.Extsに属する。
型はsortWith :: Ord b => (a -> b) -> [a] -> [a]
でsortOnと型が全く同じ。結果もおそらく同じ。
sortWith f = sortBy (\x y -> compare (f x) (f y))
なぜ、このような関数がGHC.Extsにあるのか？
全く同じ疑問を持った方がいらっしゃって回答もココにあった。
What is GHC.Exts, and how were its contents chosen?
最後に
なお、冒頭でも書いた通り、実例は大半がcodewarsのサイトから、解説文はGHCのコメントからお借りしています。