CMPT383 Comparative Programming Languages

Lecture 4-1: Custom Types

Yuepeng Wang
Spring 2025

1
Overview
• Custom data types

• Type synonyms

• Recursive data types

• Custom type classes

• Functors

• Kinds

2
Defining New Types
• We can define our own (data) types using the data keyword

• Example: the Bool type in the standard library

data Bool = False | True

• The part before the equal sign denotes the type

• The parts after the equal sign are data constructors (or value constructors)

• The | symbol is read as or

• Meaning: the Bool type can have a value of False or True

3
Data Constructors
• Data constructors can take parameters (fields) and produce a value
data Shape = Circle Float Float Float
| Rectangle Float Float Float Float

• Meaning: the Shape type can have circle and rectangle values
• Each circle has three parameters (x, y, radius)
• Each rectangle has four parameters (x, y, length, width)

• Data constructors are functions

ghci> :t Circle
Circle :: Float -> Float -> Float -> Shape
ghci> :t Rectangle
Rectangle :: Float -> Float -> Float -> Float -> Shape
4
Data Constructors
• Data constructors can be pattern matched

• Example: area of a shape

area :: Shape -> Float
area (Circle _ _ radius) = pi * radius * radius
area (Rectangle _ _ length width) = length * width

• Execution
ghci> area (Circle 0 0 1)
3.1415927
ghci> area $ Rectangle 0 0 20 10
200.0

5
Defining Types using Custom Types
• We can use custom types in the definition of a new type
data Point = Point Float Float
data Shape = Circle Point Float
| Rectangle Point Float Float

• Note that we can use the same name for a type and a data constructor

• Common for types with only one data constructor

• Example: create a circle at the origin of the coordinate

originCircle :: Float -> Shape
originCircle radius = Circle (Point 0 0) radius

6
Exporting Custom Types
• We can export custom types and data constructors in a module
module Shapes
( Point(..)
, Shape(..)
, originCircle
) where

• Export all data constructors: use ..

• Export selected data constructors: provide a comma-separated list

• Export no data constructors: just provide the type name

• We can still create an instance of the type using other functions

7
Record Syntax
• If a data constructor has several fields and it’s not obvious which field is
which, we can use the record syntax
data Car = Car { make :: String
, model :: String
, year :: Int }

• Can create values using the record syntax

• Fields are functions

ghci> :t model
model :: Car -> String
ghci> let c = Car {make="Ford", model="Focus", year=2022}
ghci> model c
"Focus"

8
Type Constructors
• Type constructors can take types as parameters and produce a new type
data Maybe a = Nothing
| Just a

• Here, a is a type parameter

• Maybe is a type constructor (not a type)
• It can produce a type of Maybe Int, Maybe Shape, etc
• No value can simply have type “Maybe”
• Nothing is a value (a data constructor with no parameters) of type Maybe a.
Its type is polymorphic
• Just is a data constructor that has type a -> Maybe a

9
Type Constructors
• A nullary type constructor (zero parameters) is a type

• What other type constructors have we learned?

• Data.Map.Map takes two type parameters: key type and value type

• [ ] takes a type parameter: element type. [a] is a syntactic sugar of [ ] a

• A type is said to be concrete if

• it doesn’t take any type parameters at all (e.g., Int, Bool), or

• it takes type parameters and they’re are instantiated (e.g., Maybe Int)
10
Example: Vector
• 3-dimensional vector where all fields have the same type

data Vector a = Vector a a a

• Implement a vplus function for vector addition

vplus :: Num a => Vector a -> Vector a -> Vector a

vplus (Vector x1 y1 z1) (Vector x2 y2 z2)
= Vector (x1 + x2) (y1 + y2) (z1 + z2)

11
Example: elemIndex
• The elemIndex function in Data.List returns the index of the first element
in the given list which is equal to the query element, or Nothing if there is
no such element

• What is the type of elemIndex?

• One possible implementation

elemIndex :: Eq a => a -> [a] -> Maybe Int
elemIndex v xs = elemIndexAux 0 v xs
where elemIndexAux :: Eq a => Int -> a -> [a] -> Maybe Int
elemIndexAux _ _ [] = Nothing
elemIndexAux i v (x:xs)
| v == x = Just i
| otherwise = elemIndexAux (i + 1) v xs
12
Example: Either
• Either is a type constructor that has two type parameters

