ADT's presentation - Haskell had best code colors in my little presentation thingy (marp), but read them as psuedocode

adts.md

paginate
true

ADT's, State Complexity & Boolean Blindness

Or, how to infer complexity using ADT's, and why booleans are evil...

---

Sounds Scary - Is not really...

• There is a relationship between types, and algebra
• Algebra as in, 1 + 1, 2 * 2, 3 ^ 3
• Mostly an exploration
• Product types & Sum types
• Real-life example
• Unit & Never <- If there's time
• Exponent types <- If there's time

---

A Pair...

A pair is simply the type of a tuple that has exactly 2 positions

 type pair<'a, 'b> = ('a, 'b)

 -- (true, false)      - (bool, bool)
 -- (8, 6)             - (int, int)
 -- (8, "some-string") - (int, string)

---

 type pair<'a, 'b> = ('a, 'b);
 type boolPair     = pair<bool, bool>;

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

 -- (2, 2) -> 4

---

Three...

 type three         = | One | Two | Three
 type boolThreePair = pair<bool, three>;

 -- (true, One)
 -- (true, Two)
 -- (true, Three)
 -- (false, One)
 -- (false, Two)
 -- (false, Three)

 -- (2, 3) -> 6

---

Four...

 type four         = | One | Two | Three | Four
 type boolFourPair = pair<bool, four>;

 -- (true, One)
 -- (true, Two)
 -- (true, Three)
 -- (true, Four)
 -- (false, One)
 -- (false, Two)
 -- (false, Three)
 -- (false, Four)

 -- (2, 4) -> 8

---

Consolidate...

 type boolPair      = pair<bool, bool>;  -- (2, 2) -> 4
 type boolThreePair = pair<bool, three>; -- (2, 3) -> 6
 type boolFourPair  = pair<bool, four>;  -- (2, 4) -> 8

 -- (x, y) -> x * y

---

Product Types...

type pair    = ('a, 'b)                      -- 'a * 'b
type triple  = ('a, 'b, 'c)                  -- 'a * 'b * 'c
type pairR   = {one: 'a, two: 'b}            -- 'a * 'b
type tripleR = {one: 'a, two: 'b, three: 'c} -- 'a * 'b * 'c

---

Sum Types...

type bool  -- | True | False              -> 2
type three -- | One  | Two | Three        -> 3
type four  -- | One  | Two | Three | Four -> 4

type pairOrBool = | One(bool) | Two((bool, bool))
             -- = | One(2)    | Two((2, 2))
             -- = + 2         + (2 * 2)
             -- = 6

---

Real-life Scenario...

---

Special Types...

Unit & Never is a special type

 type unit         = ()
 type boolUnitPair = pair<bool, unit>;

 let unit = () -- Exactly one value

 type never;
 type boolNeverPair = pair<bool, never>;

 let never = -- ?? Exactly 0 values

Are they product or sum types?

---

Unit & Never...

  let sum = reduce((x, y) => x + y, ...) -- Fill in the dots
  let product = reduce((x, y) => x * y, ...) -- Fill in the dots

  sum([1, 2]) + sum([]) = sum([1, 2]) -- 3
  product([1, 2]) * product([]) = product([1, 2]) -- 2

---

Unit & Never...

  let sum = reduce((x, y) => x + y, 0)
  let product = reduce((x, y) => x * y, 1)

  sum([1, 2]) + 0 = sum([1, 2]) -- 3
  product([1, 2]) * 1 = product([1, 2]) -- 2

So

• An empty product type (unit: ()) holds 1 value
• And an empty sum type (never: |), holds 0 values

---

Unit & Never...

 type unit    = ()
 -- type unit = () <- can be reasoned about like this, an empty tuple
 -- unit -> product type

 type never;
 -- type never = | <- can be reasoned about like this, an empty enum
 -- never -> sum type

---

Unit...

 type foo = {a: bool, b: three} -- 2 * 3
 type foo = {a: bool, b: three, c: unit} -- 2 * 3 * 1
 -- Adding unit doesn't add complexity to a product type

 type foo<'a> = | A('a) -- 'a
 type foo<'a> = | A('a) | Unit(unit) -- 'a + 1
 type foo<'a> = | Something('a) | Nothing -- 'a + 1
 type option<'a> = | Some('a) | None -- 'a + 1
 -- Adding unit to a sum type, make's it an optional value

---

Never...

 type foo = {a: bool, b: three} -- 2 * 3
 type foo = {a: bool, b: three, c: never} -- 2 * 3 * 0 == 0
 -- Adding never to a product type, makes it uninstantiable

 type foo<'a> = | A('a) -- 'a
 type foo<'a> = | A('a) | Never(never) -- 'a + 0
 -- Adding unit to a sum type, basically doesn't do anything

 type result<'a, 'b> = | Ok('a) | Error('b)
 let thingThatNeverFails = Result<string, never>

---

Exponents...

 2^100 = 2 * 2 * 2 ... * 2
 2^3   = 2 * 2 * 2
 2^3   = 2^1 * 2^1 * 2^1

• bool^three

---

Exponents...

bool^three               = 2^3             = 8
                         = 2^(1 + 1 + 1)   = 8
                         = 2^1 * 2^1 * 2^1 = 8
bool^1 * bool^1 * bool^1 =                 = 8

• Basically, for every value of three, we pick a boolean
• bool^three === (three) -> bool
• Exponents === Functions

---

Exponents...

(a ^ b) ^ c = a ^ (b * c)

(2 ^ 2) ^ 2 = 2 ^ (2 * 2)
(2 * 2 * 2) * 2 = 2 ^ (4)

---

Exponents...

• bool^three === (three) -> bool

(a ^ b) ^ c = a ^ (b * c)

(a <- b) <- c = a <- (b, c)

c -> (b -> a) = (b, c) -> a
a -> (b -> c) = (b, a) -> c -- Replace a -> c / c -> a
a -> (b -> c) = (a, b) -> c -- Swap b / a

---

Curry...

// type add: 'a => 'b => 'c
const add = (a) => (b) => a * b;

// type curry: (('a, 'b) => 'c) => 'a => ('b => 'c)
let curry = f => a => b => f(a, b);

// type uncurry: ('a => 'b => 'c) => ('a, 'b) => 'c
let uncurry = (f) => (a, b) => f(a)(b);

add(1)(2)
uncurry(add)(1, 2)
curry(uncurry(add))(1)(2)

---

Futher Reading

• Boolean Blindness -> Original Blogpost
• Boolean Blindness -> haskell Weekly Podcast

These are Paid, but well worth it

• Point Free -> ADT's Intro
• Point Free -> Exponent Types
• Point Free -> Generics & Recursion