HaskellでOrdインスタンスを手書きする場合の小技を紹介する。
辞書式順序と Ordering
複数のフィールドに対して辞書式比較したい時は、 <> を使うと良い。
例：
data Foo = A Int Double Int
instance Ord Foo where
compare (A x y z) (A x' y' z') = compare x x' <> compare y y' <> compare z z'
<> は半群やモノイドの「くっつける」演算子である。最近のGHCでは <> はPreludeからエクスポートされているが、それ以前のGHCでは Data.Semigroup か Data.Monoid をimportする必要がある。
なぜこれでうまくいくのかについては、ググれば出てくる気がするのでそっちを参照。
半群やモノイドについて詳しく知りたい方は、筆者の書いた
を読むと良い。
データ構築子のフィールドを省略する
複数のデータ構築子を持つ型の順序の定義で、異なるデータ構築子（タグ）の順序はフィールドに依存せずに決まるという場合がある。例えば、
data Bar = B Int Double Int
| C String
という型に対して、タグ B を持つ値（B _ _ _）よりもタグ C を持つ値（C _）の方が常に大きいという場合である。
その場合は
instance Ord Bar where
...
compare (B _ _ _) (C _) = LT
...
という風にフィールドをワイルドカード _ にマッチさせるという書き方をすることが多いかと思うが、フィールドがたくさんあるとこれは面倒だし、フィールドを増やしたり減らしたりした時に不必要に変更箇所が増える。
そういう時は、空のレコードパターン（という呼び名でいいのか？）を使うと良い。
instance Ord Bar where
...
compare B{} C{} = LT
compare C{} B{} = GT
...
この記法はGHC拡張ではなく、素のHaskellで利用できる。
反対称性を使う
Ord の定める順序は反対称性を持っていることが期待される。compare の言葉で書けば、
-
compare x y == LTならばcompare y x == GT -
compare x y == GTならばcompare y x == LT
となる。
さて、複数のデータ構築子の間に非自明な順序が定まっている場合を考えよう。
data Baz = D Rational Int
| E Double Int
instance Ord Baz where
...
compare (D x a) (E y b) = compare x (toRational y) <> compare a b -- 実装
compare (E x) (D x) = {- ↑とほとんど同じコードを書くのはだるい -}
...
この例では、 compare (E ...) (D ...) と compare (D ...) (E ...) がほぼ同じ処理で、結果（Ordering の値）だけが異なる。そういう場合、どちらかからもう一方の実装を呼んでその結果を反転させる（LT ↔︎ GT）ことによってコードの重複をなくす、というのは誰でも思いつくだろう。
愚直に書けばこうだ：
compare (D x a) (E y b) = ... -- 実装
compare lhs@E{} rhs@D{} = case compare rhs lhs of
LT -> GT
EQ -> EQ
GT -> LT
だが、このために4行も書くのはだるい。compare x y の比較結果を逆にするもっと簡単な方法が欲しい。
Ord を利用する側からしたら、 compare x y の比較結果を逆にしたものが欲しいなら compare y x を呼ぶなり Down 型を使って compare (Down x) (Down y) を呼ぶという手がある。しかし、 Ord のインスタンスを実装する側で前者をやってしまうと無限再帰に陥ってしまう。
compare lhs@E{} rhs@D{} = compare lhs rhs -- compare rhs lhs の逆（ダメな例）
また、 Down の実装によっては compare (Down x) (Down y) = compare y x と定義されているため、 Down を使ったやり方も使えない。
compare (D ...) (E ...) = {- 実装 -}
compare lhs@E{} rhs@D{} = compare (Down rhs) (Down lhs)
{- ↑
Down の実装が
compare (Down x) (Down y) = case compare x y of LT -> GT; EQ -> EQ; GT -> LT
なら動作するが、 Down の実装が
compare (Down x) (Down y) = compare y x
なら無限再帰に陥る
-}
Bool に対する not のような、 Ordering を反転させる便利な関数があればよいのだが、 Data.Ord を覗いてみても使えそうな関数は見当たらない。諦めて case .. of を書くしかないのだろうか？
いいや、手はある。
Ordering 自体が Ord のインスタンスになっており、 LT < EQ < GT という順序が入っていることを使うと、 compare EQ :: Ordering -> Ordering という関数によって Ordering の値を逆転できる。
実際、3通りそれぞれ考えると
compare EQ LT = GT -- EQ > LT なので
compare EQ EQ = EQ -- EQ == EQ なので
compare EQ GT = LT -- EQ < GT なので
となり、 compare EQ によって確かに LT と GT が逆転する。
よって、 compare EQ を使って
compare (D ...) (E ...) = ... -- 実装
compare lhs@E{} rhs@D{} = compare EQ (compare rhs lhs)
と実装できる。