Coproducts 

One of the well known dual concepts 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 p₁ and p₂

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 x₁ = p₁ u and x₂ = p₂ 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” i₁: A => A + B and i₂: 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 union type, like this:

data TrafficLight = Red | Yellow | Green

Unboxed union types 

Using case class and sealed traits as encoding for this doesn’t work well in some cases like if I wanted a union of Int and String. An interesting read on this topic is Miles Sabin (@milessabin)’s Unboxed union types in Scala via the Curry-Howard isomorphism.

Everyone’s seen De Morgan’s law:
!(A || B) <=> (!A && !B)
Since Scala has conjunction via A with B, Miles discovered that we can get disjunction if we can encode negation. This is ported to Scalaz under scalaz.UnionTypes:

trait UnionTypes {
  type ![A] = A => Nothing
  type !![A] = ![![A]]

  trait Disj { self =>
    type D
    type t[S] = Disj {
      type D = self.D with ![S]
    }
  }

  type t[T] = {
    type t[S] = (Disj { type D = ![T] })#t[S]
  }

  type or[T <: Disj] = ![T#D]

  type Contains[S, T <: Disj] = !![S] <:< or[T]
  type ∈[S, T <: Disj] = Contains[S, T]

  sealed trait Union[T] {
    val value: Any
  }
}

object UnionTypes extends UnionTypes

Let’s try implementing Miles’s size example:

scala> import UnionTypes._
import UnionTypes._

scala> type StringOrInt = t[String]#t[Int]
defined type alias StringOrInt

scala> implicitly[Int ∈ StringOrInt]
res0: scalaz.UnionTypes.∈[Int,StringOrInt] = <function1>

scala> implicitly[Byte ∈ StringOrInt]
<console>:18: error: Cannot prove that Byte <:< StringOrInt.
              implicitly[Byte ∈ StringOrInt]
                        ^

scala> def size[A](a: A)(implicit ev: A ∈ StringOrInt): Int = a match {
         case i: Int    => i
         case s: String => s.length  
       }
size: [A](a: A)(implicit ev: scalaz.UnionTypes.∈[A,StringOrInt])Int

scala> size(23)
res2: Int = 23

scala> size("foo")
res3: Int = 3

\/ 

Scalaz also has \/, which could be thought of as a form of sum type. The symbolic name \/ kind of makes sense since ∨ means the logical disjunction. This was covered in day 7: \/. We can rewrite the size example as follows:

scala> def size(a: String \/ Int): Int = a match {
         case \/-(i) => i
         case -\/(s) => s.length  
       }
size: (a: scalaz.\/[String,Int])Int

scala> size(23.right[String])
res15: Int = 23

scala> size("foo".left[Int])
res16: Int = 3

Coproduct and Inject 

There is actually Coproduct in Scalaz, which is like an Either on type constructor:

final case class Coproduct[F[_], G[_], A](run: F[A] \/ G[A]) {
  ...
}

object Coproduct extends CoproductInstances with CoproductFunctions

trait CoproductFunctions {
  def leftc[F[_], G[_], A](x: F[A]): Coproduct[F, G, A] =
    Coproduct(-\/(x))

  def rightc[F[_], G[_], A](x: G[A]): Coproduct[F, G, A] =
    Coproduct(\/-(x))

  ...
}

In Data types à la carte Wouter Swierstra (@wouterswierstra) describes how this could be used to solve the so-called Expression Problem:

The goal is to define a data type by cases, where one can add new cases to the data type and new functions over the data type, without recompiling existing code, and while retaining static type safety.

The automatic injections described in this paper was contributed to Scalaz in #502 by @ethul. An example of how this could be used is available in his typeclass-inject’s README.

Individual expressions construct Free[F, Int] where F is the coproduct of all three algebras.