+ - 0:00:00
Notes for current slide
Notes for next slide

Far more than you've ever wanted to know about ADTs

Nicolas Rinaudo • @NicolasRinaudo@functional.cafe

1 / 440

Far more than you've ever wanted to know about ADTs

Nicolas Rinaudo • @NicolasRinaudo@functional.cafe

2 / 440

Our proud hero

3 / 440

Valid programs

Facing south

4 / 440

Valid programs

Sending face north

face north
5 / 440

Valid programs

Facing north

face north
6 / 440

Valid programs

Sending face west

face west
7 / 440

Valid programs

Facing west

face west
8 / 440

Valid programs

Sending face south

face south
9 / 440

Valid programs

Facing south

face south
10 / 440

Valid programs

Sending face east

face east
11 / 440

Valid programs

Facing east

face east
12 / 440

Valid programs

Sending start

start
13 / 440

Valid programs

Started

start
14 / 440

Valid programs

Sending stop

stop
15 / 440

Valid programs

Stopped

stop
16 / 440

Invalid programs

Sending triple_backflip

triple_backflip
17 / 440

Invalid programs

Confused

triple_backflip
18 / 440

Invalid programs

Kaboom

triple_backflip
19 / 440

Invalid programs

Sending face -35

face -35
20 / 440

Invalid programs

Rejected

face -35
21 / 440

Invalid programs

Rejected

face -35
22 / 440

Representing Direction

23 / 440

Magic values

​object Direction:
24 / 440

Magic values

object Direction:
  val North: Int = ???
  val East:  Int = ???
  val South: Int = ???
  val West:  Int = ???
25 / 440

Magic values

object Direction:
  val North: Int = ???
  val East:  Int = ???
  val South: Int = ???
  val West:  Int = ???
26 / 440

Magic values

object Direction:
  val North: Int = 1
  val East:  Int = 2
  val South: Int = 3
  val West:  Int = 4
27 / 440

Magic values

def label(d: Int) = ???
28 / 440

Magic values

def label(d: Int) = ???
29 / 440

Magic values

def label(d: Int) = ???
30 / 440

Magic values

def label(d: Int) = d match
  case Direction.North ⇒ ???
  case Direction.East  ⇒ ???
  case Direction.South ⇒ ???
  case Direction.West  ⇒ ???
31 / 440

Magic values

def label(d: Int) = d match
  case Direction.North ⇒ ???
  case Direction.East  ⇒ ???
  case Direction.South ⇒ ???
  case Direction.West  ⇒ ???
32 / 440

Magic values

def label(d: Int) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
  case Direction.West  ⇒ "east"
33 / 440

Magic values

Sending face -35

label(-35)
34 / 440

Magic values

Kaboom

label(-35)
// 💥 scala.MatchError: -35
35 / 440

Type aliases

​type Direction = Int
object Direction:
  val North: Int = 1
  val East:  Int = 2
  val South: Int = 3
  val West:  Int = 4
36 / 440

Type aliases

type Direction = Int
object Direction:
  val North: Int = 1
  val East:  Int = 2
  val South: Int = 3
  val West:  Int = 4
37 / 440

Type aliases

type Direction = Int
object Direction:
  val North: Direction = 1
  val East:  Direction = 2
  val South: Direction = 3
  val West:  Direction = 4
38 / 440

Type aliases

def label(d: Int) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
  case Direction.West  ⇒ "west"
39 / 440

Type aliases

def label(d: Direction) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
  case Direction.West  ⇒ "west"
40 / 440

Type aliases

Sending face -35

label(-35)
41 / 440

Type aliases

Kaboom

label(-35)
// 💥 scala.MatchError: -35
42 / 440

Scala's Enumeration

​type Direction = Int
object Direction:
  val North: Direction = 1
  val East:  Direction = 2
  val South: Direction = 3
  val West:  Direction = 4
43 / 440

Scala's Enumeration

object Direction:
44 / 440

Scala's Enumeration

object Direction extends Enumeration:
45 / 440

Scala's Enumeration

object Direction extends Enumeration:
  val North, East, South, West = Value
46 / 440

Scala's Enumeration

def label(d: Direction) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
  case Direction.West  ⇒ "west"
47 / 440

Scala's Enumeration

def label(d: Direction.Value) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
  case Direction.West  ⇒ "west"
48 / 440

Scala's Enumeration

Sending face -35

label(-35)
49 / 440

Scala's Enumeration

Rejected

label(-35)
// ⛔ Found:    Int
//   Required: Direction.Value
50 / 440

Scala's Enumeration

def label(d: Direction.Value) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
  case Direction.West  ⇒ "west"
51 / 440

Scala's Enumeration

def label(d: Direction.Value) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
​//case Direction.West  ⇒ "west"
52 / 440

Scala's Enumeration

Sending face west

label(Direction.West)
53 / 440

Scala's Enumeration

Kaboom

label(Direction.West)
// 💥 scala.MatchError: West
54 / 440

Hand-written enumeration

​trait Direction
55 / 440

Hand-written enumeration

trait Direction
​object Direction:
56 / 440

Hand-written enumeration

trait Direction
object Direction:
  case object North extends Direction
