# Back2Basics: Algebraic Data Types (ADT's)

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`

- The

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.

- Query tools like SELECT, UPDATE, and JOIN are the

## 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`

).

- The number of possible values of a

## 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.

## References:

Functional Programming Simplified by Alvin Alexander

Originally published on blog.knoldus.com