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

定義と例

Wikipediaによれば、集合$P$上の２要素について以下の３つの条件を満たす二項関係$\preceq$を、数学用語で半順序 という。

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

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

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

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

自然数と整除

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

  type Nat = Int Refined Positive

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

  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で定義されている。

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

  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で、相等関係の代入原理の検証のために使われる。ここでは与えられた自然数に適当な整数を加算して別の自然数を返す関数として定義した。

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

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期間もあり、全順序ではない。

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

  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

テストコードも同様に書ける。

  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では全順序でない半順序集合の例として集合{1, 2, 3}の冪集合の包含関係が例示されているが、要素の型は別に数でなくても構わないため、ここではファイルのパーミッション{Exec, Read, Write}で考えてみる。例えばReadはRead+Writeに含まれると言えるが、Read+Execが含まれるとは言えない。

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

  opaque type Permission = Int

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

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

  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

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

  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 でも書けるが）。

  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
ライブラリバージョン等: build.sbt

メモ

他の例として、「小田急線で新宿駅からa駅を通ってb駅に着く」を挙げている資料もある。おなじ構造で考えると、たとえば進化系統樹上の、生物Aと生物Bの祖先-子孫関係も半順序関係だと思われる。
Wikipediaから引用
「任意の半順序集合は、任意の射集合が高々一つの元からなる圏とみなすことができる。」
「半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。
サンプルを Scala 3 に書き換えた (2022-07-31)