57 / 440

Hand-written enumeration

trait Direction
object Direction:
  case object North extends Direction
  case object East  extends Direction
58 / 440

Hand-written enumeration

trait Direction
object Direction:
  case object North extends Direction
  case object East  extends Direction
  case object South extends Direction
59 / 440

Hand-written enumeration

trait Direction
object Direction:
  case object North extends Direction
  case object East  extends Direction
  case object South extends Direction
  case object West  extends Direction
60 / 440

Hand-written enumeration

def label(d: Direction.Value) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
//case Direction.West  ⇒ "west"
61 / 440

Hand-written enumeration

def label(d: Direction) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
//case Direction.West  ⇒ "west"
62 / 440

Hand-written enumeration

Sending face west

label(Direction.West)
63 / 440

Hand-written enumeration

Kaboom

label(Direction.West)
// 💥 scala.MatchError: West
64 / 440

Hand-written enumeration

​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
65 / 440

Hand-written enumeration

def label(d: Direction) = d match
  case Direction.North ⇒ "north"
  case Direction.East  ⇒ "east"
  case Direction.South ⇒ "south"
//case Direction.West  ⇒ "west"
66 / 440

Hand-written enumeration

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
67 / 440

Key takeaways

68 / 440

Key takeaways

Enumerations​:

69 / 440

Key takeaways

Enumerations​:

  • make nonsensical values impossible to represent.
70 / 440

Key takeaways

Enumerations​:

  • make nonsensical values impossible to represent.

  • guarantee that our code handles all necessary cases.

71 / 440

Key takeaways

Enumerations​:

  • make nonsensical values impossible to represent.

  • guarantee that our code handles all necessary cases.

  • provided you're not using scala.Enumeration though...

72 / 440

Representing Command

73 / 440

Case class

case class Command(
)
​
​
val cmd = Command(
)
​
​
74 / 440

Case class

case class Command(
  order: String
)
​
val cmd = Command(
  "face"
)
​
75 / 440

Case class

case class Command(
  order: String,
  dir  : Option[Direction]
)
val cmd = Command(
  "face",
  Some(Direction.North)
)
76 / 440

Case class

Triple backflip

Command(
  "triple backflip",
  Some(Direction.South)
)
77 / 440

Case class

Triple backflip

Command(
  "triple backflip",
  Some(Direction.South)
)
78 / 440

Case class

Kaboom

Command(
  "triple backflip",
  Some(Direction.South)
)
79 / 440

Order as enumeration

​sealed trait Order
80 / 440

Order as enumeration

sealed trait Order
​object Order:
81 / 440

Order as enumeration

sealed trait Order
object Order:
  case object Face  extends Order
82 / 440

Order as enumeration

sealed trait Order
object Order:
  case object Face  extends Order
  case object Start extends Order
83 / 440

Order as enumeration

sealed trait Order
object Order:
  case object Face  extends Order
  case object Start extends Order
  case object Stop  extends Order
84 / 440

Order as enumeration

case class Command(
  order: String,
  dir  : Option[Direction]
)
val cmd = Command(
  "face",
  Some(Direction.North)
)
85 / 440

Order as enumeration

case class Command(
  order: Order,
  dir  : Option[Direction]
)
val cmd = Command(
  Order.Face,
  Some(Direction.North)
)
86 / 440

Order as enumeration

Sending triple backflip

Command(
  "triple backflip",
  Some(Direction.South)
)
87 / 440

Order as enumeration

Rejected

Command(
  "triple backflip",
  Some(Direction.South)
)
// ⛔ Found:    String
//   Required: Order
88 / 440

Order as enumeration

Rejected

Command(
  "triple backflip",
  Some(Direction.South)
)
89 / 440

Order as enumeration

Sending start south

Command(
  Order.Start,
  Some(Direction.South)
)
90 / 440

Order as enumeration

Sending start south

Command(
  Order.Start,
  Some(Direction.South)
)
91 / 440

Order as enumeration

Kaboom

Command(
  Order.Start,
  Some(Direction.South)
)
92 / 440

Order as "enumeration"

sealed trait Order
object Order:
  case o​bject Face  extends Order
  case object Start extends Order
  case object Stop  extends Order
93 / 440

Order as "enumeration"

sealed trait Order
object Order:
  case c​lass  Face(dir: Direction) extends Order
  case object Start                extends Order
  case object Stop                 extends Order
94 / 440

Order as "enumeration"

sealed trait Order
object Order:
  case class  Face(dir: Direction) extends Order
  case object Start                extends Order
  case object Stop                 extends Order
95 / 440

Command as "enumeration"

sealed trait Command
object Command:
  case class  Face(dir: Direction) extends Command
  case object Start                extends Command
  case object Stop                 extends Command
96 / 440

Command as "enumeration"

Sending start south

Command(
  Order.Start,
  Some(Direction.South)
)
97 / 440

Command as "enumeration"

Rejected

​Command(
  Order.Start,
  Some(Direction.South)
)
// ⛔ object Command does not take parameters
98 / 440

Command as "enumeration"

Sending

Command.Start
99 / 440

Command as "enumeration"

Sending

Command.Start
100 / 440

Key takeaways

