Haskellのソートあれこれ

[codewars](www.codewars.com)で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の比較
```型.hs
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の大小比較用特殊形ということ）

```sort.hs 
-- 第一項を比較して並べ替える（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のパフォーマンスについては後にもう一度議論がある）

```sort.hs 
-- 第一項を比較して並べ替える（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`の代わりに指定することでも同じことができる。

```flipによる降順ソート（importは省略）.hs
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`。

```シンプルな例.hs
sortOn Down [1,2,3,4]
[4,3,2,1]
```
```以下は全て同じ.hs
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.hs
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](https://ro-che.info/articles/2016-04-02-descending-sort-haskell)

このサイトの検証によれば、`sortOn Down`による降順ソートは`sortBy (comparing Down)`によるものより７倍も遅いという。理由は`Down`は単なる`newtype`で本処理ではないため、`sortOn`がシュワルツ変換の複雑なロジックになっている分が逆にオーバーヘッドになってしまうから、とのこと。

# Data.Ordの定義

```Data.Ordの定義ってこれだけだった.hs
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の実装.hs
sortWith f = sortBy (\x y -> compare (f x) (f y))
```
なぜ、このような関数が`GHC.Exts`にあるのか？
全く同じ疑問を持った方がいらっしゃって回答もココにあった。
[What is GHC.Exts, and how were its contents chosen?
](https://stackoverflow.com/questions/28229211/what-is-ghc-exts-and-how-were-its-contents-chosen)

# 最後に
なお、冒頭でも書いた通り、実例は大半が[codewars](www.codewars.com)のサイトから、解説文はGHCのコメントからお借りしています。