この記事では、ElmのListのソート方法について解説をしていきます。Listのソートを覚えれば、外部APIなどから受け取った値の列をユーザに見せたい順番で並び替えたり、テーブルを表現したときに並び替えボタンの実装などをするときには必須です。それではソート方法について見ていきましょう。
List.sort関数
それでは、List.sort関数を使ってIntのListを並び替えてみましょう。はい。並び替えができました。これでもう並び替えは完璧ですね！
> List.sort [ 3, 1, 2 ]
[1,2,3] : List number
...ですが、sort関数を覚えるだけでは全てのListについて並び替えができるわけではありません。例えば、以下のようなレコードを渡すとコンパイルエラーになります。エラーの内容としては、sort関数の第一引数には、List comparable型を渡す必要があります。となっています。
> 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ガイドでは、制約付き型変数(Constrained Type Variables)と言われます。制約付き型変数は、型変数に取れる型に制限があるものを指します。言い換えれば、制約付き型変数は限られた型を集めたもの(有限個の型の集合)になります。ガイドから抜粋すると、comparableに当てはまる型は以下になります。
comparableにはIntかFloat,Char,String,そしてcomparableな値で構成されるリストまたはタプルを当てはめられます
comparableな値で構成されるリストまたはタプルをsortした例が以下になります。リスト・タプルいずれも前から順番にソート対象になるというわけですね。
> List.sort [(1, "b"), (1, "a")]
[(1,"a"),(1,"b")] : List ( number, String )
> List.sort [['e', 'l', 'm'], ['e', 'l', 'l', 'i', 'e']]
[['e','l','l','i','e'],['e','l','m']]
: List (List Char)
sortBy関数
レコードはなぜsort関数に渡せないのでしょうか？ それは、レコード型のどのキーに対応する値を使って並び替えするかがわからないためです。sortBy関数はあるデータ型からcomparable型の値を指定(sortBy: (a -> comparable) -> List a -> List a)を取り出しその値で並び替えることができます。以下は、それぞれname: Stringとage: Intで並び替える例です。つまりこの場合、Stringとageがcomparableな型として成立しています。.nameはレコードのアクセス関数なので次のラムダ式が正式な書き方になります。(\r -> r.name)今回の例はレコード型ですが、最終的にcomparableな型を指定できればどんな型でも対応できます。
> 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関数
sortBy関数はある値からcomparable型の値を取り出すことで並び替えることができていました。しかし、comparableではない型を並び替えたい時はどうするでしょうか。その場合はsortWith関数を使います。
カスタムタイプのソート
comparableではない型の代表としてカスタムタイプ(ユーザ定義の独自型)が挙げられます。例えば、降順で松竹梅の順になるJapaneseRankという型を考えてみましょう。sortWith関数は、ソート対象のList と 2つの対象となる型を受け取り、Order型を返す関数を引数に受け取ります。Order型は(LT, GT, EQ)3つの値を持ちます。梅 < 松が成り立つ時LT(Less)を返します。逆に松 > 竹が成り立つ時GT(Greater)を返します。最後に、梅 == 梅が成り立つときにEQを返します。一番抜け漏れがない方法は2つの値をタプルにしてパターンマッチし、機械的にLT, GT, EQを当てはめていきます。もし漏れがあればコンパイラが教えてくれます。少しかったるいですが、頑張って埋めましょう。
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関数に2つのcomparable型の値を渡すだけです。
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を逆転させてあげれば降順に並ぶことになります。
flippedComparison a b =
case compare a b of
LT -> GT
EQ -> EQ
GT -> LT