Why do functional programmers always talk about algebra(s)?

name: inverse
    layout: true
    class: underscore
    ---
    class: center, middle, hero

.title[
      # Why do functional programmers always talk about algebra(s)?
      ## Adam Rosien, [@arosien](http://twitter.com/arosien)
      ## [Scala.IO 2016](http://scala.io/)

[![Underscore Logo](img/white-logo.png)](http://underscore.io/)
    ]

???

Hi, and welcome to my talk. My name is Adam Rosien and I'm a consultant at
    Underscore, a Scala specialist consultancy.

Toggle speaker view by pressing P

Pressing C clones the slideshow view,
    which is the view to put on the projector
    if you're using speaker view.

Press ? to toggle keyboard commands help.

---
    class: center wide

# .spring[.remark-code[a + 2b + 12]]

???

Algebras... what are they?

Here's a kind of algebraic expression familiar from school.

# .lemon[.remark-code[(p & q) | r]]

???

Here's another that we use all the time in programming: the boolean algebra.

# .maraschino[█ + █ = ██]

???

What about... Lego(tm)? We put a block together with another block, and what do we get? Another Lego(tm).

# .sky[.smaller-code[.remark-code[path((0 to 3) map (i => ◜ ↻ (i*90)) = ○]]]

???

How about figure drawing? We can rotate an arc 4 times by 90°, connect them as a path, and we can draw a circle.

# .smaller-code[.remark-code[case class Address(street: Street, state: State)]]

???

How about types? We can certainly combine types together in certain ways to form other types.

.lavender[
 .smaller-code[.remark-code[GET /repos/:owner/:repo/git/commits/:sha]] 
 .smaller-code[.remark-code[POST /repos/:owner/:repo/git/commits]]]

???

How about an API? Can we consider an API an algebra? Or make it one?

We'll find out!

---
    class: center middle

# 1 Structure
    # 2 Algebraic Data Types
    # 3 Exploitation
    # 4 Domain Algebras

---
    class: center middle section

# 1 Structure

???

First, what are algebras, do they have some structure?

---
    class: center

# .spring[.remark-code[a + 2b + 12]]

???

Here's our arithmetical expression again.

# a, b, ...     0, 1, 2, ...

???

We see it consists of some variables, some constants.

# a ⋅ b     a + b

???

You can add or multiply them together.

a ⋅ b = b ⋅ a     a ⋅ 1 = a     a ⋅ 0 = 0 a + b = b + a     a + 0 = a a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)

???

You might remember these rules: the order of operations doesn't matter, there's a special number 0, that when added to anything, gives you back the input, etc.

---
    class: center

# .spring[Algebra]
 # a, b, ...     0, 1, 2, ...
 # a ⋅ b     a + b
 a ⋅ b = b ⋅ a     a ⋅ 1 = a     a ⋅ 0 = 0 a + b = b + a     a + 0 = a a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)

???

So this gives us enough information to describe algebraic structure. An algebra...

---
    class: center

# .spring[Algebra]
 # Symbols
 # a ⋅ b     a + b
 a ⋅ b = b ⋅ a     a ⋅ 1 = a     a ⋅ 0 = 0 a + b = b + a     a + 0 = a a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)

???

has symbols

---
    class: center

# .spring[Algebra]
 # Symbols
 # Operations
 a ⋅ b = b ⋅ a     a ⋅ 1 = a     a ⋅ 0 = 0 a + b = b + a     a + 0 = a a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)

???

operations

---
    class: center

# .spring[Algebra]
 # Symbols
 # Operations
 # Laws

???

and laws.

---
    class: center

# .spring[Algebra]
 # .tin[Symbols:] constants, variables
 # .tin[Operations:] a ⋅ b     a + b
 # .tin[Laws: ] identity, symmetry, distributivity, ...

???

Every algebra has 3 parts: its symbols, the operations on those symbols, and laws that constrain what those operations can do.

For example, in arithmetic, the symbols are our variables. We operate on those variables using addition and multiplication, and we have to maintain certain invariants like adding 0 to anything gives you back your input.

