余積 

双対としてよく知られているものに、積の双対である余積 (coproduct、「直和」とも) がある。双対を表すのに英語では頭に “co-” を、日本語だと「余」を付ける。

以下に積の定義を再掲する:

定義 2.15. 任意の圏 C において、対象 A と B の積の図式は対象 P と射 p₁ と p₂ から構成され

以下の UMP を満たす:

この形となる任意の図式があるとき

次の図式

が可換となる (つまり、x₁ = p₁ u かつ x₂ = p₂ u が成立する) 一意の射 u: X => P が存在する。

矢印をひっくり返すと余積図式が得られる:

余積は同型を除いて一意なので、余積は A + B、u: A + B => X の射は [f, g] と表記することができる。

「余射影」の i₁: A => A + B と i₂: B => A + B は、単射 (“injective”) ではなくても「単射」 (“injection”) という。

「埋め込み」(embedding) ともいうみたいだ。積が scala.Product などでエンコードされる直積型に関係したように、余積は直和型 (sum type, disjoint union type) と関連する。

代数的データ型 

A + B をエンコードする最初の方法は sealed trait と case class を使う方法だ。

sealed trait XList[A]

object XList {
  case class XNil[A]() extends XList[A]
  case class XCons[A](head: A, rest: XList[A]) extends XList[A]
}

XList.XCons(1, XList.XNil[Int])
// res0: XList.XCons[Int] = XCons(head = 1, rest = XNil())

余積としての Either データ型 

目をすくめて見ると Either を直和型だと考えることもできる。Either の型エイリアスとして |: を定義する:

type |:[+A1, +A2] = Either[A1, A2]

Scala は型コンストラクタに中置記法を使えるので、Either[String, Int] の代わりに String |: Int と書けるようになった。

val x: String |: Int = Right(1)
// x: String |: Int = Right(value = 1)

ここまでは普通の Scala 機能しか使っていない。Cats は単射 i₁: A => A + B と i₂: B => A + B を表す cats.Injection という型クラスを提供する。これを使うと Left と Right を気にせずに coproduct を作ることができる。

import cats._, cats.data._, cats.syntax.all._

val a = Inject[String, String |: Int].inj("a")
// a: String |: Int = Left(value = "a")

val one = Inject[Int, String |: Int].inj(1)
// one: String |: Int = Right(value = 1)

値を再取得するには prj を呼ぶ:

Inject[String, String |: Int].prj(a)
// res1: Option[String] = Some(value = "a")

Inject[String, String |: Int].prj(one)
// res2: Option[String] = None

apply と unapply を使って書くときれいに見える:

lazy val StringInj = Inject[String, String |: Int]

lazy val IntInj = Inject[Int, String |: Int]

val b = StringInj("b")
// b: String |: Int = Left(value = "b")

val two = IntInj(2)
// two: String |: Int = Right(value = 2)

two match {
  case StringInj(x) => x
  case IntInj(x)    => x.show + "!"
}
// res3: String = "2!"

|: にコロンを入れた理由は右結合にするためで、3つ以上の型を使うときに便利だからだ:

val three = Inject[Int, String |: Int |: Boolean].inj(3)
// three: String |: Int |: Boolean = Right(value = Left(value = 3))

見ての通り、戻り値の型は String |: (Int |: Boolean) となった。

Curry-Howard エンコーディング 

関連して Miles Sabin (@milessabin) さんの Unboxed union types in Scala via the Curry-Howard isomorphism も興味深い。

Shapeless.Coproduct 

Shapeless の Coproducts and discriminated unions も参考になる。

EitherK データ型 

Cats には EitherK[F[_], G[_], A] というデータ型があって、これは型コンストラクタにおける Either だ。

Data types à la carte で、Wouter Swierstra (@wouterswierstra) さんがこれを使っていわゆる Expression Problem と呼ばれているものを解決できると解説している。

今日はここまで。