COMP3141 – Functors, Applicatives, and Monads
Recap Applicative Functors Monads
Software System Design and Implementation
Functors, Applicatives, and Monads
Christine Rizkallah
UNSW Sydney
Term 2 2021
1
Recap Applicative Functors Monads
Motivation
We’ll be looking at three very common abstractions:
used in functional programming and,
increasingly, in imperative programming as well.
Unlike many other languages, these abstractions are reified into bona fide type classes
in Haskell, where they are often left as mere ”design patterns” in other programming
languages.
2
Recap Applicative Functors Monads
Motivation
We’ll be looking at three very common abstractions:
used in functional programming and,
increasingly, in imperative programming as well.
Unlike many other languages, these abstractions are reified into bona fide type classes
in Haskell, where they are often left as mere ”design patterns” in other programming
languages.
3
Recap Applicative Functors Monads
Kinds
Recall that terms in the type level language of Haskell are given kinds.
The most basic kind is written as *.
Types such as Int and Bool have kind *.
Seeing as Maybe is parameterised by one argument, Maybe has kind * -> *:
given a type (e.g. Int), it will return a type (Maybe Int).
Question: What’s the kind of State?
4
Recap Applicative Functors Monads
Functor
Recall the type class defined over type constructors called Functor.
class Functor f where
fmap :: (a -> b) -> f a -> f b
Functor Laws
1 fmap id == id
2 fmap f . fmap g == fmap (f . g)
We’ve seen instances for lists, Maybe, tuples and functions.
Other instances include:
IO (how?)
State s (how?)
Gen
Demonstrate in live-coding
5
Recap Applicative Functors Monads
Functor
Recall the type class defined over type constructors called Functor.
class Functor f where
fmap :: (a -> b) -> f a -> f b
Functor Laws
1 fmap id == id
2 fmap f . fmap g == fmap (f . g)
We’ve seen instances for lists, Maybe, tuples and functions.
Other instances include:
IO (how?)
State s (how?)
Gen
Demonstrate in live-coding
6
Recap Applicative Functors Monads
QuickCheck Generators
Recall the Arbitrary class has a function:
arbitrary :: Gen a
The type Gen is an abstract type for QuickCheck generators. Suppose we have a
function:
toString :: Int -> String
And we want a generator for String (i.e. Gen String) that is the result of applying
toString to arbitrary Ints.
Then we use fmap!
7
Recap Applicative Functors Monads
Binary Functions
Suppose we want to look up a student’s zID and program code using these functions:
lookupID :: Name -> Maybe ZID
lookupProgram :: Name -> Maybe Program
And we had a function:
makeRecord :: ZID -> Program -> StudentRecord
How can we combine these functions to get a function of type
Name -> Maybe StudentRecord?
lookupRecord :: Name -> Maybe StudentRecord
lookupRecord n = let zid = lookupID n
program = lookupProgram n
in ?
8
Recap Applicative Functors Monads
Binary Functions
Suppose we want to look up a student’s zID and program code using these functions:
lookupID :: Name -> Maybe ZID
lookupProgram :: Name -> Maybe Program
And we had a function:
makeRecord :: ZID -> Program -> StudentRecord
How can we combine these functions to get a function of type
Name -> Maybe StudentRecord?
lookupRecord :: Name -> Maybe StudentRecord
lookupRecord n = let zid = lookupID n
program = lookupProgram n
in ?
9
Recap Applicative Functors Monads
Binary Map?
We could imagine a binary version of the maybeMap function:
maybeMap2 :: (a -> b -> c)
-> Maybe a -> Maybe b -> Maybe c
But then, we might need a trinary version.
maybeMap3 :: (a -> b -> c -> d)
-> Maybe a -> Maybe b -> Maybe c -> Maybe d
Or even a 4-ary version, 5-ary, 6-ary. . .
this would quickly become impractical!
10
Recap Applicative Functors Monads
Binary Map?
We could imagine a binary version of the maybeMap function:
maybeMap2 :: (a -> b -> c)
-> Maybe a -> Maybe b -> Maybe c
But then, we might need a trinary version.
maybeMap3 :: (a -> b -> c -> d)
-> Maybe a -> Maybe b -> Maybe c -> Maybe d
Or even a 4-ary version, 5-ary, 6-ary. . .
this would quickly become impractical!
11
Recap Applicative Functors Monads
Using Functor
Using fmap gets us part of the way there:
lookupRecord’ :: Name -> Maybe (Program -> StudentRecord)
lookupRecord’ n = let zid = lookupID n
program = lookupProgram n
in fmap makeRecord zid
— what about program?
But, now we have a function inside a Maybe.
We need a function to take:
A Maybe-wrapped fn Maybe (Program -> StudentRecord)
A Maybe-wrapped argument Maybe Program
And apply the function to the argument, giving us a result of type
Maybe StudentRecord?
12
Recap Applicative Functors Monads
Using Functor
Using fmap gets us part of the way there:
lookupRecord’ :: Name -> Maybe (Program -> StudentRecord)
lookupRecord’ n = let zid = lookupID n
program = lookupProgram n
in fmap makeRecord zid
— what about program?
But, now we have a function inside a Maybe.
We need a function to take:
A Maybe-wrapped fn Maybe (Program -> StudentRecord)
A Maybe-wrapped argument Maybe Program
And apply the function to the argument, giving us a result of type
Maybe StudentRecord?
13
Recap Applicative Functors Monads
Applicative
This is encapsulated by a subclass of Functor called Applicative:
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
Maybe is an instance, so we can use this for lookupRecord:
lookupRecord :: Name -> Maybe StudentRecord
lookupRecord n = let zid = lookupID n
program = lookupProgram n
in fmap makeRecord zid <*> program
— or pure makeRecord <*> zid <*> program
14
Recap Applicative Functors Monads
Applicative
This is encapsulated by a subclass of Functor called Applicative:
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
Maybe is an instance, so we can use this for lookupRecord:
lookupRecord :: Name -> Maybe StudentRecord
lookupRecord n = let zid = lookupID n
program = lookupProgram n
in fmap makeRecord zid <*> program
— or pure makeRecord <*> zid <*> program
15
Recap Applicative Functors Monads
Using Applicative
In general, we can take a regular function application:
f a b c d
And apply that function to Maybe (or other Applicative) arguments using this
pattern (where <*> is left-associative):
pure f <*> ma <*> mb <*> mc <*> md
16
Recap Applicative Functors Monads
Relationship to Functor
All law-abiding instances of Applicative are also instances of Functor, by defining:
fmap f x = pure f <*> x
Sometimes this is written as an infix operator, <$>, which allows us to write:
pure f <*> ma <*> mb <*> mc <*> md
as:
f <$> ma <*> mb <*> mc <*> md
Proof exercise: From the applicative laws (next slide), prove that this implementation
of fmap obeys the functor laws.
17
Recap Applicative Functors Monads
Applicative laws
— Identity
pure id <*> v = v
— Homomorphism
pure f <*> pure x = pure (f x)
— Interchange
u <*> pure y = pure ($ y) <*> u
— Composition
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
These laws are a bit complex, and we certainly don’t expect you to memorise them,
but pay attention to them when defining instances!
18
Recap Applicative Functors Monads
Applicative Lists
There are two ways to implement Applicative for lists:
(<*>) :: [a -> b] -> [a] -> [b]
1 Apply each of the given functions to each of the given arguments, concatenating
all the results.
2 Apply each function in the list of functions to the corresponding value in the list
of arguments.
Question: How do we implement pure?
The second one is put behind a newtype (ZipList) in the Haskell standard library.
19
Recap Applicative Functors Monads
Applicative Lists
There are two ways to implement Applicative for lists:
(<*>) :: [a -> b] -> [a] -> [b]
1 Apply each of the given functions to each of the given arguments, concatenating
all the results.
2 Apply each function in the list of functions to the corresponding value in the list
of arguments.
Question: How do we implement pure?
The second one is put behind a newtype (ZipList) in the Haskell standard library.
20
Recap Applicative Functors Monads
Applicative Lists
There are two ways to implement Applicative for lists:
(<*>) :: [a -> b] -> [a] -> [b]
1 Apply each of the given functions to each of the given arguments, concatenating
all the results.
2 Apply each function in the list of functions to the corresponding value in the list
of arguments.
Question: How do we implement pure?
The second one is put behind a newtype (ZipList) in the Haskell standard library.
21
Recap Applicative Functors Monads
Applicative Lists
There are two ways to implement Applicative for lists:
(<*>) :: [a -> b] -> [a] -> [b]
1 Apply each of the given functions to each of the given arguments, concatenating
all the results.
2 Apply each function in the list of functions to the corresponding value in the list
of arguments.
Question: How do we implement pure?
The second one is put behind a newtype (ZipList) in the Haskell standard library.
22
Recap Applicative Functors Monads
Applicative Lists
There are two ways to implement Applicative for lists:
(<*>) :: [a -> b] -> [a] -> [b]
1 Apply each of the given functions to each of the given arguments, concatenating
all the results.
2 Apply each function in the list of functions to the corresponding value in the list
of arguments.
Question: How do we implement pure?
The second one is put behind a newtype (ZipList) in the Haskell standard library.
23
Recap Applicative Functors Monads
Other instances
QuickCheck generators: Gen
Recall from Wednesday Week 4:
data Concrete = C [Char] [Char]
deriving (Show, Eq)
instance Arbitrary Concrete where
arbitrary = C <$> arbitrary <*> arbitrary
Functions: ((->) x)
Tuples: ((,) x) We can’t implement pure without an extra constraint!
IO and State s:
24
Recap Applicative Functors Monads
Other instances
QuickCheck generators: Gen
Recall from Wednesday Week 4:
data Concrete = C [Char] [Char]
deriving (Show, Eq)
instance Arbitrary Concrete where
arbitrary = C <$> arbitrary <*> arbitrary
Functions: ((->) x)
Tuples: ((,) x) We can’t implement pure without an extra constraint!
IO and State s:
25
Recap Applicative Functors Monads
Other instances
QuickCheck generators: Gen
Recall from Wednesday Week 4:
data Concrete = C [Char] [Char]
deriving (Show, Eq)
instance Arbitrary Concrete where
arbitrary = C <$> arbitrary <*> arbitrary
Functions: ((->) x)
Tuples: ((,) x) We can’t implement pure without an extra constraint!
IO and State s:
26
Recap Applicative Functors Monads
Other instances
QuickCheck generators: Gen
Recall from Wednesday Week 4:
data Concrete = C [Char] [Char]
deriving (Show, Eq)
instance Arbitrary Concrete where
arbitrary = C <$> arbitrary <*> arbitrary
Functions: ((->) x)
Tuples: ((,) x) We can’t implement pure without an extra constraint!
IO and State s:
27
Recap Applicative Functors Monads
On to Monads
Functors are types for containers where we can map pure functions on their
contents.
Applicative Functors are types where we can combine n containers with a n-ary
function.
The last and most commonly-used higher-kinded abstraction in Haskell programming is
the Monad.
Monads
Monads are types m where we can sequentially compose functions of the form a -> m
b
28
Recap Applicative Functors Monads
On to Monads
Functors are types for containers where we can map pure functions on their
contents.
Applicative Functors are types where we can combine n containers with a n-ary
function.
The last and most commonly-used higher-kinded abstraction in Haskell programming is
the Monad.
Monads
Monads are types m where we can sequentially compose functions of the form a -> m
b
29
Recap Applicative Functors Monads
On to Monads
Functors are types for containers where we can map pure functions on their
contents.
Applicative Functors are types where we can combine n containers with a n-ary
function.
The last and most commonly-used higher-kinded abstraction in Haskell programming is
the Monad.
Monads
Monads are types m where we can sequentially compose functions of the form a -> m
b
30
Recap Applicative Functors Monads
Monads
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
Sometimes in old documentation the function return is included here, but it is just an
alias for pure. It has nothing to do with return as in C/Java/Python etc.
Consider for:
Maybe
Lists
(x ->) (the Reader monad)
(x,) (the Writer monad, assuming a Monoid instance for x)
Gen
IO, State s etc.
31
Recap Applicative Functors Monads
Monads
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
Sometimes in old documentation the function return is included here, but it is just an
alias for pure. It has nothing to do with return as in C/Java/Python etc.
Consider for:
Maybe
Lists
(x ->) (the Reader monad)
(x,) (the Writer monad, assuming a Monoid instance for x)
Gen
IO, State s etc.
32
Recap Applicative Functors Monads
Monads
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
Sometimes in old documentation the function return is included here, but it is just an
alias for pure. It has nothing to do with return as in C/Java/Python etc.
Consider for:
Maybe
Lists
(x ->) (the Reader monad)
(x,) (the Writer monad, assuming a Monoid instance for x)
Gen
IO, State s etc.
33
Recap Applicative Functors Monads
Monads
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
Sometimes in old documentation the function return is included here, but it is just an
alias for pure. It has nothing to do with return as in C/Java/Python etc.
Consider for:
Maybe
Lists
(x ->) (the Reader monad)
(x,) (the Writer monad, assuming a Monoid instance for x)
Gen
IO, State s etc.
34
Recap Applicative Functors Monads
Monad Laws
We can define a composition operator with (>>=):
(<=<) :: (b -> m c) -> (a -> m b) -> (a -> m c)
(f <=< g) x = g x >>= f
Monad Laws
f <=< (g <=< x) == (f <=< g) <=< x -- associativity pure <=< f == f -- left identity f <=< pure == f -- right identity These are similar to the monoid laws, generalised for multiple types inside the monad. This sort of structure is called a category in mathematics. 35 Recap Applicative Functors Monads Monad Laws We can define a composition operator with (>>=):
(<=<) :: (b -> m c) -> (a -> m b) -> (a -> m c)
(f <=< g) x = g x >>= f
Monad Laws
f <=< (g <=< x) == (f <=< g) <=< x -- associativity
pure <=< f == f -- left identity
f <=< pure == f -- right identity
These are similar to the monoid laws, generalised for multiple types inside the monad.
This sort of structure is called a category in mathematics.
36
Recap Applicative Functors Monads
Relationship to Applicative
All Monad instances give rise to an Applicative instance, because we can define <*>
in terms of >>=.
mf <*> mx = mf >>= \f -> mx >>= \x -> pure (f x)
This implementation is already provided for Monads as the ap function in
Control.Monad.
37
Recap Applicative Functors Monads
Do notation
Working directly with the monad functions can be unpleasant.
As we’ve seen, Haskell has some notation to increase niceness:
do x <- y z becomes y >>= \x -> do z
do x
y
becomes x >>= \_ -> do y
We’ll use this for most of our examples.
38
Recap Applicative Functors Monads
Examples
Example (Dice Rolls)
Roll two 6-sided dice, if the difference is < 2, reroll the second die. Final score is the difference of the two die. What score is most common? Example (Partial Functions) We have a list of student names in a database of type [(ZID, Name)]. Given a list of zID’s, return a Maybe [Name], where Nothing indicates that a zID could not be found. Example (Arbitrary Instances) Define a Tree type and a generator for search trees: searchTrees :: Int -> Int -> Generator Tree
39
Recap Applicative Functors Monads
Examples
Example (Dice Rolls)
Roll two 6-sided dice, if the difference is < 2, reroll the second die. Final score is the difference of the two die. What score is most common? Example (Partial Functions) We have a list of student names in a database of type [(ZID, Name)]. Given a list of zID’s, return a Maybe [Name], where Nothing indicates that a zID could not be found. Example (Arbitrary Instances) Define a Tree type and a generator for search trees: searchTrees :: Int -> Int -> Generator Tree
40
Recap Applicative Functors Monads
Examples
Example (Dice Rolls)
Roll two 6-sided dice, if the difference is < 2, reroll the second die. Final score is the difference of the two die. What score is most common? Example (Partial Functions) We have a list of student names in a database of type [(ZID, Name)]. Given a list of zID’s, return a Maybe [Name], where Nothing indicates that a zID could not be found. Example (Arbitrary Instances) Define a Tree type and a generator for search trees: searchTrees :: Int -> Int -> Generator Tree
41
Recap Applicative Functors Monads
Homework
1 Next programming exercise is out now, due in Friday 12pm of Week 8.
2 This week’s quiz is also up, due in Friday 6pm of Week 8.
42
Recap
Applicative Functors
Monads