101 / 440

Key takeaways

  • Enumerations are everywhere.
102 / 440

Key takeaways

  • Enumerations are everywhere.

  • Enumerations are not enough.

103 / 440

Key takeaways

  • Enumerations are everywhere.

  • Enumerations are not enough.

  • Something "like an enumeration" might be, however.

104 / 440

Composing commands

105 / 440

Script

Waiting command

start
106 / 440

Script

Waiting command

face east
start
stop
107 / 440

Script

Sending script

face east
start
stop
108 / 440

Script

Starting

​face east
start
stop
109 / 440

Script

Continue advancing

face east
​start
stop
110 / 440

Script

Stopping

face east
start
​stop
111 / 440

Chaining commands

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
112 / 440

Chaining commands

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
113 / 440

Chaining commands

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
114 / 440

Chaining commands

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
  )
)
115 / 440

Chaining commands

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
  )
)
116 / 440

Chaining commands

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
  )
)
117 / 440

Chaining commands

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
  )
)
118 / 440

Chaining commands

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
  )
)
119 / 440

Chaining commands

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
  )
)
120 / 440

Chaining commands

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
  )
)
121 / 440

DSL

extension (cmd1: Command)
  def ~>(cmd2: Command): Command =
    Command.Chain(cmd1, cmd2)
val startStop: Command =
  Command.Start ~> Command.Stop
122 / 440

DSL

extension (cmd1: Command)
  def ~>(cmd2: Command): Command =
    Command.Chain(cmd1, cmd2)
val startStop: Command =
  Command.Start ~> Command.Stop
123 / 440

DSL

extension (cmd1: Command)
  def ~>(cmd2: Command): Command =
    Command.Chain(cmd1, cmd2)
val startStop: Command =
  Command.Start ~> Command.Stop
124 / 440

DSL

extension (cmd1: Command)
  def ~>(cmd2: Command): Command =
    Command.Chain(cmd1, cmd2)
val startStop: Command =
  Command.Start ~> Command.Stop
125 / 440

DSL

extension (cmd1: Command)
  def ~>(cmd2: Command): Command =
    Command.Chain(cmd1, cmd2)
val startStop: Command =
  Command.Start ~> Command.Stop
126 / 440

DSL

​val start                = Command.Start
127 / 440

DSL

val start                = Command.Start
​val stop                 = Command.Stop
128 / 440

DSL

val start                = Command.Start
val stop                 = Command.Stop
​def face(dir: Direction) = Command.Face(dir)
129 / 440

DSL

​val north = Direction.North
130 / 440

DSL

val north = Direction.North
​val east  = Direction.East
131 / 440

DSL

val north = Direction.North
val east  = Direction.East
​val south = Direction.South
132 / 440

DSL

val north = Direction.North
val east  = Direction.East
val south = Direction.South
​val west  = Direction.West
133 / 440

Compound commands

def move(d: Direction) =
  face(d) ~> start ~> stop
134 / 440

Compound commands

def move(d: Direction) =
  face(d) ~> start ~> stop
135 / 440

Compound commands

def move(d: Direction) =
  face(d) ~> start ~> stop
136 / 440

Compound commands

def move(d: Direction) =
  face(d) ~> start ~> stop
137 / 440

Compound commands

def move(d: Direction) =
  face(d) ~> start ~> stop
138 / 440

Compound commands

Sending script

move(east) ~> move(west)
139 / 440

Compound commands

Sending script

move(east) ~> move(west)
140 / 440

Compound commands

Sending script

​move(east) ~> move(west)
141 / 440

Compound commands

Sending script

​move(east) ~> move(west)
142 / 440

Compound commands

Sending script

​move(east) ~> move(west)
143 / 440

Compound commands

Sending script

move(east) ~> move(west)
144 / 440

Compound commands

Sending script

move(east) ~> move(west)
145 / 440

Compound commands

Sending script

move(east) ~> move(west)
146 / 440

Key takeaways

147 / 440

Key takeaways

We've completed our data structure by using:

148 / 440

Key takeaways

We've completed our data structure by using:

  • records (Chain, Face).
149 / 440

Key takeaways

We've completed our data structure by using:

  • records (Chain, Face).

  • enumerated types (Command, Direction).

150 / 440

Key takeaways

We've completed our data structure by using:

  • records (Chain, Face).

  • enumerated types (Command, Direction).

  • recursive types (Command is expressed in terms of itself).

151 / 440

Algebraic Data Types

152 / 440

Sum types

Command = Face
        | Start
        | Stop
        | Chain
153 / 440

Sum types

Command = Face
        | Start
        | Stop
        | Chain
154 / 440

Sum types

Command = Face
        | Start
        | Stop
        | Chain
155 / 440

Sum types

Command = Face
        | Start
        | Stop
        | Chain
156 / 440

Sum types

Command = Face
        | Start
        | Stop
        | Chain
157 / 440

Sum types

Command = Face
        | Start
        | Stop
        | Chain

A sum type is a discriminated union of values, and can be thought of as an OR on types.

158 / 440

Sum types

Command = Face
        | Start
        | Stop
        | Chain

A sum type is a discriminated union of values, and can be thought of as an OR on types.

