ElmにおけるListのソート3パターン

この記事では、ElmのListのソート方法について解説をしていきます。Listのソートを覚えれば、外部APIなどから受け取った値の列をユーザに見せたい順番で並び替えたり、テーブルを表現したときに並び替えボタンの実装などをするときには必須です。それではソート方法について見ていきましょう。


## [List.sort](https://package.elm-lang.org/packages/elm/core/latest/List#sort)関数

それでは、List.sort関数を使ってIntのListを並び替えてみましょう。はい。並び替えができました。これでもう並び替えは完璧ですね！

```elm
> List.sort [ 3, 1, 2 ]
[1,2,3] : List number
```

...ですが、sort関数を覚えるだけでは全てのListについて並び替えができるわけではありません。例えば、以下のようなレコードを渡すとコンパイルエラーになります。エラーの内容としては、sort関数の第一引数には、`List comparable`型を渡す必要があります。となっています。

```elm
> List.sort [ { name = "john", age = 15 }, { name = "mike", age = 20 } ]
-- TYPE MISMATCH ---------------------------------------------------------- REPL

The 1st argument to `sort` is not what I expect:

3|   List.sort [ { name = "john", age = 15 }, { name = "mike", age = 20 } ]
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This argument is a list of type:

    List { age : number, name : String }

But `sort` needs the 1st argument to be:

    List comparable
```

`comparable`型とは一体なんでしょうか。Elmでは小文字で書かれた型名の場合は、型変数であるという説明がされます。`comparable`はユーザ定義の型変数ではなく、Elmが用意した特殊な型変数になります。この特殊な型はElmガイドでは、[制約付き型変数](https://guide.elm-lang.jp/types/reading_types.html)(Constrained Type Variables)と言われます。制約付き型変数は、型変数に取れる型に制限があるものを指します。言い換えれば、制約付き型変数は限られた型を集めたもの(有限個の型の集合)になります。ガイドから抜粋すると、`comparable`に当てはまる型は以下になります。

> comparableにはIntかFloat,Char,String,そしてcomparableな値で構成されるリストまたはタプルを当てはめられます

comparableな値で構成されるリストまたはタプルをsortした例が以下になります。リスト・タプルいずれも前から順番にソート対象になるというわけですね。

```elm
> List.sort [(1, "b"), (1, "a")]
[(1,"a"),(1,"b")] : List ( number, String )
```


```elm
> List.sort [['e', 'l', 'm'], ['e', 'l', 'l', 'i', 'e']]
[['e','l','l','i','e'],['e','l','m']]
    : List (List Char)
```

## [sortBy](https://package.elm-lang.org/packages/elm/core/latest/List#sortBy)関数

レコードはなぜsort関数に渡せないのでしょうか？ それは、レコード型のどのキーに対応する値を使って並び替えするかがわからないためです。`sortBy`関数はあるデータ型からcomparable型の値を指定(`sortBy: (a -> comparable) -> List a -> List a`)を取り出しその値で並び替えることができます。以下は、それぞれ`name: String`と`age: Int`で並び替える例です。つまりこの場合、`String`と`age`が`comparable`な型として成立しています。.nameはレコードのアクセス関数なので次のラムダ式が正式な書き方になります。`(\r -> r.name)`今回の例はレコード型ですが、最終的に`comparable`な型を指定できればどんな型でも対応できます。


```elm
> List.sortBy .name [ { name = "john", age = 20 }, { name = "mike", age = 15 } ]
[{ age = 20, name = "john" },{ age = 15, name = "mike" }]
    : List { age : number, name : String }

> List.sortBy .age [ { name = "john", age = 20 }, { name = "mike", age = 15 } ]
[{ age = 15, name = "mike" },{ age = 20, name = "john" }]
    : List { age : number, name : String }
```

## [sortWith](https://package.elm-lang.org/packages/elm/core/latest/List#sortWith)関数

sortBy関数はある値から`comparable`型の値を取り出すことで並び替えることができていました。しかし、`comparable`ではない型を並び替えたい時はどうするでしょうか。その場合はsortWith関数を使います。

### カスタムタイプのソート

`comparable`ではない型の代表としてカスタムタイプ(ユーザ定義の独自型)が挙げられます。例えば、降順で`松竹梅`の順になる`JapaneseRank`という型を考えてみましょう。sortWith関数は、ソート対象のList と 2つの対象となる型を受け取り、Order型を返す関数を引数に受け取ります。Order型は(LT, GT, EQ)3つの値を持ちます。`梅 < 松`が成り立つ時`LT`(Less)を返します。逆に`松 > 竹`が成り立つ時`GT`(Greater)を返します。最後に、`梅 == 梅`が成り立つときに`EQ`を返します。一番抜け漏れがない方法は2つの値をタプルにしてパターンマッチし、機械的にLT, GT, EQを当てはめていきます。もし漏れがあればコンパイラが教えてくれます。少しかったるいですが、頑張って埋めましょう。

```elm
type JapaneseRank
    = Matsu
    | Take
    | Ume


japaneseRankComparison : JapaneseRank -> JapaneseRank -> Order
japaneseRankComparison r1 r2 =
    case ( r1, r2 ) of
        ( Ume, Take ) ->
            LT

        ( Ume, Matsu ) ->
            LT

        ( Take, Matsu ) ->
            LT
 
        ( Take, Ume ) ->
            GT

        ( Matsu, Ume ) ->
            GT

        ( Matsu, Take ) ->
            GT

        ( Ume, Ume ) ->  -- これ以降は、 _ -> EQ で大丈夫です。
            EQ

        ( Take, Take ) ->
            EQ

        ( Matsu, Matsu ) ->
            EQ

> List.sortWith japaneseRankComparison [ Take, Ume, Matsu ]
[Ume,Take,Matsu] : List JapaneseRank
```

### 複数の条件でソート

sortWithを使うケースは、カスタム型のみではありません。複数の条件で並び替えを行う場合も使用します。例えば、最初は名前でソートし、その後、年齢でソートをするのようなケースです。次のケースではレコードを受け取り、nameで比較し等しければ`age`で比較、そうでなければnameで比較をします。このとき`comparable`型で`Order`型を算出するにはどうするでしょうか。その場合には、[compare](https://package.elm-lang.org/packages/elm/core/latest/Basics#compare)関数に2つの`comparable`型の値を渡すだけです。

```elm
type alias User =
    { name : String, age : Int }


userComparison : User -> User -> Order
userComparison u1 u2 =
    if u1.name == u2.name then
        compare u1.age u2.age

    else
        compare u1.name u2.name

> List.sortWith userComparison [ { name = "john", age = 15 }, { name = "alice", age = 20 }, { name = "john", age = 13 } ]
[{ age = 20, name = "alice" },{ age = 13, name = "john" },{ age = 15, name = "john" }]
```

### sort関数とはつまり

sortWith関数には次のような興味深い一文があります。sortWithにcompare関数を渡せば結果はsort関数の結果と等しくなります。つまり、compareを実装すれば全ての型が`comparable`型になれるということになります。

> This is also the most general sort function, allowing you to define any other: sort == sortWith compare

### 降順のソート

sortWithを使って、もし降順にソートしたい場合はどうするでしょうか？ 一つはsort後にリストを`List.reverse`を渡す方法が思いつきます。しかし、これはパフォーマンス的には2度Listを操作してしまうために効率的とは言えませんし、毎回reverseをするのは冗長です。これを一発でやるには、LTとGTを逆転させてあげれば降順に並ぶことになります。

```elm 
flippedComparison a b =
    case compare a b of
      LT -> GT
      EQ -> EQ
      GT -> LT
```