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

HaskellでOrdインスタンスを手書きする場合の小技を紹介する。

# 辞書式順序と `Ordering`

複数のフィールドに対して辞書式比較したい時は、 `<>` を使うと良い。

例：

```haskell
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のためのモノイド完全ガイド](https://blog.miz-ar.info/2019/02/monoid-for-haskellers/)

を読むと良い。

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

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

```haskell
data Bar = B Int Double Int
         | C String
```

という型に対して、タグ `B` を持つ値（`B _ _ _`）よりもタグ `C` を持つ値（`C _`）の方が常に大きいという場合である。

その場合は

```haskell
instance Ord Bar where
  ...
  compare (B _ _ _) (C _) = LT
  ...
```

という風にフィールドをワイルドカード `_` にマッチさせるという書き方をすることが多いかと思うが、フィールドがたくさんあるとこれは面倒だし、フィールドを増やしたり減らしたりした時に不必要に変更箇所が増える。

そういう時は、空のレコードパターン（という呼び名でいいのか？）を使うと良い。

```haskell
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`

となる。

さて、複数のデータ構築子の間に非自明な順序が定まっている場合を考えよう。

```haskell
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`）ことによってコードの重複をなくす、というのは誰でも思いつくだろう。

愚直に書けばこうだ：

```haskell
  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` のインスタンスを実装する側で前者をやってしまうと無限再帰に陥ってしまう。

```haskell
  compare lhs@E{} rhs@D{} = compare lhs rhs -- compare rhs lhs の逆（ダメな例）
```

また、 `Down` の実装によっては `compare (Down x) (Down y) = compare y x` と定義されているため、 `Down` を使ったやり方も使えない。

```haskell
  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通りそれぞれ考えると

```haskell
compare EQ LT = GT  -- EQ > LT なので
compare EQ EQ = EQ  -- EQ == EQ なので
compare EQ GT = LT  -- EQ < GT なので
```

となり、 `compare EQ` によって確かに `LT` と `GT` が逆転する。

よって、 `compare EQ` を使って

```haskell
  compare (D ...) (E ...) = ... -- 実装
  compare lhs@E{} rhs@D{} = compare EQ (compare rhs lhs)
```

と実装できる。