Skip to content

Latest commit

 

History

History
439 lines (306 loc) · 5.62 KB

talk-algebraic-data-types.md

File metadata and controls

439 lines (306 loc) · 5.62 KB
author title theme transition slideNumber
Malte Neuss
Algebraic Data Types (ADT)
sky
none
true

Algebra

Numbers:

2 + 2 + 2 =  3 * 2

. . .

Types:

class User 
  verified: Bool
  email:    String

::: notes Algebra = Lehre von Symbol-Konstellation und Manipulation :::

Content

::: incremental

  • Product Type
  • Sum Type
  • Examples

:::

. . .

Make illegal state unrepresentable

Basic Types

type Void:                      // 0
type Unit: unit                 // 1
type Bool: true, false          // 2
...
type String: "", "a", "b" ...   // infty

Product Type

type ProductType = Type x Type

. . .

type User = Bool x String

. . .

class User 
  verified: Bool
  email:    String

Product Type

:::::::::::::: {.columns} ::: {.column width="50%"}

Type:

type User = Bool x String

Values:

User(true,  "no@reply.com")
User(false, "no@reply.com")
User(true,  "ok@reply.com")
User(false, "ok@reply.com")
...

::: ::: {.column width="50%"}

{ width=90% }

By Quartl - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=22436861

::: ::::::::::::::

Algebra

Bool x Bool: (true,true) (false,false) (true,false) (false,true)
   2 x 2   =  4

. . .

Bool x Unit: (true,unit) (false,unit)    ~ Boolean
   2 x 1   =  2                              

. . .

Bool x Void: (true,???)                  ~ Void
   2 x 0   =  0

Sum Type

type SumType = Type + Type

. . .

type ID = Int + String

. . .

type ID = Int | String                           Typescript

. . .

     ID = Union[int, str]                        Python

. . .

sealed trait ID                                  Scala

case class IntID(Int)       extends ID
case class StringID(String) extends ID

Sum Type

:::::::::::::: {.columns} ::: {.column width="50%"}

Type:

type ID = Int | String

Values:

myID: ID = 1myID: ID = "123e4567-e89b..."  ✓
...

::: ::: {.column width="50%"}

{ width=40% }

By Stephan Kulla (User:Stephan Kulla) - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=14978640

::: ::::::::::::::

Algebra

Bool | Unit: true, false, unit
   2 + 1   =  3 

. . .

Bool | Void: true, false          ~ Bool
   2 + 0   =  2                     2

. . .

Bool | Int:  true, false, 1, 2, 3, ...
   2 + 2^64  

Unit Type

type BoolOpt     = Bool | Unit 

type Optional[T] =   T  | Unit 

. . .

type Optional[T] =    T | undefined              Typescript

. . .

     Optional[T] = Union[T, NoneType]            Python

. . .

sealed trait Option[A]                           Scala

case class  Some[A] extends Option[A]
case object None    extends Option[A]

Examples

Modelling Data

Make illegal state unrepresentable

No ADT: Error codes

class UserResult:
  error_code: int             # 0 means ok
  user:       User            # contains dummy data on error

def fetchUser() -> UserResult:
  # network call

. . .

myUser = fetchUser()

if myUser.error_code == 0:
  # do sth.
  # what if myUser.user still has dummy data?
else
  # do fallback

No ADT: Error codes

class UserResult:
  error_code: int             # 0 means ok
  user:       User            # contains dummy data on error

. . .

Representable valid values:

UserResult(0, User("John"))
UserResult(0, User("Jane"))
UserResult(1, User("dummy"))
...

. . .

Representable invalid values:

UserResult(1, User("John"))
UserResult(0, User("dummy"))

No ADT: Exceptions

def fetchUser() -> User:
    # raise Exception on error

. . .

myUser = fetchUser()
# do sth.

. . .

try:
  myUser = fetchUser()
  # do sth.
except ...

ADT: Optional

type Optional[T] = NoneType | T

def fetchUser() -> Optional[User]:
    # return None on error

. . .

myUser = fetchUser()

if   isinstance(myUser, User):
  # do sth.
elif isinstance(myUser, NoneType):
  # do fallback

ADT: Either

type Either[E,T] = E | T

def fetchUser() -> Either[Error, User]:
    # return Error value on error

. . .

myUser = fetchUser()

if   isinstance(myUser, User):
  # do sth.
elif isinstance(myUser, Error):
  # analyze reason

ADT: Custom

type User = Anonymous | LoggedIn

def fetchUser() -> User:

. . .

myUser = fetchUser()

if   isinstance(myUser, Anonymous):
  # do anonymous stuff.
elif isinstance(myUser, LoggedIn):
  # do logged-in stuff.

ADT: Custom extended

type User = Anonymous | LoggedIn | Admin
                                 # !new!
def fetchUser() -> User:

. . .

myUser = fetchUser()

if   isinstance(myUser, Anonymous):
  # do anonymous stuff.
elif isinstance(myUser, LoggedIn):
  # do logged-in stuff.
!!! Compiler error: forgot Admin case !!!

Further Topics

:::::::::::::: {.columns} ::: {.column width="50%"}

  • Scala
  • Haskell
  • Rust
  • Dependent Types
  • Linear Types

::: ::: {.column width="50%"}

Category Theory

{ width=50% }

  • Functor (map)
  • Monad (flatMap)
  • ...

::: ::::::::::::::

::: notes Image is public domain :::

Thanks