159 / 440

Sum types

Command = Face
        | Start
        | Stop
        | Chain

A sum type is a discriminated union of values, and can be thought of as an OR on types.

160 / 440

Union types

union int_or_string {
  int   as_int;
  char* as_string;
};
161 / 440

Union types

union int_or_string {
  int   as_int;
  char* as_string;
};
162 / 440

Union types

union int_or_string {
  int   as_int;
  char* as_string;
};
163 / 440

Union types

union int_or_string {
  int   as_int;
  char* as_string;
};
164 / 440

Union types

#include<stdio.h>
void print_union(union int_or_string e) {
    ???
}
165 / 440

Union types

#include<stdio.h>
void print_union(union int_or_string e) {
    ???
}
166 / 440

Manually discriminated union types

enum typetag {
    int_tag,
    string_tag
};
167 / 440

Manually discriminated union types

enum typetag {
    int_tag,
    string_tag
};
168 / 440

Manually discriminated union types

enum typetag {
    int_tag,
    string_tag
};
169 / 440

Manually discriminated union types

enum typetag {
    int_tag,
    string_tag
};
170 / 440

Manually discriminated union types

union int_or_string {
    int   as_int;
    char* as_string;
};
171 / 440

Manually discriminated union types

union int_or_string {
    enum typetag discriminator;
    int   as_int;
    char* as_string;
};
172 / 440

Manually discriminated union types

​union int_or_string {
    enum typetag discriminator;
    int   as_int;
    char* as_string;
};
173 / 440

Manually discriminated union types

​struct int_or_string {
    enum typetag discriminator;
    int   as_int;
    char* as_string;
};
174 / 440

Manually discriminated union types

struct int_or_string {
    enum typetag discriminator;
    int   as_int;
    char* as_string;
};
175 / 440

Manually discriminated union types

struct int_or_string {
    enum typetag discriminator;
    union {
        int   as_int;
        char* as_string;
    } value;
};
176 / 440

Manually discriminated union types

struct int_or_string {
    enum typetag discriminator;
    union {
        int   as_int;
        char* as_string;
    } value;
};
177 / 440

Manually discriminated union types

struct int_or_string {
    enum typetag discriminator;
    union {
        int   as_int;
        char* as_string;
    } value;
};
178 / 440

Manually discriminated union types

#include<stdio.h>
void print_union(union int_or_string e) {
    ???
}
179 / 440

Manually discriminated union types

#include<stdio.h>
void print_union(struct int_or_string e) {
    ???
}
180 / 440

Manually discriminated union types

#include<stdio.h>
void print_union(struct int_or_string e) {
    ???
}
181 / 440

Manually discriminated union types

#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);
    }
}
182 / 440

Manually discriminated union types

#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);
    }
}
183 / 440

Manually discriminated union types

#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);
    }
}
184 / 440

Manually discriminated union types

#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);
    }
}
185 / 440

Sum types

Command = Face
        | Start
        | Stop
        | Chain

A sum type is a discriminated union of values, and can be thought of as an OR on types.

186 / 440

Sum types

An ADT is a sum type [...]

187 / 440

Product types

Command = Face
        | Start
        | Stop
        | Chain
188 / 440

Product types

Command = Face
        | Start
        | Stop
        | Chain
189 / 440

Product types

Command = Face
        | Start
        | Stop
        | Command & Command
190 / 440

Product types

Command = Face
        | Start
        | Stop
        | Command & Command
191 / 440

Product types

Command = Face
        | Start
        | Stop
        | Command & Command
192 / 440

Product types

Command = Face
        | Start
        | Stop
        | Command & Command

A product type is an aggregation of values, and can be thought of as an AND on types.

193 / 440

Product types

Command = Face
        | Start
        | Stop
        | Command & Command

A product type is an aggregation of values, and can be thought of as an AND on types.

194 / 440

Product types

An ADT is a sum type of product types [...]

195 / 440

Algebraic Data Types

Command = Face
        | Start
        | Stop
        | Command & Command
196 / 440

Algebraic Data Types

​Command = Face
        | Start
        | Stop
        | Command & Command
197 / 440

Algebraic Data Types

Command = Face
        | Start
        | Stop
        | Command & Command
198 / 440

Algebraic Data Types

An ADT is a potentially recursive sum type of product types.

199 / 440

Dedicated syntax

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
200 / 440

Dedicated syntax

​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
201 / 440

Dedicated syntax

​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
202 / 440

Dedicated syntax

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
203 / 440

Dedicated syntax

enum Command:
  case Face(dir: Direction) extends Command
  case Start                extends Command
  case Stop                 extends Command
  case Chain(
    cmd1: Command,
    cmd2: Command
  ) extends Command
204 / 440

Dedicated syntax

enum Command:
  case Face(dir: Direction)
  case Start
  case Stop
  case Chain(
    cmd1: Command,
    cmd2: Command
  )
205 / 440

Key takeaways

206 / 440

Key takeaways

Algebraic Data Types are:

207 / 440

Key takeaways

Algebraic Data Types are:

  • sum types.
208 / 440

Key takeaways

Algebraic Data Types are:

  • sum types.

  • product types.

209 / 440

