Anatomy of an algebra
Tags: scala, functional
Published: 2019-02-21 10:16:37

---
title: "Anatomy of an algebra"
published: true
description: "Functional programmers tend to talk a lot about algebras, what the heck is an algebra ?"
tags: [scala, fp, functional]
canonical_url: "http://geekocephale.com/blog/2018/10/06/algebras"
series: "Functional programming atlas"
---

[Check my articles on my blog [here](http://geekocephale.com/blog/)]

I will try to group here, in an anatomy atlas, basic notions of functional programming that I find myself explaining often lately into a series of articles.

The idea here is to have a place to point people needing explanations and to increase my own understanding of these subjects by trying to explain them the best I can.
I'll try to focus more on making the reader feel an intuition, a feeling about the concepts rather than on the perfect, strict correctness of my explanations.

- Part 1: [Anatomy of functional programming](https://dev.to/mmenestret/anatomy-of-functional-programming-1bpg)
- Part 2: [Anatomy of an algebra](https://dev.to/mmenestret/anatomy-of-an-algebra-3cd9)
- Part 3: [Anatomy of a type class](https://dev.to/mmenestret/anatomy-of-a-type-class-440j)
- Part 4: [Anatomy of semi groups and monoids](https://dev.to/mmenestret/anatomy-of-semigroups-and-monoids-22i8)
- Part 5: [Anatomy of functors and category theory](https://dev.to/mmenestret/anatomy-of-functors-and-category-theory-2gf0)
- Part 6: Anatomy of the tagless final encoding - Yet to come !

# What is an algebra ?

Functional programmers tend to talk a lot about _algebras_, so a good starting point would be to understand what an _algebra_ is.
A simple definition would be (from _Wikipedia_):

> In its most general form, an _algebra_ is the study of mathematical symbols and the rules for manipulating these symbols

Then to rephrase it in simpler terms, it is a system formed by:

- __Symbols__, items or "things"
- __Operations__ on thoses "things"
- __Properties and rules__ about those operations

A simple _algebra_ example would be:

- Symbols: the integer numbers
- Operations: addition and multiplication
- [Properties and rules](https://en.wikipedia.org/wiki/Integer#Algebraic_properties):
    - Closure: the result of the two operations is itself in integer number
    - Associativity: `a + (b + c) = (a + b) + c` and `a × (b × c) = (a × b) × c`
    - Commutativity: `a + b = b + a` and `a × b = b × a`
    - Identity elements: `a + 0 = a` and `a * 1 = a`
    - And so on (check the link if you want to see the rest)

# How does it relates to FP ?

## Domain modeling

When modeling a business domain, in functional programming, [we separate strongly data from behaviors](https://dev.to/mmenestret/anatomy-of-a-type-class-440j) (see the _Data/behavior relationship_ section).

To do that:

- We create types on one side
- Pure functions manipulating those types
- And these functions have to respect some strict business logic

Doesn't that ring any bell ?

We manipulate _algebras_ !

- __Symbols__: our business types
- __Operations__: our business functions acting on those types
- __Properties and rules__: our business logic implemented in these functions, and our _property based tests_
    - We won't cover those here, but to give you an idea, these are not unit tests, but tests based on function properties that they must _always_ verify (such as: "A combination of several sales cannot result in a negative price") while tested against a wide range of more or less random values generated by a test framework

### A concrete example

To make it clearer, let's take a dummy example.

Say we have to produce sales reports, we would probably model our domain like:

```scala
type Amount = Int
type Price = Int

final class ID(val value: Int) extends AnyVal
final case class Item(id: ID, price: Price)
final case class Sales(items: List[(ID, Amount)], totalPrice: Price)
  
trait SalesOperations {
    def combineAll(sales: List[Sales]): Sales
    def generateReport(sales: Sales): String
}
```

In that case:

- __Symbols__: `Amount`, `Price`, `ID`, `Item`, `Sales`, etc. (our business types)
- __Operations__: `combineAll`, `generateReport` (operations on those types)
- __Properties and rules__: the business logic and the tests we haven't implemented here

That's pretty much it !

It happens frequently to have shared behaviors that are common to several types.
We want to be able to design functions that can be run on those different types and have the expected behavior depending on their input types. Those functions are said then said to be _polymorphic_.

That's a problem we solve with [_type classes_](https://dev.to/mmenestret/anatomy-of-a-type-class-440j).

## What is an ADT ?

_ADT_ stands for _algebraic data type_. Well, we talked a bit about _algebras_ but we didn't talk about _types_ yet.

### What is a type ?

A _type_ or a _data type_, is just a classification of data, a _set of values_ or _inhabitants_, that we use to tell the compiler how we intend to use data so it can check that we respect the rules (that's the _type checking_).

- `Boolean` is a _type_ that classifies these two values: `true`, `false`
- `String` is a _type_ that reprents an infinity of inhabitants, all the possible characters combinations
- `Option[A]` is a _type_ that represents all the values of type `A` (wrapped in a `Some`) + the value `None`

    - `Option` has a number of inhabitants equals to the number of inhabitants of the type `A` + 1 (the `None` value)
    - `Option[Boolean]` has 3 inhabitants: `Some(true)`, `Some(false)`, `None`

- `Unit` is a _type_ that has only 1 inhabitant, the value: `()`
- `Noting` is a _type_ that has no member (there is no way to create a value whose type is `Nothing`)

### What is an algebraic data type then ?

Here is _Wikipedia_'s definition of an _algebraic data type_:

> In computer programming, especially functional programming and type theory, an _algebraic data type_ is a kind of composite type, i.e., a type formed by combining other types.

We call these new types _ADTs_ because we create them by combining existing types... well, guess what ? We use an _algebra_ again !

This is algebra is the following:

- __Symbols__: existing types: primitive types, other existing ADTs, ... (`Sales`, `Boolean`, `String`, `Int`, ...)
- __Operations__: _sum_ and _product_ (we'll see what they mean)
- __Properties and rules__: some properties and laws about these _sum_ and _product_ operations (we'll also see what they mean)

### Sum

_sum_ is the action of combining by "summing" their respective values together.

You can see it as a way to define that: __values of a _sum type_ can only be either a value of this OR that type__ (the __OR__ is the key intuition here).

It is done, in _Scala_, usually by using:

- _sealed traits_ and their instances as _case classes_ or _case objects_

Or less often:

- The `Either[A, B]` type

That way, when you declare:

```scala
sealed trait CoinSide
case object Heads extends CoinSide
case object Tails extends CoinSide
```

You are creating an _ADT_ `CoinSide` which is a _sum type_ (created with a _sum_ operation) which has two and only two possible values (or inhabitants), `Heads` or `Tails`.

The same would be achieved with:

```scala
type CoinSide = Either[Heads, Tails]
```

Whose possible values would then be, `Left(Heads)` or `Right(Tails)`.

These are just two different encodings for the same thing.

### Sum properties

The _sum_ operation also have properties.

I won't go into full details here but (these examples would equally be true with _sealed traits_ + their implementations instead of `Either` type):

- The number of values of a _sum type_ is the _sum_ of the values of its composing types members (just as you would assume for addition on integers)

    - `Boolean` has __two__ inhabitants: `true` and `false`
    - `Either[Boolean, Boolean]` which is a _sum type_ of two types `Boolean` has __four inhabitants__:

        - `Left(true)`
        - `Left(false)`
        - `Right(true)`
        - `Right(false)`

    - `Either[Boolean, Either[Boolean, Boolean]]]` is a _sum type_ between a `Boolean` and another _sum type_ of a `Boolean` and a `Boolean`

        - Well guess what ? It has 2 + (2 + 2) values !

- It has an _identity_ element which is the `Nothing` type which has no values at all

    - `Either[Boolean, Nothing]` is a _sum type_ of a `Boolean` with the _sum_ identity. Because there is no way to create a value of type `Nothing`, it does not exist, so there is no way to construct a `Right`, it has only __two values__:

        - `Left(true)`
        - `Left(false)`

- It is associative, `Either[Boolean, Either[Boolean, Boolean]]]` is the same as `Either[Either[Boolean, Boolean]],Boolean]`, you can enumerate the values, you'll see (well _isomorphic_, we have the same _"expressive power"_ with both representations, but let's say they are the same) !
- And so on (I'll give you more material at the end if you want to keep diving)

### Product

_product_ is the action of combining two or more types together by "multiplying" their respective values together.

You can see it as a way to define that __values of a _product type_ are the combination of values of this AND that type__ (the __AND__ is the key intuition here).

It is done, in _Scala_ usually by using:

- _case classes_

Or less often

- _tuples_

That way, when you declare:

```scala
case class TwoCoinsAndABoolean(fst: CoinSide, snd: CoinSide, b: Boolean)
// or
type TwoCoinsAndABoolean = (CoinSide, CoinSide, Boolean)
```

These are just two different encodings for the same thing.

You are creating an _ADT_ `TwoCoinsAndABoolean` which is a _product types_ (created with a _product_ operation) which has the number of values of its members multiplied.

In our case 8 values (2 * 2 * 2):

- `TwoCoinsAndABoolean(Heads, Heads, true)` or `(Heads, Heads, true)`
- `TwoCoinsAndABoolean(Heads, Tails, true)` or `(Heads, Tails, true)`
- `TwoCoinsAndABoolean(Tails, Heads, true)` or `(Tails, Heads, true)`
- `TwoCoinsAndABoolean(Tails, Tails, true)` or `(Tails, Tails, true)`
- `TwoCoinsAndABoolean(Heads, Heads, false)` or `(Heads, Heads, false)`
- `TwoCoinsAndABoolean(Heads, Tails, false)` or `(Heads, Tails, false)`
- `TwoCoinsAndABoolean(Tails, Heads, false)` or `(Tails, Heads, false)`
- `TwoCoinsAndABoolean(Tails, Tails, false)` or `(Tails, Tails, false)`

You can observe that _product types_ values are the cartesian product of their _composing types_ values !

### Product properties

The _product_ operation also have properties.

I won't go into full details here but (these example would equally be true with _case classes_ instead of _tuples_):

- The number of values of a _product types_ is the _product_ of the number of the values of its combining members (as you would assume for multiplication on integers)

    - `Boolean` has __two__ inhabitants: `true` and `false`
    - `(Boolean, Boolean)` which is a _product type_ of two types `Boolean` has __four values__:

        - `(true, true)`
        - `(true, false)`
        - `(false, true)`
        - `(false, false)`

    - `(Boolean, (Boolean, Boolean)` is a _product type_ between a `Boolean` and another _product type_ of a `Boolean` and a `Boolean`

        - Well guess what ? It has 2 * (2 * 2) values !

- It has an _identity_ which is the famous `Unit` type which has only one inhabitant, the value `()`

    - `(Boolean, Unit)` is a _product type_ of a `Boolean` with the _product_ identity. It has __two values__:
    
        - `(true, ())`
        - `(false, ())`

- It is associative, `(Boolean, (Boolean, Boolean)` is the same as `((Boolean, Boolean),Boolean)`, you can enumerate the values, you'll see (well _isomorphic_, we have the same _"expressive power"_ with both representations, but let's say they are the same) !
- And so on (I'll give you more material at the end if you want to keep diving)

### Mixed types

Of course, as we saw in some of the examples, _ADTs_ can be combinations of other _ADTs_, such as _sum of products_, _products of sums_, _product of products_ and so on.

# More material

If you want to keep diving deeper, some interesting stuff can be found on my [FP resources list](https://github.com/mmenestret/fp-ressources) and in particular:

- [Functional and Reactive Domain Modeling](https://www.manning.com/books/functional-and-reactive-domain-modeling) (An awesome book about functional domain modeling using _algebras_)
- [Kinds of types in Scala](https://kubuszok.com/compiled/kinds-of-types-in-scala/)
- [Why do Functional Programmers always talk about Algebra(s)?](https://www.youtube.com/watch?v=s2ay9nEW3ak)

# Conclusion

All that long digression was only meant to show you that, __creating new composite data types the way we do in pure FP is done by using an algebra__.

That's why these composite types are called _Algebraic Data Types_ :).

To sum up, we learnt:

- What was an _algebra_
- How algebras were used to model domains in a neat way and how it was adequate to the pure functional programming approach
- What was a _type_
- How creating new _data types_ was done by using an _algebra_ composed by _types_ and operations on them and thus why the types created that were called _algebraic data types_

I'll try to keep that blog post updated.
If there are any additions, imprecision or mistakes that I should correct or if you need more explanations, feel free to contact me on Twitter or by mail !