Back2Basics: Algebraic Data Types (ADTs)

Table of contents

Reading Time: 4 minutes

To understand ADTs, firstly, we have to understand what is the meaning of the word “algebra“.

Algebra

Algebra is basically the study of mathematical symbols and the rules for manipulating these symbols. So, logically, an algebra can be thought of as consisting of two things:

A set of objects
The operations that can be applied to those objects to create new objects

Numeric algebra

Numeric algebra is the algebra of numbers. You can think of it like this:

A set of objects, such as whole numbers, natural numbers, integers.
The operations that can be used on those objects: + , – , * , / , etc.

1 + 1 = 2
3 * 2 = 6

Here, 1, 2, 3, 6 are the numbers i.e., belongs to the set of natural numbers and +, * are the operators. Now, one thing to notice here is that the operators are used on existing numbers (objects) to create new numbers (objects).

Relational algebra

Relational algebra is the algebra of relational databases. Here,

The database tables are the “set of objects“
Query tools like SELECT, UPDATE, and JOIN are the “operators” that let you create new objects from the existing objects.

Algebra in programming

We have been using algebra in FP throughout but possibly without knowing it. For example, take a look at this case class:

case class Coordinate (
x: Int,
y: Int
)

This code creates a new type Coordinate from two instances of the existing type Int. The class constructor itself is an “operator” that lets you create new types from existing Scala types, just like + and * let you create new numbers from existing numbers.

Algebraic Data Types: ADTs

An algebraic data type is a kind of composite type, i.e., a type formed by combining other types. ADTs fall into three main categories

Sum type
Product type
Hybrid type

The Sum type

Sum type enumerates all the possible instances of the type, hence it is also referred as “enumerated type“. Let’s understand this with a simple example

sealed trait Gender
case object Male extends Gender
case object Female extends Gender
case object Other extends Gender

Sum types are typically created with a sealed trait as the base type, with instances created as case objects. You use a sealed trait because you don’t want them to be extended.
The number of enumerated types you list is the only possible instances of the base type. In this example, Gender has three possible values: Male, Female, and Other.

Why sealed trait?

A great feature of using sealed trait is that it can only be extended in the file in which it was defined and it can’t be extended anywhere else, the compiler knows all of the subtypes of the trait that can possibly exist. Because of this, the compiler can exhaustively check the possible cases in match expressions. This makes your programming easier, and your code clean and safe.

Why case object?

Sum types use the case object as they only require singleton instances. For instance, with the Gender example, it makes sense to have only one Male instance in all of your code. There’s no need to create new Male and Female instances every time you work with Gender values. Scala’s case object gives you this singleton functionality.

The Product type

Its name comes from the fact that you use the Scala case class constructor to create a data type whose number of possible concrete instances can be determined by multiplying the number of possibilities of all of its constructor fields.

case class Person(
firstName: String,
lastName: String
email: String)

What do you think the number of possibilities is for this class:
Infinite? That’s absolutely right. Because a String has an infinite number of possibilities, Person can have an infinite number of concrete instances.

Few important points about the Product type:

Writing case class and defining the constructor parameters is essentially the “product” operator.
The number of possible values of a Product type is the product of all possible combinations of the constructor parameters (i.e., a Cartesian product).

Hybrid types

The Sum and Product types are the two base ADTs; all other ADTs are hybrids created from those base types. So there is no particular base hybrid type, but one popular hybrid type is known as the “Sum of Products” type.

sealed trait Parallelogram
final case class Square(side: Double) extends Parallelogram
final case class Rectangle(length: Double, breadth: Double) extends Parallelogram

These types represent a Sum type because Parallelogram is a Square or Rectangle. Square is a Product type because it has a side and Rectangle is also a Product type because it has a length and a height.

Sum and Product types can be combined in many ways to form Hybrid type to solve the problem at hand.

Pattern Matching using Algebraic Data Type

A great benefit of ADTs is that they simplify and encourage the use of pattern matching in your code.

sealed trait Parallelogram
final case class Square(side: Double) extends Parallelogram
final case class Rectangle(length: Double, breadth: Double) extends Parallelogram

We can easily write an isSquare function using pattern matching:

def isSquare(s: Parallelogram): Boolean = s match {
case Square(_) => true
case _ => false
}

Conclusion

If you create your data models using (a) case classes with immutable fields, (b) case objects you’re already writing ADTs (probably without knowing).
ADTs are the way of categorizing the code not designing the code.
The two main types of ADTs are the Sum type and Product type. Other hybrid ADTs are derived from these base types.
ADTs encourage a pattern-matching style of programming.