Algebraic Types in Scala???

If you have ever looked into Scala at any point you would’ve heard the term Algebraic Data Types

The goal here is to attempt to explain what that is since it’s kind of an obscure concept from an OO view point. Even though you could draw a parallel between algebraic types and Composition vs Inheritance, it’s not quite the same thing. So it’s worth while to try to understand ADT for what it is.

Disclaimer, I didn’t come up with all this material on my own, I did use a number of references which you can see at the bottom because credit should be given where credit is due (check out the references). Oh and before I forget, I’m sure there are a ton of spelling mistakes here, so I apologize in advance.

All this Scala stuff is just so exciting no time to think about spelling ¯\_(ツ)_/¯

What do you mean by “algebraic?”

Let’s do some counting.

How many values of type Nothing? → 0

How many values of type Unit? → 1

How many values of type Boolean? → 2

How many values of type Byte? → 256

How many values of type String? → many

How many of type (Byte, Boolean)? → 2 × 256 = 512

How many of type (Byte, Unit)? → 256 × 1 = 256

How many of type (Byte, Byte)? → 256 × 256 = 65536

How many of type (Byte, Boolean, Boolean)? → 256 × 2 × 2 = 1024

How many of type (Boolean, String, Nothing)? → 2 × many × 0 = 0

To figure out the cardinality of a tuple type like this, you multiply the cardinalities of the component types.

Product types! This and That

Tuples!

type Person = (String, Int)

Classes!

class ScalaPerson(val name: String, val age: Int)

class Person {
final String name;
final Int age;
...
}

• Pretty much every language has product types like tuples or records or structs or classes.
• So we all have an instinct about multiplying types. But you can also add them, which isn’t something most of us think about.

Let’s do some more counting.

So this is something you may not ever think about if you’re coming from a traditional object oriented language. What if you have a choice of one thing or another?

How many of type Byte or Boolean? → 2 + 256 = 258

How many of type Boolean or Unit? → 2 + 1 = 3

How many of type (Byte, Boolean) or Boolean? → (256 × 2) + 2 = 514

How many of type Boolean or (String, Nothing)? → 2 + (many × 0) = 2

Sum types! This or That

Nothing = 0
Unit= 1
Boolean = 2
Byte= 256

(Unit , Boolean) = 1 × 2 = 2 
 Unit | Boolean= 1 + 2 = 3 // not Scala syntax

(Byte , Boolean) = 256 × 2 = 512
 Byte | Boolean= 256 + 2 = 258

(Boolean, Boolean, Boolean, Boolean, 
 Boolean, Boolean, Boolean, Boolean) = 256

// sums all the way down
Boolean = true | false
Int = 1 | 2 | 3 | ...

• So we’ll get to the exact encoding of this idea in Scala, but I wanted to explain this notion of multiplication and addition of types because that’s where the “algebraic” comes from.
• And we can do much more than add and multiply; function types are actually exponentials, and the derivative of a type is a structure called a one-hole context that’s the key to a family of data structures called zippers.
• So something interesting we see is that a tuple of 8 booleans has exactly the same number of inhabitants as byte. So the types are isomorphic, you can line them up 1:1 and convert between them without losing information.
• Another interesting thing is that anything times unit is just that thing; unit is the multiplicative identity for types. The takeaway is that there is never any reason to use unit in a product type.
• Understanding when types are equivalent is a nice skill to have.

Sum types in Scala

Encoded by Subclassing

sealed trait Pet
case class Cat(name: String) extends Pet
case class Fish(name: String, color: Color) extends Pet
case class Squid(name: String, age: Int) extends Pet

val bob: Pet = Cat("Bob")

In Scala when you hear ADT it means sum type.

Ok so we have a sealed trait, which means all implementations of that trait must be in the same source file so the compiler knows about all of them. And I’ll explain why that’s important bellow.

We don’t think of this as a class hierarchy. We think of it as a single type, Pet, with three constructors.

So Pet is a sum of three products. And if bob is a pet, he can be a cat or a fish or a squid, which we inspect…

De-structured by pattern matching

def sayHi(p: Pet): String = 
p match {
case Cat(n)=> "Meow " + n + "!"
case Fish(n, _)=> "Hello fishy " + n + "."
case Squid(n, _) => "Hi " + n + "."
}

scala> sayHi(Cat("Bob"))
res0: String = Meow Bob!

scala> sayHi(Squid("Steve", 10))
res1: String = Hi Steve.

We provide a match with a pattern for each constructor, and the arguments we used to construct the value are bound to variables when we do this so they’re available on the right-hand side. So that’s a different n in each case.

The underscore means we don’t care about the value.

Exhaustiveness Checking

def sayHi(p: Pet): String = 
p match {
case Cat(n)=> "Meow " + n + "!"
case Fish(n, _)=> "Hello fishy " + n + "."
}

<console>:14: warning: match may not be exhaustive.
It would fail on the following input: Squid(_, _)
 p match {
 ^

We get a compiler warning. So this is exhaustive matching, which you get if you use a sealed trait because the compiler knows that there are exactly three constructors for Pet.

So you don’t always need to use pattern matching because there might be methods on the parent trait that do what you want, but you can always fall back on it if you’re not sure what to do.

There is another more general way we can encode de-structuring, called a fold. We will see this in a minute.

Standard Library: Option

Computations that may fail to return a value

sealed trait Option[+A] 
case object None extends Option[Nothing]
case classSome[A](a: A) extends Option[A]

Example

def safeDiv(a: Int, b: Int): Option[Int] =
if (b != 0) Some(a / b) else None

scala> val x = safeDiv(10, 2)
x: Option[Int] = Some(5)

scala> val y = safeDiv(10, 0)
y: Option[Int] = None

This is what we do instead of using null in Scala

Standard Library: Either

Computations that may return this or that

sealed trait Either[+A, +B] 
case class Left[A](a: A)extends Either[A, Nothing]
case class Right[B](b: B) extends Either[Nothing, B]

Example

def safeDiv(a: Int, b: Int): Either[String, Int] =
if (b != 0) Right(a / b) else Left("Divide by zero!")

scala> val x = safeDiv(10, 2)
x: Either[String,Int] = Right(5)

scala> val x = safeDiv(10, 0)
x: Either[String,Int] = Left(Divide by zero!)

• You can use this to return this or that; most commonly you see left for errors and right for success.

Standard Library: Try

Computations that may fail with an exception

sealed trait Try[+A]
case class Success[A](a: A) extends Try[A]
case class Failure[A](t: Throwable) extends Try[A]

Example

import util._ // it's scala.util.Try

def safeDiv(a: Int, b: Int): Try[Int] =
Try(a / b)

scala> val x = safeDiv(10, 2)
x: scala.util.Try[Int] = Success(5)

scala> val x = safeDiv(10, 0)
x: scala.util.Try[Int] = Failure(java.lang.ArithmeticException: / by zero)

Standard Library: List

Computations that may return many answers

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

object List {
def apply[A](as: A*): List[A] = ...
}

Example

def sum(ns: List[Int]): Int =
ns match {
case Nil => 0
case n :: ns => n + sum(ns)
}

scala> sum(List(1,2,3))
res23: Int = 6

References:

http://tpolecat.github.io/

http://underscore.io/training/courses/essential-scala/

---