More Algebra of Algebraic Data Types

Tony Morris, Thu Aug 20 2020

In our last post on Algebraic Data Types, we learned about addition, multiplication and exponentiation using data types. For example, we learned that we could add two data types, such as Boolean (2) by implementing a sum type:

sealed trait Four
case class This(b: Boolean) extends Four
case class That(b: Boolean) extends Four

We could multiply Four by 2 using a product type:

case class Eight(f: Four, t: Boolean)

And we could exponentiate using a function of the codomain to the power of the domain:

def sixtyfour(b: Boolean): Eight = ...

We explored some algebraic rules with data types. For example, the distributive rule of multiplication over addition being A(B + C) = AB + AC:

// A(B + C)
case class ThisSide[A, B, C](a: A, bc: Either[B, C])

// AB + AC
case class ThatSide[A, B, C](abac: Either[(A, B), (A, C)])

// ThisSide = ThatSide

In this post, we are going to take this further, by exploring other algebraic rules and seeing what insights this brings us. In particular, we are going to take the partial differentiation of a data type.

Remember calculus? Don't worry, neither do I, except when it is required for a practical application!

Let's start with a simple example. Suppose we have a data type, which is the product of three A:

case class ThreeOf[A](a1: A, a2: A, a3: A)

Algebraically, we can describe this data type as A³. Next, we are going to differentiate this data type with respect to A. Specifically, we are going to calculate:

∂/∂A. A³

If we apply the chain rule to the repeated multiplication, we arrive at:

∂/∂A. A³
∂/∂A. A * A * A
= 3 * A²
= 3 * A * A

Let's take this derivative to a data type and see what we have. First we will write a data type for 3, then the derivative:

sealed trait Three
case object OneOfThree extends Three
case object TwoOfThree extends Three
case object ThreeOfThree extends Three

case class ThreeOfDerivative[A](t: Three, a1: A, a2: A)

Hmm interesting, we have lost one of our A but we have gained some kind of "indicator" for the "three-ness" of our original data type.

Let's try a slightly less trivial example. Suppose this data type:

case class OneOrTwo[X](x: Either[X, (X, X)])

We will differentiate with respect to X. Algebraically, this data type corresponds to:

  OneOrTwo[X]
= X + X * X

Incidentally, we can also apply the distributive rule of multiplication to arrive at an equivalent data type:

  OneOrTwoAgain[X]
= (X + 1) * X

case class OneOrTwoAgain[X](x1: Option[X], x: X)

We may think of this data type as being either one X or two X.

Let's differentiate. We will first use the sum rule followed by the power rule and finally the line rule.

∂/∂X. X + X²
(∂/∂X. X) + (∂/∂X. X²)
(∂/∂X. X) + 2 * X
= 1 + (2 * X)

We have arrived at this data type:

case class OneOrTwoDerivative[X](x: Option[(Boolean, X)])

Once again, we are left with a data type that tells us one of three positions within the original data type, though one of the (up to two) X values is always missing:

not at X i.e. None
at one X i.e. Some(true, x)
at the other X i.e. Some(false, x)

What are we seeing here?

Let's try one more. Recall in the last post on Algebraic Data Types, we learned that:

List[A]
= 1 / (1 - A)
= (1 - A)^-1

Before we differentiate, let's try to get an intuition for what is going on here. We will do a thought experiment. Consider a list, and by that I mean, think of a list of values; any list. I will use the list of numbers [1,2,3,4,5,6,7], but you may pick your favourite list. Make it a physical list. Now, pick your favourite element in the list, walk to it, and stand on top of it. I have picked the element 5 in my list.

Look around, what do you see? I see a list to my left ([4,3,2,1]), a list to my right ([6,7]), and the element that I am standing on (5). If I were to consider only the context of a list element — that is, to not consider the element itself — that context is only a pair of lists; one to my left and another to my right.

Let's now differentiate a list. However, since removing the recursion in the algebraic representation of a list results in both a quotient and a subtraction, there is no simple way to encode this as a data type. We can skip this step and move straight to differentiating.

∂/∂A. (1 - A)^-1
= -(∂/∂A. (1 - A)) / (1 - A)²
line rule
= -(∂/∂A. 1 - ∂/∂A. A) / (1 - A)²
chain rule
= -(0 - 1) / (1 - A)²
derivative of constant = 0, derivative of variable = 1
= -(-1 / (1 - A)²)
= 1 / (1 - A)²
= (1 / (1 - A))²

We have arrived at the derivative of a List[A] being (1 / (1 - A))² or in other words, the derivative of a list with respect to its element type is a pair of lists!

When we were "standing" on a list element earlier, we can call this element "a hole", and the context when we looked around us, is a list to our left and a list to our right. When we calculate the derivative of a data type, we arrive at the one-hole context for that data type¹. In fact, if you take a closer look at any of the earlier derivatives, you'll see that they too, are the one-hole context for the original data type.

Why might we use this one-hole context? Consider this very simple use-case.

Moving from left to right, find the first even number in a list.
Divide that number by two, and add that value to the element
that is 1 position further along the list.
If there are no even numbers, or not enough elements,
leave the list alone (do nothing to it).

Naïvely, we could walk along the list, find the first even number, keep a track of its position and value, then use that position to walk one extra position away and update the element we find there. However, we would be manually keep track of context, deconstructing and reconstructing the list to achieve this goal; not to mention the extra list walking. Instead, we could create a data type that is the product of its derivative, and the "hole" that we are standing on:

case class ListCursor[A](left: List[A], hole: A, right: List[A]) {
  def moveRight: Option[ListCursor[A]] =
    right match {
      case Nil => None
      case h::t => Some(ListCursor(hole::left, h, t))
    }

  def findRight(pr: A => Boolean): Option[ListCursor[A]] =
    if(pr(hole))
      Some(this)
    else
      moveRight.flatMap(_ findRight pr)

  def modifyHole(k: A => A): ListCursor[A] =
    ListCursor(left, k(hole), right)

  def toList: List[A] =
    left.reverse ::: hole :: right
}

object ListCursor {
  def fromList[A](x: List[A]): Option[ListCursor[A]] =
    x match {
      case Nil => None
      case h::t => Some(ListCursor(Nil, h, t))
    }
}

We have written a few handy functions on our data type. In particular, we can convert to and from a List and we can navigate through each one-hole context (i.e. stand on different elements). Now that we have this data type, our use-case is quite simple, since it keeps a track of context for us.

def usecase(x: List[Int]): List[Int] = {
  val r =
    for {
      c1 <- fromList(x)
      c2 <- c1.findRight(_ % 2 == 0)
      c3 <- c2.moveRight
    } yield c3.modifyHole(h => h + c2.hole / 2).toList

  r getOrElse x
}

What other use-cases are there where we might require a context? What about other data types, such as this one:

case class Tree[A](root: A, children: List[Tree[A]])

What is its derivative? What use-cases require us to keep track of context as we navigate the tree? We will look at this, and other related ideas, in a future post.

Just a note on vocabulary. The ListCursor data type is sometimes called a zipper. In other words it is "the list zipper" data type.

McBride, Conor. The derivative of a regular type is its type of one-hole contexts. (2001) ↩

More Algebra of Algebraic Data Types

Footnotes