Algebraic Data Types - mth

Overview Concepts Application

Algebraic Data Types Mark Hibberd

Mar 28, 2011

Mark Hibberd

Algebraic Data Types


Outline Introduction

Outline Gentle(ish) introduction to Algebraic Data Types (ADTs). Demonstrate patterns, or encodings, for reprsenting ADTs. Examples, using Haskell, Scala and Java. Trade-offs, and ways of dealing with them. Designing an algebraric data type.

Mark Hibberd




Terminology Overload Sum type Product type Disjoint, or tagged, union Variant type Recursive, or inductive, data type Enumeratated type Composite type Type constructor Data constructor Class constructor

Mark Hibberd




Algebraic Data Types Composite. Definition by cases. Each case is composed into a single type. Closed. A finite set of cases. Safe. Provides mechanism for helping with (and enforcing) correct handling of all cases. Prevalant. The types of data we use every day. Generalizable?. There are a number of reliable patterns for defining combinators on algraic data-types.

Mark Hibberd



Encoding Morphisms Patterns and Combinators

Encoding Algebraic Data Types

Mark Hibberd




Boolean: Haskell 1

data Boolean = True | False

Mark Hibberd




Boolean: Haskell 1


Type constructor - Boolean Two data constructors - True and False Disjoint union - exactly one of True or False Enumerated type - data constructors have no arguments.

Mark Hibberd




Boolean: Scala 1 2 3

sealed trait Boolean case object True extends Boolean case object False extends Boolean

Mark Hibberd




Boolean: Scala

2 3

sealed trait Boolean case object True extends Boolean case object False extends Boolean

1


1

Mark Hibberd




Church Encoding Representing data types (and their) operations in λ calculus. More simply, can we represent values as functions? Why is this useful?

Mark Hibberd




Church Booleans Formal Definition true ≡ λa.λb. a false ≡ λa.λb. b

Mark Hibberd




Church Booleans: Scala 1 2 3

sealed trait Boolean { def fold[A](t: => A, f: => A): A }

Mark Hibberd




Church Booleans: Scala 1 2 3 4 5 6 7 8 9 10 11 12 13

sealed trait Boolean { def fold[A](t: => A, f: => A): A } object Boolean { def True: Boolean = new Boolean { def fold[A](t: => A, f: => A) = t } def False: Boolean = new Boolean { def fold[A](t: => A, f: => A) = f } }

Mark Hibberd




Church Booleans: Scala

1 2 3 4 5 6 7 8 9 10 11 12 13

sealed trait Boolean { def fold[A](t: => A, f: => A): A } object Boolean { def True: Boolean = new Boolean { def fold[A](t: => A, f: => A) = t } def False: Boolean = new Boolean { def fold[A](t: => A, f: => A) = f } }

Mark Hibberd


true ≡ λa.λb. a false ≡ λa.λb. b



Fold Fold is a catamorphism. A catamorphism is a higher order function that defines a data type. A catamorphism has the form: A∗ → B where A∗ is an algebraic data type, and B, is any other type. All functions on a type can be defined in terms of the catamorphism. If/Else is the catamorphism for boolean.

Mark Hibberd




Church Boolean Operations: Scala

1 2 3 4 5 6

sealed trait Boolean { def fold[A](t: => A, f: => A): A def and(b: Boolean) = fold(b, m) def or(b: Boolean) = fold(this, b)

7 8 9 10 11 12 13 14

def not = fold(False, True) def xor(b: Boolean) = fold( b.fold(False, True), b.fold(True, False) ) }

Mark Hibberd





1 2 3 4 5 6


7 8 9 10 11 12 13 14

and ≡ λm.λn. m n m


Mark Hibberd





1 2 3 4 5 6


7 8 9 10 11 12 13 14

or ≡ λm.λn. m m n


Mark Hibberd





1 2 3 4 5 6


7 8 9 10 11 12 13 14

not ≡ λm.λa.λb. m b a


Mark Hibberd





1 2 3 4 5 6


