Algrebraic Data Types in Scala

What a delightful idea to come back from vacation with batteries fully charged and with some wacky ideas around our minds to write about. Best of these came from the very influence of joints the moon.

ADT?

An Algebraic Data Type (TDA from now so we can save money for each word in WordPress) is just a way to express a data type (Cat, Dog, Prevarication) based on an algebra. And when we say ‘algebra’, we mean type sums and products (of Integers, Cats, Cars, Prevarications, …). For example:

Train = Locomotive + Wagon * Train

How do one read that? A train may be: a locomotive OR a wagon AND another train (that may be as well a wagon and another train, that may be as well a …).
Take a look at both disjunction and conjunction: the sum represents an OR, and the product represents an AND (like Boole algebra).

It’s also worthy to notice that, from this type definition you can infer a recursive pattern. With the Train type, the base case is definitively the Locomotive and, at the recursive case, we have a wagon and another train. As we’ll see later, this pattern is very frequent and makes easier the type definition.

And how are sum and product represented in Scala?

The easier way to represent the type sum (also called co-product), in a paradigm with polimorphism support (in general) and in Scala (in particular), is just the inheritance feature. If we have the following case:

sealed trait Animal
case object Cat extends Animal
case object Dog extends Animal

we’re indeed expressing a type co-product:

Animal = Cat + Dog

that is, an Animal can only be, a Cat, or a Dog.

Regarding the product, we could define it as the attribute set that compounds a certain type instance. For example,

case class Student(name: String, age: Int)

expressed as a product sum, would be as follows:

Student = String * Int

So, for building a Student instance, you need a String and an Int.

If we try now to materialize the previously exposed train model (with some additives) we’ll notice that

Wagon = String * Int
Train = Locomotive + Wagon * Train

is translated into Scala as

sealed trait Train
case object Locomotive extends Train
case class Wagon(model: String, passengers: Int)
case class Nexus(wagon: Wagon, next: Train)

So what is it good for?

…absolutely nothing, listen to me♩♪♫♬.
If you think, my fellow, that this is stuff that nobody uses, you haven’t thought about which scala.Prefef structures are defined this way. Lists, for example, as defined as:

trait List[+T]
case object Nil extends List[Nothing]
case class ::[T](head: T, tail: List[T]) extends List[T]

That is, a List can be, an empty one, or an element followed by another list.
If we express that idea in terms of products and co-products:

List[T] = EmptyList[T] + NonEmptyList[T]
NonEmptyList[T] = T * List[T]

Please, notice that, the case of the empt list (Nil) has a bizarre but beautiful implementation in Scala.

If we try to define an empty list for eeeeeeeeeevery single existing type, we would have to instantiate a Nil[Cat], a Nil[Dog], …
In order to avoid this, and having an only Nil, we make it extend from List[Nothing] that, as you’ll probably remember from other posts, Nothing extends from eeeeeeeeevery single existing type (both primitive and programmer defined). If we add the fact of List[T] being covariant at T, we’ll have an only object Nil that represents the empty lists for all types. Awesome, right?

Example: Even numbers

In order to harden to this new way of thinking, let’s suppose the following challenge: how could we represent even numbers in Scala?

Requirements

If we’re not sophisticated enough and we trust a lil’ bit in runtime assertions, we could say that even numbers are defined as:

case class Even(value: Int) { 
  require(value%2==0, "it's not even")
}

But, if we try to create an Even with an odd integer number we’ll get a giant NOPE:

Even(1)
java.lang.IllegalArgumentException: requirement failed: it's not even
	at scala.Predef$.require(Predef.scala:233)
	at Even.<init>(<console>:7)

However this assertion won’t be verified until run-time, the moment when require is executed. Thus, our code could be compiled without being correct…
We can do it much better…

Next(Next(…))

Another option is to assume (and we won’t discuss about it) that zero is an even number, that we have infinite memory installed in our machine, that the overflow error doesn’t exist…

In that, not so far, case (…), we could define even numbers as:

sealed abstract class Even(val value: Int)
case object Zero extends Even(0)
case class Next(previousEven: Even) 
  extends Even(2 + previousEven.value)

So, if we have a method that generate reservations for the Boat Love, that requires an even number of participants, we can use our brand new defined Even type:

def loveBoatReservation(
  peopleAmount: Even): Reservation = ???

Given there’s no way to build an Even from an integer that is not even, we avoid uncomfortable situations at runtime, where the amount of people that get on the Love Boat are odd. Otherwise, someone could be…

Recursive ADTs and its techniques

Once the data type is defined, let’s suppose we want to implement the sum of even numbers:

def sum(e1: Even, e2: Even): Even = ???

We handle several alternatives. One of them could be the quick-and-dirty one:

def sum(e1: Even, e2: Even): Event = 
  new Even(e1.value + e2.value){}

But take a closer look at the fact that we’re totally ignoring the constructors we’ve defined. If we want to use pattern matching over the result:

val four = new Even(4){}
sum(Zero, four) match {
  case Zero => 
    //it never gets inside this case!
  case Next(Next(Zero)) => 
    //OMG! IT DOESN'T FIT HERE EITHER!
}
scala.MatchError: $anon$1@649f2009 (of class $anon$1)

The other technique (much more sophisticated by the way) consists on invoking a recursive method that, for each call, it decreases the second even number, while it increases the first one. For doing so, we make use of Next apply(constructor) and unapply(extractor) methods:

def sum(e1: Even, e2: Even): Even = {
  @tailrec
  def rSum(ev1: Even, ev2: Even): (Even, Even) = {
    ev2 match {
      case Zero => (ev1, Zero)
      case Next(e) => rSum(Next(ev1), e)
    }
  }
  val (result, _) = rSum(e1, e2)
  result
}

Undeniably beautiful 🙂

Conclusions

Apart from becoming a lil’ bit crazier when reading back-from-vacation posts, we can extract several main conclusions from what we’ve read:

• As we always say, every possible assertion that we can check at compile time instead of runtime, it’s saving time and headaches hunting bugs of software in production (which is more expensive and more keen to make heads roll).
• Constructors are THE key. If we define an ADT, we can control that generated values of that type are correct by defining the proper constructors: Zero and Next. In both cases, we are certainly sure that even number rules are satisfied.
• Methods that operate over recursive data types use to be recursive as well. And, apart from that, for generating values of the mentioned type (Even in our example) they should only use the existing constructor methods.

In a future post, we’ll talk about the relation between data types algebra and definition of formal grammars…or not.

Peace out!