class: center, middle # Far more than you've ever wanted to know about ADTs [Nicolas Rinaudo] • [@NicolasRinaudo@functional.cafe] --- class: center, middle # Far more than you've ever wanted to know about .highlight[ADTs] [Nicolas Rinaudo] • [@NicolasRinaudo@functional.cafe] --- class: center, middle .center[] --- ## Valid programs  --- ## Valid programs  ```haskell face north ``` --- ## Valid programs  ```haskell face north ``` --- ## Valid programs  ```haskell face west ``` --- ## Valid programs  ```haskell face west ``` --- ## Valid programs  ```haskell face south ``` --- ## Valid programs  ```haskell face south ``` --- ## Valid programs  ```haskell face east ``` --- ## Valid programs  ```haskell face east ``` --- ## Valid programs  ```haskell start ``` --- ## Valid programs  ```haskell start ``` --- ## Valid programs  ```haskell stop ``` --- ## Valid programs  ```haskell stop ``` --- ## Invalid programs  ```haskell triple_backflip ``` --- ## Invalid programs  ```haskell triple_backflip ``` --- ## Invalid programs  ```haskell triple_backflip ``` --- ## Invalid programs  ```haskell face -35 ``` --- ## Invalid programs  ```haskell face -35 ``` --- ## Invalid programs  ```haskell face -35 ``` --- class: center, middle name: direction # Representing `Direction` --- ## Magic values .diff-add[ ```scala *​`object Direction:` ``` ] --- ## Magic values .diff-add[ ```scala *object Direction`:` * `val North: Int = ???` * `val East: Int = ???` * `val South: Int = ???` * `val West: Int = ???` ``` ] --- ## Magic values .diff-rm[ ```scala object Direction`:` val North: Int = `???` val East: Int = `???` val South: Int = `???` val West: Int = `???` ``` ] --- ## Magic values .diff-add[ ```scala object Direction: * val North: Int = `1` * val East: Int = `2` * val South: Int = `3` * val West: Int = `4` ``` ] --- ## Magic values ```scala def label(d: Int) = ??? ``` --- ## Magic values ```scala def label(`d: Int`) = ??? ``` --- ## Magic values .diff-rm[ ```scala *def label(d: Int) = `???` ``` ] --- ## Magic values .diff-add[ ```scala *def label(d: Int) = `d match` * `case Direction.North ⇒ ???` * `case Direction.East ⇒ ???` * `case Direction.South ⇒ ???` * `case Direction.West ⇒ ???` ``` ] --- ## Magic values .diff-rm[ ```scala def label(d: Int) = d match * case Direction.North ⇒ `???` * case Direction.East ⇒ `???` * case Direction.South ⇒ `???` * case Direction.West ⇒ `???` ``` ] --- ## Magic values .diff-add[ ```scala def label(d: Int) = d match * case Direction.North ⇒ `"north"` * case Direction.East ⇒ `"east"` * case Direction.South ⇒ `"south"` * case Direction.West ⇒ `"east"` ``` ] --- ## Magic values  ```scala label(-35) ``` --- ## Magic values  ```scala label(`-35`) // 💥 scala.MatchError: -35 ``` --- ## Type aliases .diff-add[ ```scala *​`type Direction = Int` * object Direction: val North: Int = 1 val East: Int = 2 val South: Int = 3 val West: Int = 4 ``` ] --- ## Type aliases .diff-rm[ ```scala type Direction = Int object Direction: * val North: `Int` = 1 * val East: `Int` = 2 * val South: `Int` = 3 * val West: `Int` = 4 ``` ] --- ## Type aliases .diff-add[ ```scala type Direction = Int object Direction: * val North: `Direction` = 1 * val East: `Direction` = 2 * val South: `Direction` = 3 * val West: `Direction` = 4 ``` ] --- ## Type aliases .diff-rm[ ```scala *def label(d: `Int`) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" case Direction.West ⇒ "west" ``` ] --- ## Type aliases .diff-add[ ```scala *def label(d: `Direction`) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" case Direction.West ⇒ "west" ``` ] --- ## Type aliases  ```scala label(-35) ``` --- ## Type aliases  ```scala label(`-35`) // 💥 scala.MatchError: -35 ``` --- ## Scala's `Enumeration` .diff-rm[ ```scala *​`type Direction = Int` object Direction: * `val North: Direction = 1` * `val East: Direction = 2` * `val South: Direction = 3` * `val West: Direction = 4` ``` ] --- ## Scala's `Enumeration` ```scala object Direction: ``` --- ## Scala's `Enumeration` .diff-add[ ```scala *object Direction `extends Enumeration`: ``` ] --- ## Scala's `Enumeration` .diff-add[ ```scala object Direction extends Enumeration: * `val North, East, South, West = Value` ``` ] --- ## Scala's `Enumeration` .diff-rm[ ```scala *def label(d: `Direction`) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" case Direction.West ⇒ "west" ``` ] --- ## Scala's `Enumeration` .diff-add[ ```scala *def label(d: `Direction.Value`) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" case Direction.West ⇒ "west" ``` ] --- ## Scala's `Enumeration`  ```scala label(-35) ``` --- ## Scala's `Enumeration`  ```scala label(`-35`) // ⛔ Found: Int // Required: Direction.Value ``` --- ## Scala's `Enumeration` .diff-rm[ ```scala def label(d: Direction.Value) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" * `case Direction.West ⇒ "west"` ``` ] --- ## Scala's `Enumeration` .diff-add[ ```scala def label(d: Direction.Value) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" *​`//case Direction.West ⇒ "west"` ``` ] --- ## Scala's `Enumeration`  ```scala label(Direction.West) ``` --- ## Scala's `Enumeration`  ```scala label(`Direction.West`) // 💥 scala.MatchError: West ``` --- ## Hand-written enumeration .diff-add[ ```scala *​`trait Direction` ``` ] --- ## Hand-written enumeration .diff-add[ ```scala trait Direction * ​`object Direction:` ``` ] --- ## Hand-written enumeration .diff-add[ ```scala trait Direction object Direction: * `case object North extends Direction` ``` ] --- ## Hand-written enumeration .diff-add[ ```scala trait Direction object Direction: case object North extends Direction * `case object East extends Direction` ``` ] --- ## Hand-written enumeration .diff-add[ ```scala trait Direction object Direction: case object North extends Direction case object East extends Direction * `case object South extends Direction` ``` ] --- ## Hand-written enumeration .diff-add[ ```scala trait Direction object Direction: case object North extends Direction case object East extends Direction case object South extends Direction * `case object West extends Direction` ``` ] --- ## Hand-written enumeration .diff-rm[ ```scala *def label(d: `Direction.Value`) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" //case Direction.West ⇒ "west" ``` ] --- ## Hand-written enumeration .diff-add[ ```scala *def label(d: `Direction`) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" //case Direction.West ⇒ "west" ``` ] --- ## Hand-written enumeration  ```scala label(Direction.West) ``` --- ## Hand-written enumeration  ```scala label(`Direction.West`) // 💥 scala.MatchError: West ``` --- ## Hand-written enumeration .diff-add[ ```scala *​`sealed` trait Direction object Direction: case object North extends Direction case object East extends Direction case object South extends Direction case object West extends Direction ``` ] --- ## Hand-written enumeration ```scala def label(d: Direction) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" //case Direction.West ⇒ "west" ``` --- ## Hand-written enumeration ```scala def label(d: Direction) = d match case Direction.North ⇒ "north" case Direction.East ⇒ "east" case Direction.South ⇒ "south" //case Direction.West ⇒ "west" // ⛔ match may not be exhaustive. // It would fail on pattern case: West ``` --- ## [Key takeaways](#closing) -- Enumerations​: -- * make nonsensical values impossible to represent. -- * guarantee that our code handles all necessary cases. -- * provided you're not using `scala.Enumeration` though... --- class: center, middle name: command # Representing `Command` --- ## Case class ```scala case class Command( ) ​ ​ ``` ```scala val cmd = Command( ) ​ ​ ``` --- ## Case class .diff-add[ ```scala case class Command( * `order: String` ) ​ ``` ```scala val cmd = Command( * `"face"` ) ​ ``` ] --- ## Case class .diff-add[ ```scala case class Command( * order: String`,` * `dir : Option[Direction]` ) ``` ```scala val cmd = Command( * "face"`,` * `Some(Direction.North)` ) ``` ] --- ## Case class  ```scala Command( "triple backflip", Some(Direction.South) ) ``` --- ## Case class  ```scala Command( `"triple backflip"`, Some(Direction.South) ) ``` --- ## Case class  ```scala Command( "triple backflip", Some(Direction.South) ) ``` --- ## `Order` as enumeration .diff-add[ ```scala *​`sealed trait Order` ``` ] --- ## `Order` as enumeration .diff-add[ ```scala sealed trait Order * *​`object Order:` ``` ] --- ## `Order` as enumeration .diff-add[ ```scala sealed trait Order *object Order`:` * `case object Face extends Order` ``` ] --- ## `Order` as enumeration .diff-add[ ```scala sealed trait Order object Order: * `case object Face extends Order` * `case object Start extends Order` ``` ] --- ## `Order` as enumeration .diff-add[ ```scala sealed trait Order object Order: * `case object Face extends Order` * `case object Start extends Order` * `case object Stop extends Order` ``` ] --- ## `Order` as enumeration .diff-rm[ ```scala case class Command( * order: `String`, dir : Option[Direction] ) ``` ```scala val cmd = Command( * `"face"`, Some(Direction.North) ) ``` ] --- ## `Order` as enumeration .diff-add[ ```scala case class Command( * order: `Order`, dir : Option[Direction] ) ``` ```scala val cmd = Command( * `Order.Face`, Some(Direction.North) ) ``` ] --- ## `Order` as enumeration  ```scala Command( "triple backflip", Some(Direction.South) ) ``` --- ## `Order` as enumeration  ```scala Command( `"triple backflip"`, Some(Direction.South) ) // ⛔ Found: String // Required: Order ``` --- ## `Order` as enumeration  .diff-rm[ ```scala Command( * `"triple backflip"`, Some(Direction.South) ) ``` ] --- ## `Order` as enumeration  .diff-add[ ```scala Command( * `Order.Start`, Some(Direction.South) ) ``` ] --- ## `Order` as enumeration  ```scala Command( Order.`Start`, Some(Direction.`South`) ) ``` --- ## `Order` as enumeration  ```scala Command( Order.Start, Some(Direction.South) ) ``` --- ## `Order` as "enumeration" .diff-rm[ ```scala sealed trait Order object Order: * case `o​bject Face` extends Order case object Start extends Order case object Stop extends Order ``` ] --- ## `Order` as "enumeration" .diff-add[ ```scala sealed trait Order object Order: * case `c​lass Face(dir: Direction)` extends Order * case object Start extends Order * case object Stop extends Order ``` ] --- ## `Order` as "enumeration" .diff-rm[ ```scala *sealed trait `Order` *object `Order`: * case class Face(dir: Direction) extends `Order` * case object Start extends `Order` * case object Stop extends `Order` ``` ] --- ## `Command` as "enumeration" .diff-add[ ```scala *sealed trait `Command` *object `Command`: * case class Face(dir: Direction) extends `Command` * case object Start extends `Command` * case object Stop extends `Command` ``` ] --- ## `Command` as "enumeration"  ```scala Command( Order.Start, Some(Direction.South) ) ``` --- ## `Command` as "enumeration"  ```scala ​`Command`( Order.Start, Some(Direction.South) ) // ⛔ object Command does not take parameters ``` --- ## `Command` as "enumeration"  ```scala Command.Start ``` --- ## `Command` as "enumeration"  ```scala Command.Start ``` --- ## [Key takeaways](#closing) -- * Enumerations are everywhere. -- * Enumerations are not enough. -- * Something "like an enumeration" might be, however. --- class: center, middle name: composition # Composing commands --- ## Script  ```haskell start ``` --- ## Script  ```haskell face east start stop ``` --- ## Script  ```haskell face east start stop ``` --- ## Script  ```haskell ​`face east` start stop ``` --- ## Script  ```haskell face east ​`start` stop ``` --- ## Script  ```haskell face east start ​`stop` ``` --- ## Chaining commands .diff-add[ ```scala sealed trait Command object Command: case class Face(dir: Direction) extends Command case object Start extends Command case object Stop extends Command * * `case class Chain(` * `) extends Command` ``` ] --- ## Chaining commands .diff-add[ ```scala sealed trait Command object Command: case class Face(dir: Direction) extends Command case object Start extends Command case object Stop extends Command case class Chain( * `cmd1: Command` ) extends Command ``` ] --- ## Chaining commands .diff-add[ ```scala sealed trait Command object Command: case class Face(dir: Direction) extends Command case object Start extends Command case object Stop extends Command case class Chain( * cmd1: Command`,` * `cmd2: Command` ) extends Command ``` ] --- ## Chaining commands ```scala Command.Chain( Command.Chain( Command.Chain( Command.Face(Direction.East), Command.Chain( Command.Start, Command.Stop ) ), Command.Face(Direction.West) ), Command.Chain( Command.Start, Command.Stop ) ) ``` --- ## Chaining commands ```scala Command.Chain( Command.Chain( Command.Chain( Command.`Face`(Direction.`East`), Command.Chain( Command.Start, Command.Stop ) ), Command.Face(Direction.West) ), Command.Chain( Command.Start, Command.Stop ) ) ``` --- ## Chaining commands ```scala Command.Chain( Command.Chain( Command.Chain( Command.Face(Direction.East), Command.Chain( Command.`Start`, Command.Stop ) ), Command.Face(Direction.West) ), Command.Chain( Command.Start, Command.Stop ) ) ``` --- ## Chaining commands ```scala Command.Chain( Command.Chain( Command.Chain( Command.Face(Direction.East), Command.Chain( Command.Start, Command.`Stop` ) ), Command.Face(Direction.West) ), Command.Chain( Command.Start, Command.Stop ) ) ``` --- ## Chaining commands ```scala Command.Chain( Command.Chain( Command.Chain( Command.Face(Direction.East), Command.Chain( Command.Start, Command.Stop ) ), Command.`Face`(Direction.`West`) ), Command.Chain( Command.Start, Command.Stop ) ) ``` --- ## Chaining commands ```scala Command.Chain( Command.Chain( Command.Chain( Command.Face(Direction.East), Command.Chain( Command.Start, Command.Stop ) ), Command.Face(Direction.West) ), Command.Chain( Command.`Start`, Command.Stop ) ) ``` --- ## Chaining commands ```scala Command.Chain( Command.Chain( Command.Chain( Command.Face(Direction.East), Command.Chain( Command.Start, Command.Stop ) ), Command.Face(Direction.West) ), Command.Chain( Command.Start, Command.`Stop` ) ) ``` --- ## DSL ```scala extension (cmd1: Command) def ~>(cmd2: Command): Command = Command.Chain(cmd1, cmd2) ``` ```scala val startStop: Command = Command.Start ~> Command.Stop ``` --- ## DSL ```scala extension (`cmd1: Command`) def ~>(cmd2: Command): Command = Command.Chain(cmd1, cmd2) ``` ```scala val startStop: Command = `Command.Start` ~> Command.Stop ``` --- ## DSL ```scala extension (cmd1: Command) def `~>`(cmd2: Command): Command = Command.Chain(cmd1, cmd2) ``` ```scala val startStop: Command = Command.Start `~>` Command.Stop ``` --- ## DSL ```scala extension (cmd1: Command) def ~>(`cmd2: Command`): Command = Command.Chain(cmd1, cmd2) ``` ```scala val startStop: Command = Command.Start ~> Command.`Stop` ``` --- ## DSL ```scala extension (cmd1: Command) def ~>(cmd2: Command): Command = Command.`Chain(cmd1, cmd2)` ``` ```scala val `startStop`: Command = Command.Start ~> Command.Stop ``` --- ## DSL .diff-add[ ```scala *​`val start = Command.Start` ``` ] --- ## DSL .diff-add[ ```scala val start = Command.Start *​`val stop = Command.Stop` ``` ] --- ## DSL .diff-add[ ```scala val start = Command.Start val stop = Command.Stop *​`def face(dir: Direction) = Command.Face(dir)` ``` ] --- ## DSL .diff-add[ ```scala *​`val north = Direction.North` ``` ] --- ## DSL .diff-add[ ```scala val north = Direction.North *​`val east = Direction.East` ``` ] --- ## DSL .diff-add[ ```scala val north = Direction.North val east = Direction.East *​`val south = Direction.South` ``` ] --- ## DSL .diff-add[ ```scala val north = Direction.North val east = Direction.East val south = Direction.South *​`val west = Direction.West` ``` ] --- ## Compound commands ```scala def move(d: Direction) = face(d) ~> start ~> stop ``` --- ## Compound commands ```scala def move(`d: Direction`) = face(d) ~> start ~> stop ``` --- ## Compound commands ```scala def move(d: Direction) = `face(d)` ~> start ~> stop ``` --- ## Compound commands ```scala def move(d: Direction) = face(d) ~> `start` ~> stop ``` --- ## Compound commands ```scala def move(d: Direction) = face(d) ~> start ~> `stop` ``` --- ## Compound commands  ```scala move(east) ~> move(west) ``` --- ## Compound commands  ```scala move(east) ~> move(west) ``` --- ## Compound commands  ```scala ​`move(east)` ~> move(west) ``` --- ## Compound commands  ```scala ​`move(east)` ~> move(west) ``` --- ## Compound commands  ```scala ​`move(east)` ~> move(west) ``` --- ## Compound commands  ```scala move(east) ~> `move(west)` ``` --- ## Compound commands  ```scala move(east) ~> `move(west)` ``` --- ## Compound commands  ```scala move(east) ~> `move(west)` ``` --- ## [Key takeaways](#closing) -- We've completed our data structure by using: -- * records (`Chain`, `Face`). -- * enumerated types (`Command`, `Direction`). -- * recursive types (`Command` is expressed in terms of itself). --- class: center, middle name: adt # Algebraic Data Types --- ## Sum types ```scala Command = Face | Start | Stop | Chain ``` --- ## Sum types ```scala Command = `Face` | Start | Stop | Chain ``` --- ## Sum types ```scala Command = Face | `Start` | Stop | Chain ``` --- ## Sum types ```scala Command = Face | Start | `Stop` | Chain ``` --- ## Sum types ```scala Command = Face | Start | Stop | `Chain` ``` --- ## Sum types ```scala Command = Face | Start | Stop | Chain ``` > A sum type is a discriminated union of values, and can be thought of as an `OR` on types. --- ## Sum types ```scala Command = Face `|` Start `|` Stop `|` Chain ``` > A sum type is a discriminated union of values, and can be thought of as an .highlight[`OR`] on types. --- ## Sum types ```scala Command = Face | Start | Stop | Chain ``` > A sum type is a .highlight[discriminated] union of values, and can be thought of as an `OR` on types. --- ## Union types ```c union int_or_string { int as_int; char* as_string; }; ``` --- ## Union types ```c union `int_or_string` { int as_int; char* as_string; }; ``` --- ## Union types ```c union int_or_string { `int as_int;` char* as_string; }; ``` --- ## Union types ```c union int_or_string { int as_int; `char* as_string;` }; ``` --- ## Union types ```c #include<stdio.h> void print_union(union int_or_string e) { ??? } ``` --- ## Union types ```c #include<stdio.h> void print_union(union int_or_string e) { `???` } ``` --- ## Manually discriminated union types ```c enum typetag { int_tag, string_tag }; ``` --- ## Manually discriminated union types ```c enum `typetag` { int_tag, string_tag }; ``` --- ## Manually discriminated union types ```c enum typetag { `int_tag`, string_tag }; ``` --- ## Manually discriminated union types ```c enum typetag { int_tag, `string_tag` }; ``` --- ## Manually discriminated union types ```c union int_or_string { int as_int; char* as_string; }; ``` --- ## Manually discriminated union types .diff-add[ ```c union int_or_string { * `enum typetag discriminator;` * int as_int; char* as_string; }; ``` ] --- ## Manually discriminated union types .diff-rm[ ```c *​`union` int_or_string { enum typetag discriminator; int as_int; char* as_string; }; ``` ] --- ## Manually discriminated union types .diff-add[ ```c *​`struct` int_or_string { enum typetag discriminator; int as_int; char* as_string; }; ``` ] --- ## Manually discriminated union types .diff-rm[ ```c struct int_or_string { enum typetag discriminator; * `int as_int;` * `char* as_string;` }; ``` ] --- ## Manually discriminated union types .diff-add[ ```c struct int_or_string { enum typetag discriminator; * `union {` * ` int as_int;` * ` char* as_string;` * `} value;` }; ``` ] --- ## Manually discriminated union types ```c struct int_or_string { enum typetag discriminator; * union { * int as_int; * char* as_string; * } value; }; ``` --- ## Manually discriminated union types ```c struct int_or_string { * enum typetag discriminator; union { int as_int; char* as_string; } value; }; ``` --- ## Manually discriminated union types .diff-rm[ ```c #include<stdio.h> *void print_union(`union` int_or_string e) { ??? } ``` ] --- ## Manually discriminated union types .diff-add[ ```c #include<stdio.h> *void print_union(`struct` int_or_string e) { ??? } ``` ] --- ## Manually discriminated union types .diff-rm[ ```c #include<stdio.h> void print_union(struct int_or_string e) { * `???` } ``` ] --- ## Manually discriminated union types .diff-add[ ```c #include<stdio.h> void print_union(struct int_or_string e) { * `if(e.discriminator == int_tag) {` * `printf("int: %i", e.value.as_int);` * `}` * `else {` * `printf("string: %s", e.value.as_string);` * `}` } ``` ] --- ## Manually discriminated union types ```c #include<stdio.h> void print_union(struct int_or_string e) { if(`e.discriminator == int_tag`) { printf("int: %i", e.value.as_int); } else { printf("string: %s", e.value.as_string); } } ``` --- ## Manually discriminated union types ```c #include<stdio.h> void print_union(struct int_or_string e) { if(e.discriminator == int_tag) { printf("int: %i", `e.value.as_int`); } else { printf("string: %s", e.value.as_string); } } ``` --- ## Manually discriminated union types ```c #include<stdio.h> void print_union(struct int_or_string e) { if(e.discriminator == int_tag) { printf("int: %i", e.value.as_int); } else { printf("string: %s", `e.value.as_string`); } } ``` --- ## Sum types ```scala Command = Face | Start | Stop | Chain ``` > A sum type is a .highlight[discriminated] union of values, and can be thought of as an `OR` on types. --- ## Sum types > An ADT is a sum type [...] --- ## Product types ```scala Command = Face | Start | Stop | Chain ``` --- ## Product types .diff-rm[ ```scala Command = Face | Start | Stop * | `Chain` ``` ] --- ## Product types .diff-add[ ```scala Command = Face | Start | Stop * | `Command & Command` ``` ] --- ## Product types ```scala Command = Face | Start | Stop | `Command` & Command ``` --- ## Product types ```scala Command = Face | Start | Stop | Command & `Command` ``` --- ## Product types ```scala Command = Face | Start | Stop | Command & Command ``` > A product type is an aggregation of values, and can be thought of as an `AND` on types. --- ## Product types ```scala Command = Face | Start | Stop | Command `&` Command ``` > A product type is an aggregation of values, and can be thought of as an .highlight[`AND`] on types. --- ## Product types > An ADT is a sum type of product types [...] --- ## Algebraic Data Types ```scala Command = Face | Start | Stop | Command & Command ``` --- ## Algebraic Data Types ```scala ​`Command` = Face | Start | Stop | Command & Command ``` --- ## Algebraic Data Types ```scala Command = Face | Start | Stop | `Command` & `Command` ``` --- ## Algebraic Data Types > An ADT is a potentially recursive sum type of product types. --- ## Dedicated syntax ```scala sealed trait Command object Command: case class Face(dir: Direction) extends Command case object Start extends Command case object Stop extends Command case class Chain( cmd1: Command, cmd2: Command ) extends Command ``` --- ## Dedicated syntax .diff-rm[ ```scala *​`sealed trait Command` * *​`object` Command: case class Face(dir: Direction) extends Command case object Start extends Command case object Stop extends Command case class Chain( cmd1: Command, cmd2: Command ) extends Command ``` ] --- ## Dedicated syntax .diff-add[ ```scala *​`enum` Command: case class Face(dir: Direction) extends Command case object Start extends Command case object Stop extends Command case class Chain( cmd1: Command, cmd2: Command ) extends Command ``` ] --- ## Dedicated syntax .diff-rm[ ```scala enum Command: * case `c​lass` Face(dir: Direction) extends Command * case `o​bject` Start extends Command * case `ob​ject` Stop extends Command * case `c​lass` Chain( cmd1: Command, cmd2: Command ) extends Command ``` ] --- ## Dedicated syntax .diff-rm[ ```scala enum Command: * case Face(dir: Direction) `extends Command` * case Start `extends Command` * case Stop `extends Command` case Chain( cmd1: Command, cmd2: Command * ) `extends Command` ``` ] --- ## Dedicated syntax ```scala enum Command: case Face(dir: Direction) case Start case Stop case Chain( cmd1: Command, cmd2: Command ) ``` --- ## [Key takeaways](#closing) -- Algebraic Data Types are: -- * sum types. -- * product types. -- * potentially recursive. --- class: center, middle name: safe-composition # Safe command composition --- ## Illegal state transition  ```scala start ~> start ``` --- ## Illegal state transition  ```scala `start` ~> start ``` --- ## Illegal state transition  ```scala start ~> `start` ``` --- ## Illegal state transition  ```scala start ~> start ``` --- ## Illegal state transition  ```scala stop ~> stop ``` --- ## Illegal state transition  ```scala `stop` ~> stop ``` --- ## Illegal state transition  ```scala stop ~> `stop` ``` --- ## Illegal state transition  ```scala stop ~> stop ``` --- ## Illegal state transition  ```scala start ~> face(north) ``` --- ## Illegal state transition  ```scala `start` ~> face(north) ``` --- ## Illegal state transition  ```scala start ~> `face(north)` ``` --- ## Illegal state transition  .foreground[] ```scala start ~> face(north) ``` --- ## Tracking state ```scala final abstract class Idle final abstract class Moving ``` --- ## Tracking state ```scala final abstract class `Idle` final abstract class Moving ``` --- ## Tracking state ```scala final abstract class Idle final abstract class `Moving` ``` --- ## Tracking state .diff-add[ ```scala *enum Command`[Before, After]`: case Face(dir: Direction) case Start case Stop case Chain( cmd1: Command, cmd2: Command ) ``` ] --- ## Tracking state .diff-add[ ```scala enum Command[Before, After]: * case Face(dir: Direction) `extends Command[Idle, Idle]` case Start case Stop case Chain( cmd1: Command, cmd2: Command ) ``` ] --- ## Tracking state .diff-add[ ```scala enum Command[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] * case Start `extends Command[Idle, Moving]` case Stop case Chain( cmd1: Command, cmd2: Command ) ``` ] --- ## Tracking state .diff-add[ ```scala enum Command[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] case Start extends Command[Idle, Moving] * case Stop `extends Command[Moving, Idle]` case Chain( cmd1: Command, cmd2: Command ) ``` ] --- ## Tracking state ```scala enum Command[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] case Start extends Command[Idle, Moving] case Stop extends Command[Moving, Idle] `case Chain(` `cmd1: Command,` `cmd2: Command` `)` ``` --- ## Tracking state .diff-add[ ```scala enum Command[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] case Start extends Command[Idle, Moving] case Stop extends Command[Moving, Idle] case Chain( * cmd1: Command`[A, B]`, cmd2: Command ) ``` ] --- ## Tracking state .diff-add[ ```scala enum Command[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] case Start extends Command[Idle, Moving] case Stop extends Command[Moving, Idle] case Chain( cmd1: Command[A, B], * cmd2: Command`[B, C]` ) ``` ] --- ## Tracking state ```scala enum Command[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] case Start extends Command[Idle, Moving] case Stop extends Command[Moving, Idle] case Chain( cmd1: Command[A, `B`], cmd2: Command[`B`, C] ) ``` --- ## Tracking state .diff-add[ ```scala enum Command[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] case Start extends Command[Idle, Moving] case Stop extends Command[Moving, Idle] case Chain( cmd1: Command[A, B], cmd2: Command[B, C] * ) `extends Command[A, C]` ``` ] --- ## Tracking state .diff-add[ ```scala enum Command[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] case Start extends Command[Idle, Moving] case Stop extends Command[Moving, Idle] * case Chain`[A, B, C]`( cmd1: Command[A, B], cmd2: Command[B, C] ) extends Command[A, C] ``` ] --- ## DSL .diff-add[ ```scala *extension (cmd1: Command`[A, B]`) def ~>(cmd2: Command): Command = Command.Chain(cmd1, cmd2) ``` ] --- ## DSL .diff-add[ ```scala *extension `[A, B]`(cmd1: Command[A, B]) def ~>(cmd2: Command): Command = Command.Chain(cmd1, cmd2) ``` ] --- ## DSL .diff-add[ ```scala extension [A, B](cmd1: Command[A, B]) * def ~>(cmd2: Command`[B, C]`): Command = Command.Chain(cmd1, cmd2) ``` ] --- ## DSL .diff-add[ ```scala extension [A, B](cmd1: Command[A, B]) * def ~>[`C`](cmd2: Command[B, C]): Command = Command.Chain(cmd1, cmd2) ``` ] --- ## DSL .diff-add[ ```scala extension [A, B](cmd1: Command[A, B]) * def ~>[C](cmd2: Command[B, C]): Command`[A, C]` = Command.Chain(cmd1, cmd2) ``` ] --- ## Illegal state transition  ```scala start ~> start ``` --- ## Illegal state transition  ```scala start ~> `start` // ⛔ Found: Command[Idle, Moving] // Required: Command[Moving, C] ``` --- ## Illegal state transition  ```scala stop ~> stop ``` --- ## Illegal state transition  ```scala stop ~> `stop` // ⛔ Found: Command[Moving, Idle] // Required: Command[Idle, C] ``` --- ## Illegal state transition  ```scala start ~> face(north) ``` --- ## Illegal state transition  ```scala start ~> `face(north)` // ⛔ Found: Command[Idle, Idle] // Required: Command[Moving, C] ``` --- ## Safe state transition  ```scala face(east) ~> start ~> stop ``` --- ## Safe state transition  ```scala face(east) ~> start ~> stop ``` --- ## Safe state transition  ```scala ​`face(east)` ~> start ~> stop ``` --- ## Safe state transition  ```scala face(east) ~> `start` ~> stop ``` --- ## Safe state transition  ```scala face(east) ~> start ~> `stop` ``` --- ## Smarter exhaustivity checks ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" case _: Command.Chain[_, _, _] => "chain" ``` --- ## Smarter exhaustivity checks ```scala def movingLabel(cmd: `Command[Moving, _]`) = cmd match case Command.Stop => "stop" case _: Command.Chain[_, _, _] => "chain" ``` --- ## Smarter exhaustivity checks ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case `Command.Stop` => "stop" case _: Command.Chain[_, _, _] => "chain" ``` --- ## Smarter exhaustivity checks ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" case _: `Command.Chain[_, _, _]` => "chain" ``` --- ## Smarter exhaustivity checks  ```scala movingLabel(Command.Start) ``` --- ## Smarter exhaustivity checks  ```scala movingLabel(`Command.Start`) // ⛔ Found: Command[Idle, Moving] // Required: Command[Moving, ?] ``` --- ## Smarter exhaustivity checks .diff-rm[ ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" * `case _: Command.Chain[_, _, _] => "chain"` ``` ] --- ## Smarter exhaustivity checks .diff-add[ ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" *​`//case _: Command.Chain[_, _, _] => "chain"` ``` ] --- ## Smarter exhaustivity checks ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" //case _: `Command.Chain[_, _, _]` => "chain" // ⛔ match may not be exhaustive. // It would fail on pattern case: Command.Chain(_, _) ``` --- ## Smarter exhaustivity checks .diff-rm[ ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" *​`//case _: Command.Chain[_, _, _] => "chain"` ``` ] --- ## Smarter exhaustivity checks .diff-add[ ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" case _: Command.Chain[_, _, _] => "chain" * `case Command.Start => "start"` ``` ] --- ## Smarter exhaustivity checks ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" case _: Command.Chain[_, _, _] => "chain" case `Command.Start` => "start" // ⛔ Found: Command[Idle, Moving] // Required: Command[Moving, ?] ``` --- ## [Key takeaways](#closing) -- We used type constraints on our sum type's members to: -- * make illegal state transitions impossible to represent. -- * guarantee that our code handles all necessary cases. -- * guarantee that our code handles *only* necessary cases. --- class: center, middle name: gadt # Generalised Algebraic Data Types --- ## Sum type ```scala enum Command[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] case Start extends Command[Idle, Moving] case Stop extends Command[Moving, Idle] case Chain[A, B, C]( cmd1: Command[A, B], cmd2: Command[B, C] ) extends Command[A, C] ``` --- ## Sum type ```scala enum `Command`[Before, After]: case Face(dir: Direction) extends Command[Idle, Idle] case Start extends Command[Idle, Moving] case Stop extends Command[Moving, Idle] case Chain[A, B, C]( cmd1: Command[A, B], cmd2: Command[B, C] ) extends Command[A, C] ``` --- ## Sum type ```scala enum Command[Before, After]: case `Face`(dir: Direction) extends Command[Idle, Idle] case `Start` extends Command[Idle, Moving] case `Stop` extends Command[Moving, Idle] case `Chain`[A, B, C]( cmd1: Command[A, B], cmd2: Command[B, C] ) extends Command[A, C] ``` --- ## Sum type > A GADT is a sum type [...] --- ## Witness type ```scala enum Command[`Before`, After]: case Face(dir: Direction) extends Command[`Idle`, Idle] case Start extends Command[`Idle`, Moving] case Stop extends Command[`Moving`, Idle] case Chain[A, B, C]( cmd1: Command[A, B], cmd2: Command[B, C] ) extends Command[`A`, C] ``` --- ## Witness type ```scala enum Command[Before, `After`]: case Face(dir: Direction) extends Command[Idle, `Idle`] case Start extends Command[Idle, `Moving`] case Stop extends Command[Moving, `Idle`] case Chain[A, B, C]( cmd1: Command[A, B], cmd2: Command[B, C] ) extends Command[A, `C`] ``` --- ## Witness type > A witness type describes properties of a sum type's variants at the type level. --- ## GADT > A GADT is a sum type with one or more witness types [...] --- ## Type equality ```scala def movingLabel(cmd: Command[`Moving`, _]) = cmd match case Command.Stop => "stop" //case _: Command.Chain[_, _, _] => "chain" case Command.Start => "start" ``` --- ## Type equality ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" ​`//case _: Command.Chain[_, _, _] => "chain"` case Command.Start => "start" ``` --- ## Type equality ```scala def movingLabel(cmd: Command[Moving, _]) = cmd match case Command.Stop => "stop" //case _: Command.Chain[_, _, _] => "chain" `case Command.Start => "start"` ``` --- ## Type equality > Type equality is information available to the compiler about each witness type, allowing it to refine pattern matches. --- ## GADT > A GADT is a sum type with one or more witness types, each equipped with a type equality. --- ## [Key takeaways](#closing) -- * A GADT is a sum type with one or more witness types, each equipped with a type equality. --- ## [Key takeaways](#closing) * ~~A GADT is a sum type with one or more witness types, each equipped with a type equality.~~ -- * A GADTs is a sum type with interesting properties for pattern matching. --- class: center, middle name: algebra # The algebra of types --- ## Cardinality > The cardinality of type `A` is written \\(\\vert A \\vert\\) and is the number of values of type `A`. --- ## Cardinality .center[] --- ## Cardinality .center[] -- \\(\vert Nothing \\vert = 0\\) --- ## Cardinality .center[] --- ## Cardinality .center[] -- \\(\vert Unit \\vert = 1\\) --- ## Cardinality .center[] --- ## Cardinality .center[] --- ## Cardinality .center[] -- \\(\vert Boolean \\vert = 2\\) --- ## Sum types ```scala enum +[+A, +B]: case Left[A](value: A) extends +[A, Nothing] case Right[B](value: B) extends +[Nothing, B] ``` --- ## Sum types ```scala enum `+[+A, +B]`: case Left[A](value: A) extends +[A, Nothing] case Right[B](value: B) extends +[Nothing, B] ``` --- ## Sum types ```scala enum +[+A, +B]: case `Left[A]`(value: A) extends +[A, Nothing] case Right[B](value: B) extends +[Nothing, B] ``` --- ## Sum types ```scala enum +[+A, +B]: case Left[A](`value: A`) extends +[A, Nothing] case Right[B](value: B) extends +[Nothing, B] ``` --- ## Sum types ```scala enum +[+A, +B]: case Left[A](value: A) extends +[A, Nothing] case `Right[B]`(value: B) extends +[Nothing, B] ``` --- ## Sum types ```scala enum +[+A, +B]: case Left[A](value: A) extends +[A, Nothing] case Right[B](`value: B`) extends +[Nothing, B] ``` --- ## Sum types .diff-rm[ ```scala enum +[+A, +B]: * case Left[A](value: A) extends `+[A, Nothing]` * case Right[B](value: B) extends `+[Nothing, B]` ``` ] --- ## Sum types .diff-add[ ```scala enum +[+A, +B]: * case Left[A](value: A) extends `(A + Nothing)` * case Right[B](value: B) extends `(Nothing + B)` ``` ] --- ## Sum types .center[] --- ## Sum types .center[] --- ## Sum types .center[] --- ## Sum types .center[] \\(\vert A + B \\vert = \vert A \vert \ldots\\) --- ## Sum types .center[] \\(\vert A + B \\vert = \vert A \vert + \vert B \vert \\) --- ## Type isomorphisms > We'll say that types `A` and `B` are isomorphic if they have the same cardinality, and write `A ~= B`. --- ## Type isomorphisms > We'll say that types `A` and `B` are isomorphic if they have the same cardinality, and write .highlight[`A ~= B`]. --- ## Sum types .section[Algebra] ```scala 1 + 1 = 2 ``` -- .section[Types] ```scala Unit + Unit ~= Boolean ``` --- ## Sum types .section[Algebra] ```scala ​`1` + `1` = 2 ``` .section[Types] ```scala ​`Unit` + `Unit` ~= Boolean ``` --- ## Sum types .section[Algebra] ```scala 1 + 1 = `2` ``` .section[Types] ```scala Unit + Unit ~= `Boolean` ``` --- ## Sum types .section[Algebra] ```scala 1 `+` 1 = 2 ``` .section[Types] ```scala Unit `+` Unit ~= Boolean ``` --- ## Sum types .section[Algebra] ```scala 1 + 1 `=` 2 ``` .section[Types] ```scala Unit + Unit `~=` Boolean ``` --- ## Sum types .center[] --- ## Sum types .center[] --- ## Sum types .center[] --- ## Sum types .center[] --- ## Sum types .center[] --- ## Sum types .center[] --- ## Sum types associativity .section[Algebra] ```scala a + (b + c) = (a + b) + c ``` -- .section[Types] ```scala A + (B + C) ~= (A + B) + C ``` --- ## Sum types associativity .center[] --- ## Sum types associativity .center[] --- ## Sum types associativity .center[] --- ## Sum types associativity .center[] --- ## Sum types associativity .center[] --- ## Sum types associativity .center[] --- ## Sum types associativity .center[] --- ## Sum types associativity .center[] --- ## Sum types commutativity .section[Algebra] ```scala a + b = b + a ``` -- .section[Types] ```scala A + B ~= B + A ``` --- ## Sum types commutativity .center[] --- ## Sum types commutativity .center[] --- ## Sum types commutativity .center[] --- ## Sum types commutativity .center[] --- ## Sum types commutativity .center[] --- ## Sum types commutativity .center[] --- ## Sum types neutral element .section[Algebra] ```scala a + 0 = a ``` -- .section[Types] ```scala A + Nothing ~= A ``` --- ## Sum types neutral element .center[] --- ## Sum types neutral element .center[] --- ## Sum types neutral element .center[] --- ## Sum types neutral element .center[] --- ## Sum types neutral element .center[] --- ## Product types ```scala case class ✕[A, B](first: A, second: B) ``` --- ## Product types ```scala case class `✕[A, B]`(first: A, second: B) ``` --- ## Product types ```scala case class ✕[A, B](`first: A`, second: B) ``` --- ## Product types ```scala case class ✕[A, B](first: A, `second: B`) ``` --- ## Product types ```scala extension [A](a: A) def ✕[B](b: B): ✕[A, B] = new ✕(a, b) ``` --- ## Product types ```scala extension [A](`a: A`) def ✕[B](b: B): ✕[A, B] = new ✕(a, b) ``` --- ## Product types ```scala extension [A](a: A) def `✕`[B](b: B): ✕[A, B] = new ✕(a, b) ``` --- ## Product types ```scala extension [A](a: A) def ✕[B](`b: B`): ✕[A, B] = new ✕(a, b) ``` --- ## Product types ```scala extension [A](a: A) def ✕[B](b: B): `✕[A, B]` = new ✕(a, b) ``` --- ## Product types .diff-rm[ ```scala extension [A](a: A) * def ✕[B](b: B): `✕[A, B]` = new ✕(a, b) ``` ] --- ## Product types .diff-add[ ```scala extension [A](a: A) * def ✕[B](b: B): `A ✕ B` = new ✕(a, b) ``` ] --- ## Product types .center[] --- ## Product types .center[] --- ## Product types .center[] --- ## Product types .center[] --- ## Product types .center[] \\(\vert A \times B \\vert = \vert A \vert \ldots\\) --- ## Product types .center[] \\(\vert A \times B \\vert = \vert A \vert \times \vert B \vert \\) --- ## Product types .section[Algebra] ```scala a + a = 2 * a ``` -- .section[Types] ```scala A + A ~= Boolean ✕ A ``` --- ## Product types .section[Algebra] ```scala a + a = 2 `*` a ``` .section[Types] ```scala A + A ~= Boolean `✕` A ``` --- ## Product types .center[] --- ## Product types .center[] --- ## Product types .center[] --- ## Product types .center[] --- ## Product types .center[] --- ## Product types .center[] --- ## Product types associativity .section[Algebra] ```scala (a * b) * c = a * (b * c) ``` -- .section[Types] ```scala (A ✕ B) ✕ C ~= A ✕ (B ✕ C) ``` --- ## Product types associativity .center[] --- ## Product types associativity .center[] --- ## Product types associativity .center[] --- ## Product types associativity .center[] --- ## Product types commutativity .section[Algebra] ```scala a * b = b * a ``` -- .section[Types] ```scala A ✕ B ~= B ✕ A ``` --- ## Product types commutativity .center[] --- ## Product types commutativity .center[] --- ## Product types commutativity .center[] --- ## Product types commutativity .center[] --- ## Product types neutral element .section[Algebra] ```scala a * 1 = a ``` -- .section[Types] ```scala A ✕ Unit ~= A ``` --- ## Product types neutral element .center[] --- ## Product types neutral element .center[] --- ## Product types neutral element .center[] --- ## Product types neutral element .center[] --- ## Recursive types ```scala enum List[+A]: case Nil case Cons(head: A, tail: List[A]) ``` --- ## Recursive types ```scala enum `List[+A]`: case Nil case Cons(head: A, tail: List[A]) ``` --- ## Recursive types ```scala enum List[+A]: case `Nil` case Cons(head: A, tail: List[A]) ``` --- ## Recursive types ```scala enum List[+A]: case Nil case `Cons`(head: A, tail: List[A]) ``` --- ## Recursive types ```scala enum List[+A]: case Nil case Cons(`head: A`, tail: List[A]) ``` --- ## Recursive types ```scala enum List[+A]: case Nil case Cons(head: A, `tail: List[A]`) ``` --- ## Recursive types ```scala enum `List[+A]`: case Nil case Cons(head: A, tail: List[A]) ``` --- ## List of fixed size \\( \vert List_0[A] \vert\\) --- ## List of fixed size \\( \vert List_0[A] \vert = \vert Nil \vert\\) --- ## List of fixed size \\( \vert List_0[A] \vert = 1\\) --- ## List of fixed size \\( \vert List_1[A] \vert\\) --- ## List of fixed size \\( \vert List_1[A] \vert = \vert A \times List_0[A] \vert\\) --- ## List of fixed size \\( \vert List_1[A] \vert = \vert A \vert \times \vert List_0[A] \vert\\) --- ## List of fixed size \\( \vert List_1[A] \vert = \vert A \vert \times 1\\) --- ## List of fixed size \\( \vert List_1[A] \vert = \vert A \vert\\) --- ## List of fixed size \\( \vert List_2[A] \vert\\) --- ## List of fixed size \\( \vert List_2[A] \vert = \vert A \times List_1[A] \vert\\) --- ## List of fixed size \\( \vert List_2[A] \vert = \vert A \vert \times \vert List_1[A] \vert\\) --- ## List of fixed size \\( \vert List_2[A] \vert = \vert A \vert \times \vert A \vert\\) --- ## List of fixed size \\( \vert List_2[A] \vert = \vert A \vert^2\\) --- ## List of fixed size \\( \vert List_n[A] \vert = \vert A \vert^n\\) --- ## List of maximum size \\( \vert List^n[A] \vert\\) --- ## List of maximum size \\(\\vert List^n[A] \\vert = \vert \displaystyle\sum_{i = 0}^n List_i[A] \vert^i\\) --- ## List of maximum size \\(\\vert List^n[A] \\vert = \displaystyle\sum_{i = 0}^n \vert List_i[A] \vert\\) --- ## List of maximum size \\(\\vert List^n[A] \\vert = \displaystyle\sum_{i = 0}^n \vert A \vert^i\\) --- ## List of maximum size \\(\\vert List^n[A] \\vert = \frac{\vert A \vert^{n + 1} - 1}{\vert A \vert - 1}\\) --- ## List of maximum size \\(\\vert List^2[Boolean] \\vert = \frac{\vert Boolean \vert^{2 + 1} - 1}{\vert Boolean \vert - 1}\\) --- ## List of maximum size \\(\\vert List^2[Boolean] \\vert = \frac{2^{2 + 1} - 1}{2 - 1}\\) --- ## List of maximum size \\(\\vert List^2[Boolean] \\vert = 7\\) --- ## List of maximum size .center[] --- ## List of maximum size .center[] --- ## List of maximum size .center[] --- ## List of maximum size .center[] --- ## List of maximum size .center[] --- ## [Key takeaways](#closing) -- * ADTs have a deep connection to the algebra you know. -- * you can use this connection to prove fun facts about types. -- * you can also use it to pad talks and look clever. --- class: center, middle name: closing # In closing --- ## If you only remember 1 slide... -- * ADTs make data structures simpler and safer. -- * So do GADTs, only more so. -- * Thinking about data structures that way will have a lasting impact on the way you write code. --- class: center, middle name: questions [<img src="img/qr-code.svg" width="50%" height="50%"/>][Slides] [Nicolas Rinaudo] • [@NicolasRinaudo@functional.cafe] [@NicolasRinaudo@functional.cafe]:https://functional.cafe/@NicolasRinaudo [Nicolas Rinaudo]:https://nrinaudo.github.io/ [Slides]:https://nrinaudo.github.io/far-more-adt/ --- ## Table of contents * [Representing Direction](#direction) * [Representing Command](#command) * [Composing commands](#composition) * [Algebraic Data Types](#adt) * [Safe command composition](#safe-composition) * [Generalised Algebraic Data Types](#gadt) * [The algebra of types](#algebra)