7 8 9 10 11 12 13 14

xor ≡ λm.λn.λa.λb. m (n b a) (n a b)


Mark Hibberd




There is a machine in your type Side bar There is a striking similarity between the catamorphism of a datastructure, A∗ → B, and the type of a program, or even a virtual machine.

Mark Hibberd




Church Booleans: Haskell

1 2 3 4 5 6

true ≡ λa.λb. a false ≡ λa.λb. b

data Boolean = B { fold :: forall a. a -> a -> a } true = B (\a _ -> a) false = B (\_ b -> b)

7 8 9 10 11 12

and m n = fold m n m or m n = fold m m n not m = fold m true false xor m n = fold m (fold n false true) 13 (fold n false true)

Mark Hibberd





1 2 3 4 5 6

and ≡ λm.λn. m n m


7 8 9 10 11 12


Mark Hibberd





1 2 3 4 5 6

or ≡ λm.λn. m m n


7 8 9 10 11 12


Mark Hibberd





1 2 3 4 5 6

not ≡ λm.λa.λb. m b a


7 8 9 10 11 12


Mark Hibberd





1 2 3 4 5 6

xor ≡ λm.λn.λa.λb. m (n b a) (n a b)


7 8 9 10 11 12


Mark Hibberd




Church Booleans: Java 1 2 3 4 5 6 7

public abstract class Boolean { private Boolean() {} public abstract X fold(Thunk t, Thunk f); public static Boolean True = new Boolean() { public X fold(Thunk t, Thunk f) { return t.apply(); } }; public static Boolean False = new Boolean() { public X fold(Thunk t, Thunk f) { return f.apply(); } };

8 9 10 11 12 13 14 15 16

} Mark Hibberd




Church Booleans: Java 1 2 3

interface Thunk { A apply(); }

Mark Hibberd




Option: Haskell 1

data Option a = None | Some a

Mark Hibberd




Option: Scala 1 2 3

sealed trait Option[A] case class None[A]() extends Option[A] case class Some[A](a: A) extends Option[A]

Mark Hibberd




Option: Scala - Church Encoding 1 2 3 4 5 6 7 8 9 10 11

sealed trait Option[A] { def fold[X](none: => X, some: A => X): X } object Option { def None[A]: Option[A] = new Option[A] { def fold[X](none: => X, some: A => X): X = none } def Some[A](a: A): Option[A] = new Option[A] { def fold[X](none: => X, some: A => X): X = some(a) } }

Mark Hibberd




Option: Java - Church Encoding 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public abstract class Option { private Option() {} public abstract X fold(Thunk none, F some); public static Option None() { return new Option() { public X fold(Thunk none, F some) { return none.apply(); } }; } public static Option Some(final A a) { return new Option() { public X fold(Thunk none, F some) { return some.apply(a); } }; } Mark Hibberd Algebraic Data Types }



Pattern Matching What? Recognise values. Bind names to values. Break down values into parts.

Why? Programming by cases. Compiler can help for algebraic data types.

Mark Hibberd




Option Pattern Matching: Haskell 1 2 3 4 5 6 7 8 9 10 11 12 13 14

isSome :: Option a -> Bool isSome None = False isSome Some _ = True isNone :: Option a -> Bool isNone = not isSome map :: (a -> b) -> Option a -> Option b map _ None = None map f Some s = Some (f s) toList :: Option a -> [a] toList None = [] toList Some s = [a]

Mark Hibberd




Option (Poor) Pattern Matching: Scala 1

val option = somePartialFunction(args)

2 3 4 5 6 7

val mapping = option match { case None => None case Some(s) => Some(needsAnS(s)) }

8 9 10 11 12 13 14 15 16

val set = option match { case None => false case Some(_) => true } val default = option match { case None => defaultvalue case Some(s) => s } Mark Hibberd




Option More (Poor) Pattern Matching: Scala 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