data Either a b = Left a | Right b

• If Left is used, its contents have type a

• If Right is used, its contents have type b

• Either is more general than Maybe

• Maybe can represent the results of computations that could fail
• In addition, Either can distinguish different failures

13
Deriving Type Classes
ghci> Vector 'a' 'b' 'c'
<interactive>: ... error:
• No instance for (Show (Vector Char)) ...

• The error is because "Vector a" is not an instance of the Show type class

• We can easily make a custom type an instance of some type classes

• Eq, Ord, Show, Read, Enum, Bounded
• Enum is for things that have predecessors and successors
• Bounded is for things that have minBound and maxBound

• To fix the Show problem

data Vector a = Vector a a a deriving (Show)

14
Example: Day
• A Day type that represents the days of a week
data Day = Monday|Tuesday|Wednesday|Thursday|Friday|Saturday|Sunday
deriving (Eq, Ord, Show, Read, Enum, Bounded)

• The functions from the Eq, Ord, Show, Read, Enum, and Bounded type
classes are available to use
ghci> read "Monday" :: Day
Monday
ghci> succ Monday
Tuesday
ghci> maxBound :: Day
Sunday
ghci> [Tuesday .. Friday]
[Tuesday,Wednesday,Thursday,Friday]

15
Type Synonyms
• We can create synonyms for types using the type keyword
• Synonyms and original types are interchangeable

type String = [Char]

• We can parametrize type synonyms

type AssocList k v = [(k, v)]

• We can partially apply type parameters and get new type constructors
type IntMap v = Map Int v
type IntMap = Map Int

16
Recursive Data Types
• A data constructor can have several fields and each field must be
of some type (can even be the type to be defined)
• We get a recursive data type if the type has itself as a type in the fields
data List a = Empty | Cons a (List a) deriving (Eq, Ord, Show, Read)

• Record syntax
data List a = Empty | Cons { listHead :: a, listTail :: List a }
deriving (Eq, Ord, Show, Read)

• Example: list concatenation

listConcat :: List a -> List a -> List a
listConcat Empty ys = ys
listConcat (Cons x xs) ys = Cons x (listConcat xs ys)

17
Recursive Data Types
• A binary tree is an empty tree or a node with a value and two binary trees
data Tree a = EmptyTree
| Node a (Tree a) (Tree a)
deriving (Show)

• A binary search tree (with unique keys) is a binary tree where each node
stores a key greater than all keys in the left subtree but less than all keys
in the right subtree
• Example: write a function to check if a key is in a binary search tree
treeElem :: Ord a => a -> Tree a -> Bool
treeElem k EmptyTree = False
treeElem k (Node x left right)
| k == x = True
| k < x = treeElem k left
| k > x = treeElem k right
18
Type Classes
• A type class defines some function, similar to an interface

• If a type T is an instance of a type class, we can use the functions that the
type class defines with T
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
x == y = not (x /= y)
x /= y = not (x == y)

• The type declarations for functions are required

• The default function implementations are optional
• Need to override at least one function for termination

19
Instance of a Type Class
• We can make a custom type an instance of a type class by hand
• Example: traffic light
data TrafficLight = Red | Yellow | Green

• Make TrafficLight an instance of Eq

instance Eq TrafficLight where
Red == Red = True
Yellow == Yellow = True
Green == Green = True
_ == _ = False

• A minimal set of functions to implement/override is called a minimal

complete definition for the type class (e.g., == for Eq)
• If no default implementations, the minimal complete definition has both funcs

20
Instance of a Type Class
• Make TrafficLight an instance of the Show type class
instance Show TrafficLight where
show Red = "Red light"
show Yellow = "Yellow light"
show Green = "Green light"

• Execution
ghci> Green
Green light

21
Subclasses
• We can make type classes that are subclasses of other type classes

• Syntax: class Superclass => Subclass where

• Example
class Eq a => Ord a where
(<=) :: a -> a -> Bool
(<) :: a -> a -> Bool
...
x < y = x <= y && x /= y

• Subclassing is a class constraint on a class declaration

• Functions in subclass can assume existence of functions in superclass

22
Parameterized Types as Instances
• We can make a parameterized type an instance of a type class

• Example: Maybe a
instance Eq a => Eq (Maybe a) where
Just x == Just y = x == y
Nothing == Nothing = True
_ == _ = False