Key takeaways

Algebraic Data Types are:

  • sum types.

  • product types.

  • potentially recursive.

210 / 440

Safe command composition

211 / 440

Illegal state transition

Start 

 start ~> start
212 / 440

Illegal state transition

Start 

 start ~> start
213 / 440

Illegal state transition

Start 

 start ~> start
214 / 440

Illegal state transition

Start 

 start ~> start
215 / 440

Illegal state transition

Start

 stop ~> stop
216 / 440

Illegal state transition

Start

 stop ~> stop
217 / 440

Illegal state transition

Start 

 stop ~> stop
218 / 440

Illegal state transition

Start

 stop ~> stop
219 / 440

Illegal state transition

Start

 start ~> face(north)
220 / 440

Illegal state transition

Start

 start ~> face(north)
221 / 440

Illegal state transition

Start

 start ~> face(north)
222 / 440

Illegal state transition

Start Big badaboom

 start ~> face(north)
223 / 440

Tracking state

final abstract class Idle
final abstract class Moving
224 / 440

Tracking state

final abstract class Idle
final abstract class Moving
225 / 440

Tracking state

final abstract class Idle
final abstract class Moving
226 / 440

Tracking state

enum Command[Before, After]:
  case Face(dir: Direction)
  case Start
  case Stop
  case Chain(
    cmd1: Command,
    cmd2: Command
  )
227 / 440

Tracking state

enum Command[Before, After]:
  case Face(dir: Direction) extends Command[Idle, Idle]
  case Start
  case Stop
  case Chain(
    cmd1: Command,
    cmd2: Command
  )
228 / 440

Tracking state

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
  )
229 / 440

Tracking state

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
  )
230 / 440

Tracking state

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
  )
231 / 440

Tracking state

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
  )
232 / 440

Tracking state

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]
  )
233 / 440

Tracking state

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]
  )
234 / 440

Tracking state

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]
235 / 440

Tracking state

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]
236 / 440

DSL

extension (cmd1: Command[A, B])
  def ~>(cmd2: Command): Command =
    Command.Chain(cmd1, cmd2)
237 / 440

DSL

extension [A, B](cmd1: Command[A, B])
  def ~>(cmd2: Command): Command =
    Command.Chain(cmd1, cmd2)
238 / 440

DSL

extension [A, B](cmd1: Command[A, B])
  def ~>(cmd2: Command[B, C]): Command =
    Command.Chain(cmd1, cmd2)
239 / 440

DSL

extension [A, B](cmd1: Command[A, B])
  def ~>[C](cmd2: Command[B, C]): Command =
    Command.Chain(cmd1, cmd2)
240 / 440

DSL

extension [A, B](cmd1: Command[A, B])
  def ~>[C](cmd2: Command[B, C]): Command[A, C] =
    Command.Chain(cmd1, cmd2)
241 / 440

Illegal state transition

Start

start ~> start
242 / 440

Illegal state transition

Start 

start ~> start
// ⛔ Found:    Command[Idle, Moving]
//   Required: Command[Moving, C]
243 / 440

Illegal state transition

Start

stop ~> stop
244 / 440

Illegal state transition

Start

stop ~> stop
// ⛔ Found:    Command[Moving, Idle]
//   Required: Command[Idle, C]
245 / 440

Illegal state transition

Start

start ~> face(north)
246 / 440

Illegal state transition

Start

start ~> face(north)
// ⛔ Found:    Command[Idle, Idle]
//   Required: Command[Moving, C]
247 / 440

Safe state transition

Start

face(east) ~> start ~> stop
248 / 440

Safe state transition

Start

face(east) ~> start ~> stop
249 / 440

Safe state transition

Start

​face(east) ~> start ~> stop
250 / 440

Safe state transition

Start

face(east) ~> start ~> stop
251 / 440

Safe state transition

Start

face(east) ~> start ~> stop
252 / 440

Smarter exhaustivity checks

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
  case _: Command.Chain[_, _, _] => "chain"
253 / 440

Smarter exhaustivity checks

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
  case _: Command.Chain[_, _, _] => "chain"
254 / 440

Smarter exhaustivity checks

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
  case _: Command.Chain[_, _, _] => "chain"
255 / 440

Smarter exhaustivity checks

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
  case _: Command.Chain[_, _, _] => "chain"
256 / 440

Smarter exhaustivity checks

Start

movingLabel(Command.Start)
257 / 440

Smarter exhaustivity checks

Start

movingLabel(Command.Start)
// ⛔ Found:    Command[Idle, Moving]
//   Required: Command[Moving, ?]
258 / 440

Smarter exhaustivity checks

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
  case _: Command.Chain[_, _, _] => "chain"
259 / 440

Smarter exhaustivity checks

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
​//case _: Command.Chain[_, _, _] => "chain"
260 / 440

Smarter exhaustivity checks

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(_, _)
261 / 440

Smarter exhaustivity checks

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
​//case _: Command.Chain[_, _, _] => "chain"
262 / 440

Smarter exhaustivity checks

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
  case _: Command.Chain[_, _, _] => "chain"
  case Command.Start             => "start"
263 / 440

Smarter exhaustivity checks

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, ?]
264 / 440