val specialcase = option match { case None => None case Some(‘nugget‘) => None case s@Some(_) => s } val guardcase = option match { case None => None case Some(s) if s == nugget => None case s@Some(_) => s } val overlapIsSet = option match { case None => false case _ => true } Mark Hibberd




Pattern Matching What? Recognise values. Bind names to values. Break down values into parts.

Why? Programming by cases. Compiler can help for algebraic data types.

Why not? Difficult to add a case for all operations. Can replace all pattern matches with higher-order functions.

Mark Hibberd




The Expression Problem “The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).” – Philip Wadler, The Expression Problem, 1998

Mark Hibberd




Expression Problem: Hard to add cases 1 2 3 4 5 6

data Shape = Circle Int | Square Int | Rectangle Int Int area area area area

:: Shape -> Double Circle r = pi * r ^ 2 Square s = s ^ 2 Rectangle w h = w * h

Mark Hibberd




Expression Problem: Hard to add cases Easy to add operations:

Difficult to add cases:

Mark Hibberd




Expression Problem: Hard to add cases 1 2 3 4 5 6 7 8 9 10 11

data Shape = Circle Int | Square Int | Rectangle Int Int area area area area

:: Shape -> Double Circle r = pi * r ^ 2 Square s = s ^ 2 Rectangle w h = w * h

perimeter perimeter perimeter perimeter

:: Shape -> Double Circle r = 2 * pi * r Square s = s * 4 Rectangle w h = (w + h) * 2

Mark Hibberd




Expression Problem: Hard to add cases 1 2 3 4 5 6 7 8 9 10 11 12 13

data Shape = Circle Int | Square Int | Rectangle Int Int | Triangle Int Int Int area area area area area

:: Shape -> Double Circle r = pi * r ^ 2 Square s = s ^ 2 Rectangle w h = w * h Triangle o a h = o * a / 2

perimeter perimeter perimeter perimeter perimeter

:: Shape -> Double Circle r = 2 * pi * r Square s = s * 4 Rectangle w h = (w + h) * 2 Triangle o a h = o + a + h

Mark Hibberd




Expression Problem: Hard to add operations 1 2 3 4 5 6 7 8 9 10 11 12

trait Shape { def area: Double } case class Circle(r: Int) extends Shape { def area = Math.PI * Math.pow(r, 2) } case class Square(s: Int) extends Shape { def area = Math.pow(s, 2) } case class Rectangle(w: Int, h: Int) extends Shape { def area = w * h }

Mark Hibberd




Expression Problem: Hard to add operations Easy to add cases:

Difficult to add operations:

Mark Hibberd




Expression Problem: Hard to add operations 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

trait Shape { def area: Double } case class Circle(r: Int) extends Shape { def area = Math.PI * Math.pow(r, 2) } case class Square(s: Int) extends Shape { def area = Math.pow(s, 2) } case class Rectangle(w: Int, h: Int) extends Shape { def area = w * h } case class Triangle(o: Int, a: Int, h: Int) extends Shape { def area = o * a / 2 } Mark Hibberd




Expression Problem: Hard to add operations 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

trait Shape { def area: Double def perimeter: Double } case class Circle(r: Int) extends Shape { def area = Math.PI * Math.pow(r, 2) def perimeter = 2 * Math.PI * r } case class Square(s: Int) extends Shape { def area = Math.pow(s, 2) def perimeter = s * 4 } case class Rectangle(w: Int, h: Int) extends Shape { def area = w * h def perimeter = (w + h) * 2 } Mark Hibberd




Expression Problem: Hard to add operations 1 2 3 4 5 6 7 8 9 10 11 12 13

data Circle Int data Square Int data Rectangle Int Int class Shape a where area :: a -> Double instance Shape Circle where area Circle r = pi * r ^ 2 instance Shape Square where area Square s = s ^ 2 instance Shape Rectangle where area Rectangle w h = w * h

Mark Hibberd




Expression Problem: Hard to add cases 1 2 3 4 5 6 7 8 9 10

