# FP for Sceptics: Introduction to ADTs (Algebraic Data Types)

Algebraic Data Types (or ADTs) model the flow of a program (or a system) in terms of data & functions that describe the complete behaviour and states the data can go through.

Let's take an example to grok the concept better.

## Example: Area of a rectangle

Calculate the area of a rectangle from a list of positive integers

Here's a possible algorithm:

• Take a list of integers (positive & negative)
• Filter for positive integers ie., remove negative integers
• Create pairs from the filtered list
• Apply equation for area of rectangle

Base functions:

```def filterPositives(allIntegers: List[Int]): List[Int] = allIntegers.filter(_ > 0)

def toPairs(positiveIntegers: List[Int]): List[(Int, Int)] = positiveIntegers.map(i => (i, i))

def toAreaList(pairs: List[(Int, Int)]): List[Int] = pairs.map({ case (l: Int, b: Int) => l * b })
```

We can express our program in terms of these functions:

```def program(allIntegers: List[Int]): List[Int] = {
val positiveIntegers: List[Int] = filterPositives(allIntegers)

val pairsOfPositiveIntegers: List[(Int, Int)] = toPairs(positiveIntegers)

toAreaList(pairsOfPositiveIntegers)
}

// Elegant alternative

def elegantProgram(allIntegers: List[Int]): List[Int] =
toAreaList _ compose toPairs compose filterPositives apply allIntegers
```

That's awesome but it is not so straightforward to make sense of how or what data is flowing through where in the program:

```type program =
(List[Int] => List[Int]) =>               // filterPositives
(List[Int] => List[(Int, Int)]) =>    // toPairs
(List[(Int, Int)] => List[Int])   // toAreaList
```

That is a crazy amount of `List`s, `Int`s and `List of Int`s to follow around. What makes it worse is that we have no idea about what the data types signify, for example - How does `List[Int]` used in `filterPositives` input differ from the one used by `toPairs`?

We can model our system better using ADTs. But first, let's start by visualizing our problem: The diagram nicely helps break down the program into functions, data stages & data types.

##### Functions
• `filterPositives`
• `toPairs`
• `toAreaList`
##### Stages of Data:
• `All Integers`
• `Posiives`
• `Positive Pairs`
• `Areas`

#### Data Types

• `ℤ` (Remember that `ℤ` in mathematics is used to denote the set of all integers)
• `ℤ+`
• `(ℤ+, ℤ+)`

In previous example, we had functions & types of data being passed around but nothing to describe the stages of data.

This is where ADTs comes in.

ADTs are a set of data classes (`case class`es in Scala) that encapsulate our primitive types into domain specific descriptive types.

Let's start by describing stages of our data:

```case class AllIntegers(values: List[Int])
case class Positives(values: List[Int])
case class PositivePairs(values: List[(Int, Int)])
case class Areas(values: List[Int])
```

Now our functions change to:

```def filterPositives(allIntegers: AllIntegers): Positives = Positives(allIntegers.values.filter(_ > 0))

def toPairs(positiveIntegers: Positives): PositivePairs = PositivePairs(positiveIntegers.values.map(i => (i, i)))

def toAreaList(pairs: PositivePairs): Areas = Areas(pairs.values.map({ case PositivePairs(l: Int, b: Int) => l * b }))
```

The data flow changes to:

```type program =
AllIntegers =>
Positives =>     // filterPositives
PositivePairs => // toPairs
Areas            // toAreaList
```

The program can be written as

```def elegantProgram(allIntegers: AllIntegers): Areas = // Note the types used for input & output
toAreaList _ compose toPairs compose filterPositives apply allIntegers
```

An important thing to appreciate here is that using ADTs now makes it harder to make mistakes with function composition. For example, when we were using primitive types, we could've easily written following code which would compile and run:

```def programPrimitiveTypes(allIntegers: List[Int]): List[Int] = allIntegers
```

However with ADTs, we have the compiler on our side ensuring the program is typesafe and correct.

```def programADTs(allIntegers: AllIntegers): Areas = allIntegers // Compiler error!
```

### Conclusion

I hope this sheds some light on the value of ADTs and why they are useful.

There is a lot more to ADTs but I will cover it in a separate post using the context of a web application.

Would you like a free ebooklet?