Key takeaways

265 / 440

Key takeaways

We used type constraints on our sum type's members to:

266 / 440

Key takeaways

We used type constraints on our sum type's members to:

  • make illegal state transitions impossible to represent.
267 / 440

Key takeaways

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.

268 / 440

Key takeaways

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.

269 / 440

Generalised Algebraic Data Types

270 / 440

Sum type

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]
271 / 440

Sum type

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]
272 / 440

Sum type

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]
273 / 440

Sum type

A GADT is a sum type [...]

274 / 440

Witness type

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]
275 / 440

Witness type

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]
276 / 440

Witness type

A witness type describes properties of a sum type's variants at the type level.

277 / 440

GADT

A GADT is a sum type with one or more witness types [...]

278 / 440

Type equality

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
//case _: Command.Chain[_, _, _] => "chain"
  case Command.Start             => "start"
279 / 440

Type equality

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
​//case _: Command.Chain[_, _, _] => "chain"
  case Command.Start             => "start"
280 / 440

Type equality

def movingLabel(cmd: Command[Moving, _]) = cmd match
  case Command.Stop              => "stop"
//case _: Command.Chain[_, _, _] => "chain"
  case Command.Start             => "start"
281 / 440

Type equality

Type equality is information available to the compiler about each witness type, allowing it to refine pattern matches.

282 / 440

GADT

A GADT is a sum type with one or more witness types, each equipped with a type equality.

283 / 440

Key takeaways

284 / 440

Key takeaways

  • A GADT is a sum type with one or more witness types, each equipped with a type equality.
285 / 440

Key takeaways

  • A GADT is a sum type with one or more witness types, each equipped with a type equality.
286 / 440

Key takeaways

  • 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.

287 / 440

The algebra of types

288 / 440

Cardinality

The cardinality of type A is written ∣A∣\vert A \vert and is the number of values of type A.

289 / 440

Cardinality

Nothing

290 / 440

Cardinality

Nothing

291 / 440

Cardinality

Nothing

∣Nothing∣=0\vert Nothing \vert = 0

292 / 440

Cardinality

Unit

293 / 440

Cardinality

Unit

294 / 440

Cardinality

Unit

∣Unit∣=1\vert Unit \vert = 1

295 / 440

Cardinality

Boolean

296 / 440

Cardinality

Boolean

297 / 440

Cardinality

Boolean

298 / 440

Cardinality

Boolean

∣Boolean∣=2\vert Boolean \vert = 2

299 / 440

Sum types

enum +[+A, +B]:
  case Left[A](value: A) extends +[A, Nothing]
  case Right[B](value: B) extends +[Nothing, B]
300 / 440

Sum types

enum +[+A, +B]:
  case Left[A](value: A) extends +[A, Nothing]
  case Right[B](value: B) extends +[Nothing, B]
301 / 440

Sum types

enum +[+A, +B]:
  case Left[A](value: A) extends +[A, Nothing]
  case Right[B](value: B) extends +[Nothing, B]
302 / 440

Sum types

enum +[+A, +B]:
  case Left[A](value: A) extends +[A, Nothing]
  case Right[B](value: B) extends +[Nothing, B]
303 / 440

Sum types

enum +[+A, +B]:
  case Left[A](value: A) extends +[A, Nothing]
  case Right[B](value: B) extends +[Nothing, B]
304 / 440

Sum types

enum +[+A, +B]:
  case Left[A](value: A) extends +[A, Nothing]
  case Right[B](value: B) extends +[Nothing, B]
305 / 440

Sum types

enum +[+A, +B]:
  case Left[A](value: A) extends +[A, Nothing]
  case Right[B](value: B) extends +[Nothing, B]
306 / 440

Sum types

enum +[+A, +B]:
  case Left[A](value: A) extends (A + Nothing)
  case Right[B](value: B) extends (Nothing + B)
307 / 440

Sum types

+

308 / 440

Sum types

+

309 / 440

Sum types

+

310 / 440

Sum types

+

∣A+B∣=∣A∣…\vert A + B \vert = \vert A \vert \ldots

311 / 440

Sum types

+

∣A+B∣=∣A∣+∣B∣\vert A + B \vert = \vert A \vert + \vert B \vert

312 / 440

Type isomorphisms

We'll say that types A and B are isomorphic if they have the same cardinality, and write A ~= B.

313 / 440

Type isomorphisms

We'll say that types A and B are isomorphic if they have the same cardinality, and write A ~= B.

314 / 440

Sum types

Algebra

1 + 1 = 2
315 / 440

Sum types

Algebra

1 + 1 = 2

Types

Unit + Unit ~= Boolean
316 / 440

Sum types

Algebra

​1 + 1 = 2

Types

​Unit + Unit ~= Boolean
317 / 440

Sum types

Algebra

1 + 1 = 2

Types

Unit + Unit ~= Boolean
318 / 440

Sum types

Algebra

1 + 1 = 2

Types

Unit + Unit ~= Boolean
319 / 440

Sum types

Algebra

1 + 1 = 2

Types

Unit + Unit ~= Boolean
320 / 440

Sum types

Unit + Unit = Boolean

321 / 440

