半順序〜PartialOrder の実装例と Discipline テスト

半順序の定義と例を調べて、実装サンプルと法則への準拠テストを書いた。Cats と Discipline と refined 等を使った。

## 定義と例

[Wikipedia](https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88#%E5%89%8D%E9%A0%86%E5%BA%8F%E3%83%BB%E5%8D%8A%E9%A0%86%E5%BA%8F%E3%83%BB%E5%85%A8%E9%A0%86%E5%BA%8F)によれば、集合$P$上の２要素について以下の３つの条件を満たす二項関係$\preceq$を、数学用語で**半順序** という。

1. 反射律 : $a \preceq a$
2. 推移律 : $a \preceq b$ かつ $b \preceq c$ ならば $a \preceq c$
3. 反対称律 : $a \preceq b$ かつ $b \preceq a$ ならば $a$ と $b$ は等しい

ここで、１と２だけ成り立つものを**前順序**といい、１〜３に加えてさらに$P$上のどの要素ペアについてもこの二項関係があるとき、**全順序**という。二項関係$\preceq$は、数の「大なりイコール」とは限らず、あとで見るようにいろいろな例がある。

Cats で提供されている`PartialOrder`はこの半順序の実装で、そのメソッド`tryCompare`は二つの要素を**もし可能ならば**比較して、その結果を Option に入れて返す。

ただし Scala の数値型の大小関係の`PartialOrder`は、比較できないペアを含まない全順序`Order`なので、`PartialOrder`の例としてはあまり面白くない。以下、全順序ではない半順序を選んでコードを書いてみる。

## 自然数と整除
自然数$a$, $b$について、$a$が$b$を割り切ることを$a|b$ と書くとすると、(1)「$a | a$」、(2)「$a|b$ かつ $b|c$ ならば $a|c$」、(3)「$a|b$ かつ $b|a$ ならば $a=a$」が成り立ち、また$a|b$でも$b|a$でもない組み合わせもあることから、自然数の整除関係は、全順序ではない半順序といえる。これを Scala で書いてみる。

まず自然数は refined を用いて次のように書ける。

```scala
  type Nat = Int Refined Positive
```

この`Nat`の`PartialOrder`インスタンスは次のように書ける。

```scala
  given PartialOrder[Nat] = (a: Nat, b: Nat) =>
    val compare = (_: Nat).value % (_: Nat).value
    (compare(a, b), compare(b, a)) match
      case (0, 0) =>  0.0
      case (0, _) => -1.0
      case (_, 0) =>  1.0
      case _      => Double.NaN
```
SAM で `PartialOrder#partialCompare`を実装している。二つの自然数の間に整除関係がある場合にはその向きを表す正か負の数またはゼロを、整除関係がない場合は`NaN`を返す。

このインスタンスが半順序の法則を満たしているかどうか、Cats で提供されている`PartialOrderTests`を使って確かめることができる。法則自体は`PartialOrderLaws`で定義されている。

テストに使う「任意の自然数」の生成も含めて、以下のように書いてみた。ただし「任意の自然数」といっても桁あふれまで考えるとややこしいので、ここでは小さな数の範囲に収めた。

```scala
  val smallIntGen = Gen.chooseNum[Int](1, 100)

  given Arbitrary[Nat] = Arbitrary(
    smallIntGen.map(refineV[Positive](_).toOption.get))

  given Arbitrary[Nat => Nat] =
    Arbitrary(smallIntGen.map(n => nat => refineV[Positive](nat.value + n).toOption.get))

  checkAll("nat divisibility", PartialOrderTests[Nat].partialOrder)
```

`arbF: Arbitrary[Nat => Nat]`は、`PartialOrderTests`が継承している`EqTests`で、[相等関係の代入原理](https://ja.wikipedia.org/wiki/%E7%AD%89%E5%BC%8F#%E5%B0%8E%E5%85%A5)の検証のために使われる。ここでは与えられた自然数に適当な整数を加算して別の自然数を返す関数として定義した。



実行すると以下のような出力が得られる（コメントはあとから追記したもの）。

```
partialOrder.antisymmetry     // 反対称律（a≦b ∧ b≦a ⇒ a=b）
partialOrder.gt               // PartialOrder#gt
partialOrder.gteqv            // PartialOrder#gteqv
partialOrder.lt               // PartialOrder#lt
partialOrder.partialCompare   // PartialOrder#partialCompare
partialOrder.pmax             // PartialOrder#pmax
partialOrder.pmin             // PartialOrder#pmin
partialOrder.reflexitivity    // 反射律（a==a）
partialOrder.reflexitivity gt // 反射律（a>=a）
partialOrder.reflexitivity lt // 反射律（a<=a）
partialOrder.symmetry         // 相等関係の対称律（a=b ⇒ b=a）
partialOrder.transitivity     // 推移律（a≦b ∧ b≦c ⇒ a≦c）

Process finished with exit code 0
```

## 期間と包含関係
始まりと終わりの二つの日付からなる期間の包含関係も、反射律・推移律・反対称律を満たし、半順序となる。ただし、2〜5月と1〜3月など包含関係のない2期間もあり、全順序ではない。

自然数の整除と同様にインスタンスを定義すると以下のようになる。似たようなコードなので共通の構造を抽出することもできるが、さしあたりこのままにしておく。

```scala
  case class FromTo(from: LocalDate, to: LocalDate)

  given PartialOrder[FromTo] = (a: FromTo, b: FromTo) =>
    val compare = (inner: FromTo, outer: FromTo) =>
      !(inner.from isBefore outer.from) && !(outer.to isAfter inner.to)

    (compare(a, b), compare(b, a)) match
      case (true, true) =>  0.0
      case (true, _   ) => -1.0
      case (_   , true) =>  1.0
      case _            => Double.NaN
```
テストコードも同様に書ける。

```scala
  val d0 = LocalDate.of(2018, 1, 1)

  given Arbitrary[FromTo] = Arbitrary(
    for
      offset <- Gen.chooseNum(0, 11)
      period <- Gen.chooseNum(1, 12 - offset)
    yield FromTo(d0.plus(offset, MONTHS), d0.plus(offset + period, MONTHS).minus(1, DAYS)))

  given Arbitrary[FromTo => FromTo] =
    Arbitrary(smallIntGen.map(n => ft => FromTo(ft.from.plus(n, DAYS), ft.to.plus(n, DAYS))))

  checkAll("period inclusion", PartialOrderTests[FromTo].partialOrder)
```
`Arbitrary[FromTo]`は、2018年に含まれる 1〜12ヶ月の任意の期間とした。また`arbF`では日付を適当にずらしている。

## アクセス権限の包含関係

[Wikipedia](https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88#%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88%E3%81%AE%E4%BE%8B)では全順序でない半順序集合の例として集合{1, 2, 3}の冪集合の包含関係が例示されているが、要素の型は別に数でなくても構わないため、ここではファイルのパーミッション{`Exec`, `Read`, `Write`}で考えてみる。例えば`Read`は`Read+Write`に含まれると言えるが、`Read+Exec`が含まれるとは言えない。

まず`Permission`のコードは以下のように書いてみた。

```scala
  opaque type Permission = Int

  val Empty: Permission = 0
  val Exec : Permission = 1
  val Write: Permission = 2
  val Read : Permission = 4
```

これまでと同様に`PartialOrder[Permission]`も定義する。

```scala
  given PartialOrder[Permission] = (a: Permission, b: Permission) =>
    def compare(a: Permission, b: Permission) = (a | b) == b
    (compare(a, b), compare(b, a)) match
      case (true, true) =>  0.0
      case (true, _   ) => -1.0
      case (_   , true) =>  1.0
      case _            => Double.NaN
```

テストコードは以下のように書いた。

```scala
  val ifTrue = (p: Permission) => Gen.oneOf(true, false).map(if _ then Empty else p)

  given Arbitrary[Permission] =
    Arbitrary(List(Exec, Read, Write).foldMapM(ifTrue))

  given Arbitrary[Permission => Permission] =
    Arbitrary(Gen.chooseNum[Int](0, 7).map(n => p => Permission(n) + p))

  checkAll("permission inclusion", PartialOrderTests[Permission].partialOrder)
```
任意の`Permission`の生成では、３つの権限を並べたリストに対して、要素をランダムに`Empty`に置き換えた上で畳み込んでいる。そのために必要な`Monad[Gen]`と、`Monoid[Permission]`は、以下のように別途定義した（普通の for comprehension でも書けるが）。

```scala
  given Monoid[Permission] with
    val empty: Permission = Permission.Empty
    def combine(x: Permission, y: Permission): Permission = x + y

  given Monad[Gen] with    def pure[A](a: A): Gen[A] = Gen.const(a)
    def flatMap[A, B](fa: Gen[A])(f: A => Gen[B]): Gen[B] = fa flatMap f
    def tailRecM[A, B](a: A)(f: A => Gen[Either[A, B]]): Gen[B] =
      f(a).flatMap(_.fold(tailRecM(_)(f), pure))

```

## ソースと依存ライブラリ

ソースコード: [PartialOrderExerciseTest.scala](https://github.com/yasuabe/qiita-cats3-sample/blob/main/src/test/scala/partial_order/PartialOrderExerciseTest.scala)
ライブラリバージョン等: [build.sbt](https://github.com/yasuabe/qiita-cats3-sample/blob/main/build.sbt)

## メモ
- 他の例として、「小田急線で新宿駅からa駅を通ってb駅に着く」を挙げている[資料](http://web.sfc.keio.ac.jp/~kawazoe/math/book/d-chap6-2.pdf)もある。おなじ構造で考えると、たとえば進化系統樹上の、生物Aと生物Bの祖先-子孫関係も半順序関係だと思われる。
- [Wikipedia](https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88#%E5%9C%8F%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88)から引用
 - 「任意の半順序集合は、任意の射集合が高々一つの元からなる圏とみなすことができる。」
 - 「半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。
- サンプルを Scala 3 に書き換えた (2022-07-31)