Coproduct

One of the well known duals is coproduct, which is the dual of product. Prefixing with “co-” is the convention to name duals.

Here’s the definition of products again:

Definition 2.15. In any category C, a product diagram for the objects A and B consists of an object P and arrows p1 and p2

satisfying the following UMP:

Given any diagram of the form

there exists a unique u: X => P, making the diagram

commute, that is, such that x1 = p1 u and x2 = p2 u.

Flip the arrows around, and we get a coproduct diagram:

Since coproducts are unique up to isomorphism, we can denote the coproduct as A + B, and [f, g] for the arrow u: A + B => X.

The “coprojections” i1: A => A + B and i2: B => A + B are usually called injections, even though they need not be “injective” in any sense.

Similar to the way products related to product type encoded as `scala.Product`, coproducts relate to the notion of sum type, or disjoint union type.

Algebraic datatype

First way to encode A + B might be using sealed trait and case classes.

``````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 datatype as coproduct

If we squint `Either` can be considered a union type. We can define a type alias called `|:` for `Either` as follows:

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

Because Scala allows infix syntax for type constructors, we can write `Either[String, Int]` as `String |: Int`.

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

Thus far I’ve only used normal Scala features only. Cats provides a typeclass called `cats.Inject` that represents injections i1: A => A + B and i2: B => A + B. You can use it to build up a coproduct without worrying about Left or Right.

``````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)``````

To retrieve the value back you can call `prj`:

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

We can also make it look nice by using `apply` and `unapply`:

``````scala> val StringInj = Inject[String, String |: Int]
StringInj: cats.Inject[String,String |: Int] = cats.InjectInstances\$\$anon\$2@3e67ae9
scala> val IntInj = Inject[Int, String |: Int]
IntInj: cats.Inject[Int,String |: Int] = cats.InjectInstances\$\$anon\$3@6a9628bb
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!``````

The reason I put colon in `|:` is to make it right-associative. This matters when you expand to three types:

``````scala> val three = Inject[Int, String |: Int |: Boolean].inj(3)
three: String |: (Int |: Boolean) = Right(Left(3))``````

The return type is `String |: (Int |: Boolean)`.

Curry-Howard encoding

An interesting read on this topic is Miles Sabin (@milessabin)’s Unboxed union types in Scala via the Curry-Howard isomorphism.

Shapeless.Coproduct

There’s a datatype in Cats called `EitherK[F[_], G[_], A]`, which is an either on type constructor.