• Note we cannot make “Maybe” an instance because Maybe is not a type

• The class constraint is added because we need == on x and y

23
Example: YesNo
• Some weakly typed languages (e.g., JavaScript) treat an “empty” value as
False and other values as True for conditions in if
• Haskell doesn’t work like that, but we can simulate it by a YesNo type
class
class YesNo a where
yesno :: a -> Bool

• For Int instance YesNo Int where

yesno 0 = False
yesno _ = True

• For [a] instance YesNo [a] where

yesno [] = False
yesno _ = True

24
Example: YesNo
• For Bool
instance YesNo Bool where
yesno = id
id :: a -> a is the identity function

• For Maybe a
instance YesNo (Maybe a) where
yesno Nothing = False
yesno _ = True

• The “if” function

yesnoIf :: YesNo a => a -> b -> b -> b
yesnoIf cond yesRes noRes = if yesno cond then yesRes else noRes

25
Functors
• The Functor type class is for things that can be mapped over
class Functor f where
fmap :: (a -> b) -> f a -> f b

• map applies a function to every element in a list

• Intuitively, fmap is a generalization of map. It applies a function to every

element inside some structure (functor) without changing the structure itself

• A functor in Haskell is an instance of the Functor type class that obeys the
following laws
• fmap id == id
• fmap (g . h) == fmap g . fmap h
26
List as a Functor
• [ ] (List) is a functor
instance Functor [] where
-- fmap :: (a -> b) -> [a] -> [b]
fmap = map

• map id == id

• map (g . h) == map g . map h

ghci> fmap (+1) [1, 2, 3]
[2,3,4]

27
Maybe as a Functor
• Maybe is a functor
instance Functor Maybe where
-- fmap :: (a -> b) -> Maybe a -> Maybe b
fmap f (Just x) = Just (f x)
fmap _ Nothing = Nothing

• fmap id (Just x) == Just (id x) == Just x == id (Just x)

• fmap id Nothing == Nothing == id Nothing
• fmap (g . h) (Just x) == Just ((g . h) x) == Just (g (h x))
== fmap g (Just (h x)) == fmap g (fmap h (Just x)) == (fmap g . fmap h) (Just x)
• fmap (g . h) Nothing = Nothing == fmap g Nothing == (fmap g . fmap h) Nothing
ghci> fmap (+1) (Just 10)
Just 11
ghci> fmap (+1) Nothing
Nothing

28
Tree as a Functor
• Tree is also a functor
instance Functor Tree where
-- fmap :: (a -> b) -> Tree a -> Tree b
fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)
fmap _ EmptyTree = EmptyTree

• We can check that both functor laws hold

• Execution example
ghci> fmap (+1) (Node 2
(Node 1 EmptyTree EmptyTree)
(Node 3 EmptyTree EmptyTree))
Node 3 (Node 2 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree)
ghci> fmap (+1) EmptyTree
EmptyTree

29
Either a as a Functor
• Either a b has two type parameters, but we can partially apply the type
constructor to obtain “Either a”, which is also a functor!
instance Functor (Either a) where
-- fmap :: (b -> c) -> Either a b -> Either a c
fmap f (Right x) = Right (f x)
fmap _ (Left x) = Left x

• Both functor laws hold

• Execution example
ghci> fmap (+1) (Right 10)
Right 11
ghci> fmap (+1) (Left "error")
Left "error"

30
Example: inc
• Define a general increment function on functors
• What is its type?
inc :: (Functor f, Num a) => f a -> f a
inc = fmap (+1)

• Execution example
ghci> inc [1, 2, 3]
[2,3,4]
ghci> inc (Just 10)
Just 11
ghci> inc (Node 1 EmptyTree (Node 2 EmptyTree EmptyTree))
Node 2 EmptyTree (Node 3 EmptyTree EmptyTree)
ghci> inc (Right 10)
Right 11

31
Kinds
• Functions take parameters to produce values. Type constructors take
parameters to produce types (eventually)
• Type is an attribute of data. Kind is an attribute of type (“type” of type)
ghci> :k Int
Int :: *
ghci> :k Maybe
Maybe :: * -> *
ghci> :k Either
Either :: * -> * -> *

• Here, * denotes a type

• The kind of all functors must be * -> *

32