Data

Algebraic Data Types

Data Structures

• A mutable list

​

​

​

​

• Not entirely complete though. How do I specify the end of a list? Or an empty list? ref only lets us create real data. Need something like None in Python, to communicate an empty reference, or some better way to specify a distinguished end. We’ll revisit in Data Abstraction.

// F#�type MyList = {value : int; ref : MyList};

Algebraic Data Types

• Move from beyond primitive/atomic data (e.g., bool, int, etc), richer structures likes pairs, tuples, enums, lists, trees, etc.
• We’ve already seen records, which are related (i.e., named tuples) but algebraic data structures

​

// F#�type option_int = None | Some of int

A piece of data that is either nothing, or an integer.

Divided by zero? Return None. Else return integer

// F#�type int_list = Nil | Cons of int * int_list

A list of integers: either the empty list (Nil) or �an integer and the rest of the list

Case or Matching Statements

// F#�type option_int = None | Some of int

let f (x : option_int) =

match x with

| None -> printfn "Nope"

| Some v -> printfn "%i" v

in

f (Some 3); f(None)

Prints “3” and then “Nope”

Case or Matching Statements

// F#�type option_int = None | Some of int

let rec print_list l =

match l with

| Nil -> printfn "End"

| Cons(head, rest) ->

printfn "%i," head; � print_list rest

in� let l = Cons(1, Cons(2, Cons(3, Nil))) in

print_list l

Prints �“1,2,3,End”

Example

// F#�type t = L of int | N of int * t * t

Example

​

​

​

​

• A tree

// F#�type t = L of int | N of int * t * t

// F#�type Tree = Leaf of int | Node of int * Tree * Tree

Example

​

​

​

�Also like Enums

// F#�type Color = Red | Green | Blue

Algebraic Data Types

• It’s the essence of data in programming languages.
• When start to combine them with names (e.g., records), subtyping, etc, you start to recover many of the ways we thinking about organize data (e.g., objects).

​

• Reducible to the composition of a simple set of primitives
• Product types
• Sums types

​

Products

​

​

​

• A pair of values constructed using parenthesis
• Projections (left exp.L and right, exp.R) that enable us to access the left and right values of the product, respectively
• Can represent tuples, n-ary products
• (1, (2, 3)) (what we’ll do here)
• Or could invent new notation and syntax and semantics (e.g., (1, 2, 3).3) where projections are given by an integer.

let x = (1, 2) in� print x.L ;

print x.R

(1, 2).L = 1

(1, 2).R = 1

Semantics

Types

Sums

​

• Values are constructed by injections
• Case enables us destruct a value to figure out which kind of value it is

let None = inl () in�let Some(x) = inr x in …

let f (x) =

case x {

| L(v) -> print "Nope"

| R(v) -> print "%i" v }

in

f (Some 3); f(None)

Sums

// F#�type option_int = None | Some of int

let f (x : option_int) =

match x with

| None -> printfn "Nope"

| Some v -> printfn "%i" v

in

f (Some 3); f(None)

Sums

// F#�type option_int = None | Some of int

let f (x : option_int) =

match x with

| None -> printfn "Nope"

| Some v -> printfn "%i" v

in

f (Some 3); f(None)

let None = inl () in�let Some(x) = inr x in …

let f (x) =

case x {

| L(v) -> print "Nope"

| R(v) -> print "%i" v }

in

f (Some 3); f(None)

Semantics

Types

More than Binary

// F#�type color = Red | Green | Blue

More than Binary

// F#�type color = Red | Green | Blue

let Red = inl () in�let Green = inr (inl ()) in

let Blue = inr (inr ()) in …

A little more…

let Red = inl () in�let Green = inr (inl ()) in

let Blue = inr (inr ()) in …

// F#�type color = Red | Green | Blue

// F#�type position = Left | Center | Right

let Left = inl () in�let Center = inr (inl ()) in

let Right = inr (inr ()) in …

A little more…

let Red = inl () in�let Green = inr (inl ()) in

let Blue = inr (inr ()) in …

// F#�type color = Red | Green | Blue

// F#�type position = Left | Center | Right

let Left = inl () in�let Center = inr (inl ()) in

let Right = inr (inr ()) in …

Structural typing mean these are interchangeable

Variants (unique labels)

let Red = <color.Red = ()> in�let Green = <color.Green = ()> in

let Blue = < color.Blue – ()> in

// F#�type color = Red | Green | Blue

// F#�type position = Left | Center | Right

let Left = <position.Left = ()> in�let Center = <position.Center = ()> in

let Right = <position.Right = ()> in

Some Final Details

let Red = <color.Red = ()> in�let Green = <color.Green = ()> in

let Blue = < color.Blue – ()> in

let f (x) =

case x {

| <color.Red = v> -> print ”Red”

| <color.Green = v> -> print ”Green”

| <color.Blue = v> -> print ”Blue”�in

f (Some 3); f(None)

// F#�type color = Red | Green | Blue

Handle tagging in case statement

Some Final Details

let Red = <color.Red = ()> in�let Green = <color.Green = ()> in

let Blue = < color.Blue – ()> in

let f (x) =

case x {

| <color.Red = v> -> print ”Red”

| <color.Green = v> -> print ”Green”

| <color.Blue = v> -> print ”Blue”�in

f (Some 3); f(None)

// F#�type color = Red | Green | Blue

Also can perform exhaustiveness

checking

Recursive Types

• We aren’t quite there yet. Types need to refer to themselves.

​

​

​

• In principle, it is not too complicated to extend the type system. But, there are some subtleties with typechecking/inference. See notes

​

​

​

​

​

​

// F#�type int_list = Nil | Cons of int * int_list

Why Algebraic?

• How many values there of type bool?
• 2, True and False
• |bool| = 2
• What about bool * bool?
• 4, (True, True), (True, False), (False, True), (False, False)
• |bool * bool| = |bool| * |bool| = 4
• Looks quite a bit like multiplication!
• What about unit + unit?
• 2, inl () and inr ().
• |unit| = 1
• |unit + unit| = 2

Why Algebraic?

• What about bool * unit?
• 2, (True, ()), (False, ())
• Unit is the multiplicative identity. It’s the empty product type
• Void is the additive identity. �It’s the empty sum type. |bool| + |void| = |bool|. �(we haven’t used void consistently up until now with how some languages instead use unit. See notes)

​

• There are some neat insights to be gained from this relationship, such as efficient functional data structure representations�The algebra (and calculus) of algebraic data types.

Conclusion

• Algebraic Data Types are the essence of data in programming languages.
• When start to combine them with names (e.g., records), subtyping, etc, you start to recover many of the ways we thinking about organize data (e.g., objects).
• When interpreted slight differently, also enables reasoning about infinite data.

​

• Reducible to the composition of a simple set of primitives
• Product types
• Sums types
• Recursive types

​