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.

Lecture Goals

• Introduce user-defined (algebraic) data types

• Examine use of recursive algebraic data types

• Explore safe error handling with Maybe and Either

Definition

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 other

    Data abstraction (e.g. Chapter 7, Rational Arithmetic)

Construction

Algebraic data types formed by algebra of operations — recursive

1. 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

2. Product operation that combines several values (fields) together to construct single value—also tuple or record

   Using Cartesian product operator

Declaration

Haskell enables definition of new data types

    data Datatype a1 a2 ... aN = Constr1 | Constr2 | ... | ConstrM

• 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 Types

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

Example Type Color'

data Color' = Red' | Blue' | Grayscale Int
              deriving (Show, Eq)

• Constructor Grayscale implicitly defines constructor function that takes argument – product

Deriving Class Instances (1)

• 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

Deriving Class Instances (2)

• 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

Type Bool

data Bool = False | True -- as in Prelude
            deriving (Ord, Show)

• False < True yields Boolean True

• False > True yields Boolean False

• show x yields string "False" or "True"

Example Type Point

data Point a = Pt a a
               deriving (Show, Eq)

• 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

Example Type 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

Type Synonyms

type Matrix a = [[a]]

• Allows type parameters like data

• Does not introduce new type, just alias for existing type

Types to Encode Errors

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

Type BinTree (1)

data BinTree a = Empty | Node (BinTree a) a (BinTree a)
                 deriving (Show, Eq)

• 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

Type BinTree (2)

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

Binary Tree BinTree

Function flatten

flatten :: BinTree a -> [a] 
flatten Empty        = [] 
flatten (Node l v r) = flatten l ++ [v] ++ flatten r 

flatten (Node (Node Empty 3 Empty) 5 
              (Node (Node Empty 7 Empty) 1 Empty))
    == [3,5,7,1]

• Under what circumstances does flatten t terminate normally?

• What is time complexity of flatten t?

Tail Recursive 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?

Function treeFold

Reduce tree of values to value using associative operation

treeFold :: (a -> a -> a) -> a -> BinTree a -> a 
treeFold op i Empty        = i 
treeFold op i (Node l v r) = op (op (treeFold op i l) v) 
                                (treeFold op i r)

Type Tree

data Tree a = Leaf a | Tree a :^: Tree a
              deriving (Show, Eq)

• Values only at leaves

• Infix constructor :^:

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

    ((Leaf 1 :^: Leaf 2) :^: (Leaf 3 :^: Leaf 4))

Function fringe

fringe :: Tree a -> [a]
fringe (Leaf v)  = [v] 
fringe (l :^: r) = fringe l ++ fringe r 

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

Error Handling Motivation (1)

Association list:

list 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

    lookup' :: String -> [(String,String)] -> String
    lookup' key ((x,y):xys)
        | key == x  =  y
        | otherwise =  lookup' key xys

Error-Handling Motivation (2)

What if key not in list (list empty)?

1. Leave undefined for empty list?
2. Insert error call with custom error message?
3. Return some default value for advisor, e.g. "NONE"?
4. Return null reference?

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

Type Maybe

What is safer, more general approach?

    data Maybe a   -- type from Prelude
        = Nothing  -- no value
        | Just a   -- wraps value

    lookup'' :: (Eq a) => a -> [(a,b)] -> Maybe b
    lookup'' key []  =  Nothing
    lookup'' key ((x,y):xys)
        | key == x   =  Just y
        | otherwise  =  lookup'' key xys

Using 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

    whoIsAdvisor :: String -> String
    whoIsAdvisor std =
        case lookup'' std advisorList of
            Nothing   -> defaultAdvisor
            Just prof -> prof

Using 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

    whoIsAdvisor' std = 
        fromMaybe defaultAdvisor $ lookup std advisorList 

    whoIsAdvisor'' std =
        let ad = lookup std advisorList
        in if isJust ad then fromJust ad else defaultAdvisor

Type 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

    fromLeft  :: a -> Either a b -> a
    fromRight :: b -> Either a b -> b
    isLeft    :: Either a b -> Bool
    isRight   :: Either a b -> Bool

Other Languages

• 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

Key Ideas

• Algebraic data types

• Recursive data types

• Safe error-handling with Maybe and Either

Source Code

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