余積 

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

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

定義 2.15. 任意の圏 C において、対象 A と B の積の図式は対象 P と射 p1 と p2 から構成され
product diagram
以下の UMP を満たす:

この形となる任意の図式があるとき
product definition
次の図式
product of objects
が可換となる (つまり、x1 = p1 u かつ x2 = p2 u が成立する) 一意の射 u: X => P が存在する。

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

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

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

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

代数的データ型 

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

scala> :paste
// Entering paste mode (ctrl-D to finish)
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]
}

// Exiting paste mode, now interpreting.
defined trait XList
defined object XList
scala> XList.XCons(1, XList.XNil[Int])
res5: XList.XCons[Int] = XCons(1,XNil())

余積としての Either データ型 

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

scala> type |:[+A1, +A2] = Either[A1, A2]
defined type alias $bar$colon

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

scala> val x: String |: Int = Right(1)
x: String |: Int = Right(1)

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

scala> import cats._, cats.data._, cats.implicits._
import cats._
import cats.data._
import cats.implicits._
scala> val a = Inject[String, String |: Int].inj("a")
a: String |: Int = Left(a)
scala> val one = Inject[Int, String |: Int].inj(1)
one: String |: Int = Right(1)

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

scala> Inject[String, String |: Int].prj(a)
res6: Option[String] = Some(a)
scala> Inject[String, String |: Int].prj(one)
res7: Option[String] = None

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

scala> val StringInj = Inject[String, String |: Int]
StringInj: cats.Inject[String,String |: Int] = cats.InjectInstances$$anon$2@3c0e66a8
scala> val IntInj = Inject[Int, String |: Int]
IntInj: cats.Inject[Int,String |: Int] = cats.InjectInstances$$anon$3@a894b28
scala> val b = StringInj("b")
b: String |: Int = Left(b)
scala> val two = IntInj(2)
two: String |: Int = Right(2)
scala> two match {
         case StringInj(x) => x
         case IntInj(x)    => x.show + "!"
       }
res8: String = 2!

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

scala> val three = Inject[Int, String |: Int |: Boolean].inj(3)
three: String |: (Int |: Boolean) = Right(Left(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 と呼ばれているものを解決できると解説している。

今日はここまで。

Contents

猫番
    1. 余積