Sum types

Unit + Unit = Boolean

322 / 440

Sum types

Unit + Unit = Boolean

323 / 440

Sum types

Unit + Unit = Boolean

324 / 440

Sum types

Unit + Unit = Boolean

325 / 440

Sum types

Unit + Unit = Boolean

326 / 440

Sum types associativity

Algebra

a + (b + c) = (a + b) + c
327 / 440

Sum types associativity

Algebra

a + (b + c) = (a + b) + c

Types

A + (B + C) ~= (A + B) + C
328 / 440

Sum types associativity

A + B + C

329 / 440

Sum types associativity

A + B + C

330 / 440

Sum types associativity

A + B + C

331 / 440

Sum types associativity

A + B + C

332 / 440

Sum types associativity

A + B + C

333 / 440

Sum types associativity

A + B + C

334 / 440

Sum types associativity

A + B + C

335 / 440

Sum types associativity

A + B + C

336 / 440

Sum types commutativity

Algebra

a + b = b + a
337 / 440

Sum types commutativity

Algebra

a + b = b + a

Types

A + B ~= B + A
338 / 440

Sum types commutativity

A + B

339 / 440

Sum types commutativity

A + B

340 / 440

Sum types commutativity

A + B

341 / 440

Sum types commutativity

A + B

342 / 440

Sum types commutativity

A + B

343 / 440

Sum types commutativity

A + B

344 / 440

Sum types neutral element

Algebra

a + 0 = a
345 / 440

Sum types neutral element

Algebra

a + 0 = a

Types

A + Nothing ~= A
346 / 440

Sum types neutral element

A + B

347 / 440

Sum types neutral element

A + B

348 / 440

Sum types neutral element

A + B

349 / 440

Sum types neutral element

A + B

350 / 440

Sum types neutral element

A + B

351 / 440

Product types

case class ✕[A, B](first: A, second: B)
352 / 440

Product types

case class ✕[A, B](first: A, second: B)
353 / 440

Product types

case class ✕[A, B](first: A, second: B)
354 / 440

Product types

case class ✕[A, B](first: A, second: B)
355 / 440

Product types

extension [A](a: A)
  def ✕[B](b: B): ✕[A, B] = new ✕(a, b)
356 / 440

Product types

extension [A](a: A)
  def ✕[B](b: B): ✕[A, B] = new ✕(a, b)
357 / 440

Product types

extension [A](a: A)
  def ✕[B](b: B): ✕[A, B] = new ✕(a, b)
358 / 440

Product types

extension [A](a: A)
  def ✕[B](b: B): ✕[A, B] = new ✕(a, b)
359 / 440

Product types

extension [A](a: A)
  def ✕[B](b: B): ✕[A, B] = new ✕(a, b)
360 / 440

Product types

extension [A](a: A)
  def ✕[B](b: B): ✕[A, B] = new ✕(a, b)
361 / 440

Product types

extension [A](a: A)
  def ✕[B](b: B): A ✕ B = new ✕(a, b)
362 / 440

Product types

✕

363 / 440

Product types

✕

364 / 440

Product types

✕

365 / 440

Product types

✕

366 / 440

Product types

✕

∣A×B∣=∣A∣…\vert A \times B \vert = \vert A \vert \ldots

367 / 440

Product types

✕

∣A×B∣=∣A∣×∣B∣\vert A \times B \vert = \vert A \vert \times \vert B \vert

368 / 440

Product types

Algebra

a + a = 2 * a
369 / 440

Product types

Algebra

a + a = 2 * a

Types

A + A ~= Boolean ✕ A
370 / 440

Product types

Algebra

a + a = 2 * a

Types

A + A ~= Boolean ✕ A
371 / 440

Product types

A + A

372 / 440

Product types

A + A

373 / 440

Product types

A + A

374 / 440

Product types

A + A

375 / 440

Product types

A + A

376 / 440

Product types

A + A

377 / 440

Product types associativity

Algebra

(a * b) * c = a * (b * c)
378 / 440

Product types associativity

Algebra

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

Types

(A ✕ B) ✕ C ~= A ✕ (B ✕ C)
379 / 440

Product types associativity

A ✕ B ✕ C

380 / 440

Product types associativity

A ✕ B ✕ C

381 / 440

Product types associativity

A ✕ B ✕ C

382 / 440

Product types associativity

A ✕ B ✕ C

383 / 440

Product types commutativity

Algebra

a * b = b * a
384 / 440

Product types commutativity

Algebra

a * b = b * a

Types

A ✕ B ~= B ✕ A
385 / 440

Product types commutativity

A ✕ B

386 / 440

Product types commutativity

A ✕ B

387 / 440

Product types commutativity

A ✕ B

388 / 440

Product types commutativity

A ✕ B

389 / 440

Product types neutral element

Algebra

a * 1 = a
390 / 440

Product types neutral element

Algebra

a * 1 = a

Types

A ✕ Unit ~= A
391 / 440

Product types neutral element

A ✕ Unit

392 / 440

Product types neutral element

A ✕ Unit

393 / 440

Product types neutral element

A ✕ Unit

394 / 440

Product types neutral element

A ✕ Unit

395 / 440

