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
(type=“text/plain”).
Introduce user-defined (algebraic) data types
Examine use of recursive algebraic data types
Explore safe error handling with Maybe
and
Either
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 other
Data 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 types
Using 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
Sum type whose constructors take no arguments (nullary)
data Color = Red | White | Blue
deriving (Show, Eq)
isRed :: Color -> Bool
isRed Red = True
isRed _ = False
deriving
clause generates instances of classesColor'
Grayscale
implicitly defines constructor function that takes argument –
productCan 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/variables
Avoid 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 cons
What 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 conslist of pairs in which first component is key, second is associated value
Dictionary, map, or table data structure
Example: associate student name with academic advisor name
What if key not in list (list empty)?
error
call
with custom error message?"NONE"
?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 assigned
Example: 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 hierarchy
Rust’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
.