There can be higher order constraints, like the distributive law, where the product of a sum is equal to the sum of the products (with the multiplication factor *distributed* to the sums).

---
    class: center middle section

# 2 Algebraic Data Types

---
    class: center middle

# Algebraic Data Types
 # Symbols
 # Operations
 # Laws

???

Algebraic data types... they must be some kind of algebra. We know what makes up an algebra now: symbols, operations, and laws.

---
    class: center middle

# Algebraic Data Types
 # .tin[Symbols: ] A, B, ...
 # Operations
 # Laws

???

We know what the symbols of this algebra are, they are the names of our types.

---
    class: center middle

# Algebraic Data Types
 # .tin[Symbols: ] A, B, ...
 # .tin[Operations: ] "make new types"
 # .tin[Laws: ] compiler does it?

???

But what about the operations? We know we want to "make new types". You may already have ideas about what operations we can perform.

And the laws? Maybe the compiler has them? Or, what are they?

---
    class: center

# a ⋅ b

???

It turns out that the algebra of types is equivalent to the algebra of arithmetic. So we'll build our algebra of types starting with the same operations, and laws, as we did before.

Here we have a product: a times b.

--
    ```
    (A, B)
    ```

???

In types, that's just a tuple.

--
    ```
    (A, B) ≅ (B, A)

(A, (B, C)) ≅ ((A, B), C)
    ```

???

(symmetry law, associativity law)

Note that I'm not using = here, I'm using ≅ to mean "equivalent": both order of components in the tuples contain equivalent information. Same for nesting of tuples.

---
    class: center

# a ⋅ 1 = a

???

What about multiplication by 1? We know this is true for arithmetic.

```
    (A, Unit) ≅ A
    ```

???

It's the same for products for types. 1 is the type Unit.

identity law (products)

---
    class: center

# a ⋅ 0 = 0

???

What about multiplication by 0?

```
    (A, Nothing) ≅ Nothing
    ```

???

0 in types is Nothing, the type with *no* values. So anything paired with a value that can't exist, that can't exist either!

---
    class: center

# a + b

```
    Either[A, B]
    ```

```
    Either[A, B] ≅ Either[B, A]

Either[A, Either[B, C]]
    ≅
    Either[Either[A, B], C]
    ```

???

symmetry law

associativity law

---
    class: center

# a + 0 = a

```
    Either[A, Nothing] ≅ A
    ```
    ???

identity law (coproducts)

---
    class: center

# a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)

--
    ```scala
    (A, Either[B, C])
    ≅
    Either[(A, B), (A, C)]
    ```

???

distributive law

---
    class: center

# 1 + 1 = 2

```
    Either[Unit, Unit] ≅ Boolean
    ```

---
    class: center

# 1 + a

```
    Either[Unit, A] ≅ Option[A]
    ```

---
    class: center

# a + a = 2 ⋅ a

```
    Either[A, A] ≅ (Boolean, A)
    ```

---
    class: center middle

# Algebraic Data Types
 # Symbols
 # Operations
 # Laws

---
    class: center middle

# Algebraic Data Types
 # .tin[Symbols:] Type symbols
 # Operations
 # Laws

---
    class: center middle

# Algebraic Data Types
 # .tin[Symbols:] Type symbols
 # .tin[Operations:] product, sum
 # Laws

???

TODO: product ~ case class
    TODO: sum ~ sealed trait hierarchy

---
    class: center middle

# Algebraic Data Types
 # .tin[Symbols:] Type symbols
 # .tin[Operations:] product, sum
 # .tin[Laws:] "it's just a semiring"

---
    class: center middle section

# 3 Exploitation

???

"exploiting algebraic structure"

a.k.a "what's the point?"

---
    class: center middle

# Symbols
    # Operations
    # Laws

---
    class: center middle

# .tin[Symbols]
    # .tin[Operations]
    # Laws

???

Exploitation of our algebraic structure comes from the laws.