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する必要がある。

なぜこれでうまくいくのかについては、ググれば出てくる気がするのでそっちを参照。

半群やモノイドについて詳しく知りたい方は、筆者の書いた

Haskellerのためのモノイド完全ガイド

を読むと良い。

データ構築子のフィールドを省略する

複数のデータ構築子を持つ型の順序の定義で、異なるデータ構築子（タグ）の順序はフィールドに依存せずに決まるという場合がある。例えば、

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)

と実装できる。

HaskellでOrdインスタンスを書くときの小技3選

辞書式順序と Ordering

データ構築子のフィールドを省略する

反対称性を使う

辞書式順序と `Ordering`