Recursive types

enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])
396 / 440

Recursive types

enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])
397 / 440

Recursive types

enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])
398 / 440

Recursive types

enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])
399 / 440

Recursive types

enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])
400 / 440

Recursive types

enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])
401 / 440

Recursive types

enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])
402 / 440

List of fixed size

∣List0[A]∣ \vert List_0[A] \vert

403 / 440

List of fixed size

∣List0[A]∣=∣Nil∣ \vert List_0[A] \vert = \vert Nil \vert

404 / 440

List of fixed size

∣List0[A]∣=1 \vert List_0[A] \vert = 1

405 / 440

List of fixed size

∣List1[A]∣ \vert List_1[A] \vert

406 / 440

List of fixed size

∣List1[A]∣=∣A×List0[A]∣ \vert List_1[A] \vert = \vert A \times List_0[A] \vert

407 / 440

List of fixed size

∣List1[A]∣=∣A∣×∣List0[A]∣ \vert List_1[A] \vert = \vert A \vert \times \vert List_0[A] \vert

408 / 440

List of fixed size

∣List1[A]∣=∣A∣×1 \vert List_1[A] \vert = \vert A \vert \times 1

409 / 440

List of fixed size

∣List1[A]∣=∣A∣ \vert List_1[A] \vert = \vert A \vert

410 / 440

List of fixed size

∣List2[A]∣ \vert List_2[A] \vert

411 / 440

List of fixed size

∣List2[A]∣=∣A×List1[A]∣ \vert List_2[A] \vert = \vert A \times List_1[A] \vert

412 / 440

List of fixed size

∣List2[A]∣=∣A∣×∣List1[A]∣ \vert List_2[A] \vert = \vert A \vert \times \vert List_1[A] \vert

413 / 440

List of fixed size

∣List2[A]∣=∣A∣×∣A∣ \vert List_2[A] \vert = \vert A \vert \times \vert A \vert

414 / 440

List of fixed size

∣List2[A]∣=∣A∣2 \vert List_2[A] \vert = \vert A \vert^2

415 / 440

List of fixed size

∣Listn[A]∣=∣A∣n \vert List_n[A] \vert = \vert A \vert^n

416 / 440

List of maximum size

∣Listn[A]∣ \vert List^n[A] \vert

417 / 440

List of maximum size

∣Listn[A]∣=∣∑i=0nListi[A]∣i\vert List^n[A] \vert = \vert \displaystyle\sum_{i = 0}^n List_i[A] \vert^i

418 / 440

List of maximum size

∣Listn[A]∣=∑i=0n∣Listi[A]∣\vert List^n[A] \vert = \displaystyle\sum_{i = 0}^n \vert List_i[A] \vert

419 / 440

List of maximum size

∣Listn[A]∣=∑i=0n∣A∣i\vert List^n[A] \vert = \displaystyle\sum_{i = 0}^n \vert A \vert^i

420 / 440

List of maximum size

∣Listn[A]∣=∣A∣n+1−1∣A∣−1\vert List^n[A] \vert = \frac{\vert A \vert^{n + 1} - 1}{\vert A \vert - 1}

421 / 440

List of maximum size

∣List2[Boolean]∣=∣Boolean∣2+1−1∣Boolean∣−1\vert List^2[Boolean] \vert = \frac{\vert Boolean \vert^{2 + 1} - 1}{\vert Boolean \vert - 1}

422 / 440

List of maximum size

∣List2[Boolean]∣=22+1−12−1\vert List^2[Boolean] \vert = \frac{2^{2 + 1} - 1}{2 - 1}

423 / 440

List of maximum size

∣List2[Boolean]∣=7\vert List^2[Boolean] \vert = 7

424 / 440

List of maximum size

List

425 / 440

List of maximum size

List

426 / 440

List of maximum size

List

427 / 440

List of maximum size

List

428 / 440

List of maximum size

List

429 / 440

Key takeaways

430 / 440

Key takeaways

  • ADTs have a deep connection to the algebra you know.
431 / 440

Key takeaways

  • ADTs have a deep connection to the algebra you know.

  • you can use this connection to prove fun facts about types.

432 / 440

Key takeaways

  • 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.

433 / 440

In closing

434 / 440

If you only remember 1 slide...

435 / 440

If you only remember 1 slide...

  • ADTs make data structures simpler and safer.
436 / 440

If you only remember 1 slide...

  • ADTs make data structures simpler and safer.

  • So do GADTs, only more so.

437 / 440

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.

438 / 440

Nicolas Rinaudo • @NicolasRinaudo@functional.cafe

439 / 440

Table of contents

440 / 440

Far more than you've ever wanted to know about ADTs

Nicolas Rinaudo • @NicolasRinaudo@functional.cafe

2 / 440
Paused

Help

Keyboard shortcuts

↑, ←, Pg Up, k Go to previous slide
↓, →, Pg Dn, Space, j Go to next slide
Home Go to first slide
End Go to last slide
Number + Return Go to specific slide
b / m / f Toggle blackout / mirrored / fullscreen mode
c Clone slideshow
p Toggle presenter mode
t Restart the presentation timer
?, h Toggle this help
Esc Back to slideshow