with Interpreters

and Functional Programming

Chapter 21

Algebraic Data Types

**H. Conrad Cunningham**

**24 October 2018**

Copyright (C) 2017, 2018, H. Conrad Cunningham

**Acknowledgements**: I originally created these slides in Fall 2017 to accompany what is now Chapter 21, Algebraic Data Types, in the 2018 version of the textbook *Exploring Languages with Interpreters and Functional Programming*.

**Browser Advisory**: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of October 2018 is a recent version of Firefox from Mozilla.

**Source Code**: The Haskell module for this chapter is in file `AlgDataTypes.hs`

.

Introduce user-defined (algebraic) data types

Examine use of recursive algebraic data types

Explore safe error handling with

`Maybe`

and`Either`

- Algebraic Data Type:
*Composite*data type formed by combining other types

Careful! Acronym ADT sometimes used for two different structures

**Algebraic Data Type**specified with its*syntax*(structure) — rules on how to compose and decompose**Abstract Data Type**specified with its*semantics*(meaning) — rules on how operations behave in relation to each otherData abstraction (e.g. Chapter 7, Rational Arithmetic)

Algebraic data types formed by algebra of operations — recursive

**Sum**operation that constructs values with one variant among several — also*tagged*,*disjoint union*, or*variant*typesUsing

*alternation*operator — choice of exactly one of two alternatives**Product**operation that combines several values (*fields*) together to construct single value—also*tuple*or*record*Using

*Cartesian product*operator

Haskell enables definition of new data types

`Datatype`

is (capitalized) name of new type constructor with*arity*`N`

`a1 a2 ... aN`

are`N`

distinct type variables for parameters`Constr1 Constr2 ... ConstrM`

are`M`

distinct data constructors

- Enumerated type
Sum type whose constructors take no arguments (

*nullary*)

- Each constructor corresponds to single value

```
data Color = Red | White | Blue
deriving (Show, Eq)
isRed :: Color -> Bool
isRed Red = True
isRed _ = False
```

- Optional
`deriving`

clause generates instances of classes

`Color'`

- Constructor
`Grayscale`

implicitly defines constructor function that takes argument – product

Can derive instances for classes

`Eq`

,`Ord`

,`Enum`

,`Bounded`

,`Read`

,`Show`

using defaults based on declaration`Eq`

includes`(==)`

,`(/=)`

methods — compare tags and values`Ord`

adds`compare`

,`(<)`

,`(<=)`

,`(>)`

,`(>=)`

,`max`

,`min`

methods — using declared order`Enum`

assigns integers increasing from 0 at left`Bounded`

assigns`minBound`

to left,`maxBound`

to right

`Show`

enables function`show`

to convert to syntactically correct expression string — with constructor names, parentheses, spaces`show (Grayscale 3)`

yields`"Grayscale 3"`

`Read`

enables function`read`

to parse above format into value

`Bool`

`False < True`

yields Boolean`True`

`False > True`

yields Boolean`False`

`show x`

yields string`"False"`

or`"True"`

`Point`

2-D point with polymorphic type values — product

Both values associated with constructor

`Pt`

same type`Pt`

implicitly function of type`a -> a -> Point a`

`Set`

```
data Set a = Set [a]
deriving (Show, Eq)
makeSet :: Eq a => [a] -> Set a
makeSet xs = Set (nub xs) -- nub removes duplicates
```

`Set`

used for both data type and constructor — different namespaces for types versus functions/variablesAvoid except when only one data constructor

Allows type parameters like

`data`

Does

**not**introduce new type, just alias for existing type

```
data Result a = Ok a | Err String
deriving (Show, Eq)
divide :: Int -> Int -> Result Int
divide _ 0 = Err "Divide by zero"
divide x y = Ok (x `div` y)
-- use to handle error flexibly
f :: Int -> Int -> Int
f x y =
case divide x y of
Ok z -> z
Err s -> maxBound
```

`case`

expression uses pattern match inside function`Maybe`

and`Either`

types defined in Prelude

`BinTree`

(1)Binary tree with value in each node – recursive

“empty” (denoted by

`Empty`

)“node” (denoted by

`Node`

) with value of type`a`

and “left” and “right” subtrees

`BinTree`

(2)Three-part “record” with nested records, no explicit pointers

`flatten`

Under what circumstances does

`flatten t`

terminate normally?What is time complexity of

`flatten t`

?

`flatten`

```
flatten' :: BinTree a -> [a]
flatten' t = inorder t []
where inorder Empty xs = xs
inorder (Node l v r) xs =
inorder l (v : inorder r xs)
```

`inorder`

builds list of values from right using consWhat is time complexity of

`flatten' t`

?

`treeFold`

Reduce tree of values to value using *associative* operation

`Tree`

Values only at leaves

Infix constructor

`:^:`

Below: complete binary tree with height 3, integers 1, 2, 3, 4 at leaves

`fringe`

```
fringe' :: Tree a -> [a]
fringe' t = leaves t []
where leaves (Leaf v) = ((:) v)
leaves (l :^: r) = leaves l . leaves r
```

`leaves`

builds list of leaves from right using cons

- Association list:
list of pairs in which first component is

**key**, second is associated**value**

*Dictionary*,*map*, or*table*data structureExample: associate student name with academic advisor name

What if key not in list (list empty)?

- Leave undefined for empty list?
- Insert
`error`

call with custom error message? - Return some default value for advisor, e.g.
`"NONE"`

? - Return
*null reference*?

- 1, 2 require exception handling, break referential transparency
- 3 not general
- 4 not possible in Haskell — Hoare’s “billion dollar mistake”

`Maybe`

What is safer, more general approach?

`Maybe`

(1)`advisorList`

association list pairing students with their advisors`defaultAdvisor`

advisor student should consult if no advisor assignedExample:

`whoIsAdvisor`

returns`defaultAdvisor`

for`Nothing`

`Maybe`

(2)`Data.Maybe`

library operations

```
fromMaybe :: a -> Maybe a -> a
isJust :: Maybe a -> Bool
isNothing :: Maybe a -> Bool
fromJust :: Maybe a -> a -- error if Nothing
```

Allow following rewrites of `whoIsAdvisor`

`Either`

What if want specific error messages?

```
data Either a b -- from Prelude
= Left a -- convention: error msg
| Right b -- convention: value
deriving (Eq, Ord, Read, Show)
```

Available in `Data.Either`

library

Java 8’s final class

`Optional<T>`

Scala’s

`Option[T]`

case class hierarchyRust’s

`Option<T>`

enum (algebraic data type)Idris, Elm, PureScript’s Haskell-like

`Maybe`

Object-oriented languages Null Object design pattern

Algebraic data types

Recursive data types

Safe error-handling with

`Maybe`

and`Either`

The Haskell module for this chapter is in file `AlgDataTypes.hs`

.