trait Shape case class Circle(r: Int) extends Shape case class Square(s: Int) extends Shape case class Rectangle(w: Int, h: Int) extends Shape def area(s: Shape) = s match { case Circle(r) => Math.PI * Math.pow(r, 2) case Square(s) => Math.pow(s, 2) case Rectangle(w, h) => w * h }

Mark Hibberd




Alleviating the Expression Problem with Combinators

Mark Hibberd




Alleviating the Expression Problem with Combinators 1 2 3 4 5 6 7 8 9 10 11

sealed trait Option[A] { def fold[X](none: => X, some: A => X): X } object Option { def None[A]: Option[A] = new Option[A] { def fold[X](none: => X, some: A => X): X = none } def Some[A](a: A): Option[A] = new Option[A] { def fold[X](none: => X, some: A => X): X = some(a) } }

Mark Hibberd




Alleviating the Expression Problem with Combinators 1 2 3 4 5 6

sealed trait Option[A] { def fold[X](none: => X, some: A => X): X def map[B](f: A => B) = fold(None, v => Some(f(v)) def flatMap[B](f: A => Option[B]) = fold(None, v => f(v))

7 8 9 10 11 12 13

def orElse(other: => A) = fold(other, a => a) def isSet = fold(false, true) def isNotSet = !isSet }

Mark Hibberd




Alleviating the Expression Problem with Combinators 1 2 3 4


Mark Hibberd





2 3 4


1

val mapping = option map (needsAnS(_))

1

Mark Hibberd





val set = option match { case None => false case Some(_) => true }

Mark Hibberd





2 3 4

val set = option match { case None => false case Some(_) => true }

1

option.isSet

1

Mark Hibberd





val default = option match { case None => defaultvalue case Some(s) => s }

Mark Hibberd





2 3 4

val default = option match { case None => defaultvalue case Some(s) => s }

1

option.orElse(defaultValue)

1

Mark Hibberd




Alleviating the Expression Problem with Combinators 1 2 3 4 5 6 7 8 9 10 11 12 13

val chain = option match { case None => defaultvalue case Some(s1) => f1(s1) match { case None => defaultvalue case Some(s2) => f2(s2) match { case None => defaultvalue case Some(s3) => f3(s3) match { case None => defaultvalue case Some(s4) => s4 } } } }

Mark Hibberd




Alleviating the Expression Problem with Combinators 1 2 3 4 5 6

val s4 = option.flatMap( f1(_)).flatMap( f2(_)).flatMap( f3(_)) s4.orElse(defaultValue)

Mark Hibberd




Alleviating the Expression Problem with Combinators 1 2 3 4 5 6 7

val s4 = for { o = (f2(_)) >>= (f3(_)) s4.orElse(defaultValue)

Mark Hibberd




Concept Summary We can use built in language constructs or church encoding to represent algebraic data types. Everything is defined in terms of fold, or the catamorphism, of some data structure. The expression problem is evident, no matter what approach, but we can help combat it by hiding constructors, using combinators and having good language support.

Mark Hibberd




Questions

Mark Hibberd



Goal

Designing an application around ADTs Accessing data from a database. A data type to represent a result. A data type to represent a query. A data type to represent an update. A data type to represent the execution of query or update to obtain a result.

Mark Hibberd



Goal

Design 1 2 3 4 5 6 7 8 9

data DbValue a = Err String | Nul | Value a data Variable = S String | I Int data Ddl = D String [Variable] data Query a = Q String [Variable] (ResultSet -> DbValue a) data Connector a = C (Connection -> DbValue a)

Mark Hibberd



Goal

To The Code

Mark Hibberd



Goal

That’s it.

Mark Hibberd



Goal

References 1

Meijer, E. and Fokkinga, M. and Paterson, R. - Functional programming with bananas, lenses, envelopes and barbed wire - http://bit.ly/gOTczS

2

Philip Wadler - The Expression Problem http://bit.ly/g86Guv

3

Runar Bjarnason - Functonal Programming for Beginners http://vimeo.com/18554216 - http://bit.ly/gaEbxJ

Mark Hibberd
