Scalaの型で有界半束（BoundedSemilattice）を作ってみる

「[圏論勉強会第2回](http://nineties.github.io/category-seminar/2.html#/18)」資料を読んでたら「有界半束はモノイドである」というフレーズがあった。この辺りの Cats 実装を調べてみると、以下のような継承関係になっている。

![boundedsemigroup-inheritance.png](https://qiita-image-store.s3.amazonaws.com/0/9633/3a104152-259d-6561-ba49-338e7435ed1b.png)

この記事では有界半束`BoundedSemilattice`を調べて実装してみる。[前の記事](https://qiita.com/yasuabe2613/items/fd9a8961b0301d4d64f5)に書いた`PartialOrder`も利用する。

### 使ってる技術など
Cats、Discipline、束論初歩と、Scalaのリフレクションを少々。

### 依存ライブラリ
- **cats**: 2.0.0-M1
- **specs2**: 4.3.6
- **scalacheck**: 1.14.0

（[ソースはこちら](https://gist.github.com/yasuabe/21fa9e487eb43b27eb34b8f4e1538352)）

## 有界半束
そもそも有界半束とは何か。馴染みがないので[Wikipediaの束論](https://ja.wikipedia.org/wiki/%E6%9D%9F_(%E6%9D%9F%E8%AB%96))のエントリと「[順序集合と束](http://www.hongo.wide.ad.jp/~jo2lxq/dm/lecture/03.pdf)」という離散数学の資料でしらべてみた。

下の図のように、半順序集合内の比較可能な二つの要素を、大きい方を上にして線でつなげたとき、ある二つの要素から上向きに辿っていける領域の交差部分を**上界**という。

上界の中で最小のものが**もしあれば**それを**結び（join）**といい $a \lor b$ と表し、どの２つの要素をとっても結びがあるとき、この集合を**結び半束** (join-semilattice) という。

向きを下にとった場合は、上界→**下界**、結び（join）→**交わり (meet) ** $a \land b$、**結び半束**→**交わり半束**となる。また、結び半束かつ交わり半束であるものを**束**といい、最小要素と最大要素をもつ束のことを**有界束**という。

![lattice.png](https://qiita-image-store.s3.amazonaws.com/0/9633/92492d70-f180-f605-f443-e64c0e2c694b.png)

図の左では、青と赤の上界に最小要素の緑が一つだけあり、これが結びとなる。ただし線を１本加えた図の右では、二つの緑のうちどちらが上界の最小か定まらないので結びがあるといえず、したがって右は半束にならない。

これらを踏まえて、Scala コードを書いてみる。

## 実装例

以降、`trait`の継承関係から半順序集合を作り、これを結びの有界半束として実装し、`Discipline`で各種の法則に準拠しているか検証する。

### 半順序(PartialOrder)

以下のように`trait`を定義する。

```scala
  trait A; trait B; trait C
  trait D extends B; trait E extends B with C
```
下図の左のような継承関係になる。

![boundedsemilattice.png](https://qiita-image-store.s3.amazonaws.com/0/9633/53389a27-4e25-4cf3-d2b4-f71d6f2da0bc.png)

これらに共通の基底クラスと`AnyRef`と、結び半束の単位元となる最小元`Nothing`を加えると、上図中央のような[ハッセ図](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%BB%E5%9B%B3)になる。ちなみに、もし`D`が`C`をも継承していると上図右のようになり、`D`と`E`の結びがなくなるため有界半束にならない。

これらの型を半順序集合とする`PartialOrder`インスタンスを以下のように定義する。

```scala
implicit val typePartialOrder: PartialOrder[Type] = (x: Type, y: Type) =>
  (x <:< y, y <:< x) match {
    case (true, true) => 0.0
    case (true, _)    => -1.0
    case (_   , true) => 1.0
    case _            => Double.NaN
  }
```
`<:<`は`TypeApi`で定義されていている演算子で、左辺の型が右辺の型に適合する（等しいか継承している）場合に`true`となる。

半順序の法則を満たしているかどうか、以下のようにテストできる。

```scala
  implicit def arbType: Arbitrary[Type] = Arbitrary(
    Gen.oneOf(typeOf[Any], typeOf[A], typeOf[B], typeOf[C], typeOf[D], typeOf[E], typeOf[Nothing]))

  private val checkTypePartialOrder = {
    implicit val arbF: Arbitrary[Type => Type] = Arbitrary(Gen.const(t => t))
    checkAll("型の半順序集合", PartialOrderTests[Type].partialOrder)
  }
```
任意の型`arbType`はハッセ図上の型から一つ選択する。任意関数`arbF`は「相等性の代入原理」のチェックで使うが、この記事の内容とあまり関係がないので適当にした。


### 有界半束(BoundedSemilattice)

半順序集合になっていることが確認できたので、有界半束を実装してみる。`BoundedSemilattice`のインスタンスを作るには、`Semigroup`で宣言されている`combine`と、`Monoid`で宣言されている`empty`を実装する必要があるが、それぞれ「結び」と最小値`Nothing`に対応づける。

```scala
  implicit val typeBoundedSemilattice: BoundedSemilattice[Type] = new BoundedSemilattice[Type] {
    val empty: Type = typeOf[Nothing]

    def superTypesOf(t: Type): Set[Type] = t.baseClasses.map(t.baseType).toSet + t

    def combine(x: Type, y: Type): Type =
      if      (x == empty) y
      else if (y == empty) x else
        (superTypesOf(x) intersect superTypesOf(y))
          .toList
          .sortWith((x, y) => x <= y) match {
            case h  :: Nil     => h
            case h1 :: h2 :: _ =>
              assert((h1 tryCompare h2).nonEmpty, "結びがない！")
              h1
    }
  }
```
`Type`を得るための`typeOf`は、`import scala.reflect.runtime.universe._`で使えるようになる。結びの実装では`Type#baseClasses`で得た基底クラス集合の共通部分を`PartialOrder`で並べ替えて、先頭要素を返している。ただし、2番目の要素と比較不能な場合には、`AssertionError`を返すようにした。

これも Cats で提供されているルールを使って、Discipline で検証できる。

```scala
  private val checkTypeBoundedSemilattice =
    checkAll("型の有界半束", BoundedSemilatticeTests[Type].boundedSemilattice)
```

specs2で実行すると以下のような出力を得る。PartialOrderの部分は[前回](https://qiita.com/yasuabe2613/items/fd9a8961b0301d4d64f5)とかぶるので割愛した(コメントは後で書き足したもの)。

```
boundedSemilattice.associative      // Semigroup law
boundedSemilattice.collect0         // Monoid law
boundedSemilattice.combine all      // Monoid law
boundedSemilattice.combineAllOption // Semigroup law
boundedSemilattice.commutative      // CommutativeSemigroup law
boundedSemilattice.idempotency      // Band law
boundedSemilattice.is id            // Monoid law
boundedSemilattice.left identity    // Monoid law
boundedSemilattice.repeat0          // Monoid law
boundedSemilattice.repeat1          // Semigroup law
boundedSemilattice.repeat2          // Semigroup law
boundedSemilattice.right identity   // Monoid law

Process finished with exit code 0
```
ためしに`D`が`C`も継承するようにしてから再テストすると、アサーションが失敗して”結びがない”旨のエラーメッセージが出力されることがわかる。

ちなみに、冒頭の`BoundedSemilattice`そのものを含むクラス図も、`AnyRef`と`Nothing`を加えるとそれ自身有界半束となり Discipline テストも成功する。

## まとめ
やっぱり有界半束はモノイドだった