The Mantra
Don’t Repeat Yourself
In this lecture we will see advanced ways to abstract code patterns
Outline
- Functors
- A Monad for Error Handling
- Writing apps with monads
- A Monad for Mutable State
Recall: HOF
Recall how we used higher-order functions to abstract code patters
Iterating Through Lists
data List a
= []
| (:) a (List a)
Rendering the Values of a List
-- >>> showList [1, 2, 3]
-- ["1", "2", "3"]
showList :: List Int -> List String
showList [] = []
showList (n:ns) = show n : showList ns
Squaring the values of a list
-- >>> sqrList [1, 2, 3]
-- 1, 4, 9
sqrList :: List Int -> List Int
sqrList [] = []
sqrList (n:ns) = n^2 : sqrList ns
Common Pattern: map over a list
Refactor iteration into mapList
mapList :: (a -> b) -> List a -> List b
mapList f [] = []
mapList f (x:xs) = f x : mapList f xs
Reuse mapList to implement showList and sqrList
showList xs = mapList (\n -> show n) xs
sqrList xs = mapList (\n -> n ^ 2) xs
Iterating Through Trees
data Tree a
= Leaf
| Node a (Tree a) (Tree a)
Rendering the Values of a Tree
-- >>> showTree (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf))
-- (Node "2" (Node "1" Leaf Leaf) (Node "3" Leaf Leaf))
showTree :: Tree Int -> Tree String
showTree Leaf = ???
showTree (Node v l r) = ???
Squaring the values of a Tree
-- >>> sqrTree (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf))
-- (Node 4 (Node 1 Leaf Leaf) (Node 9 Leaf Leaf))
sqrTree :: Tree Int -> Tree Int
sqrTree Leaf = ???
sqrTree (Node v l r) = ???
QUIZ: Mapping over a Tree
If we refactor iteration into mapTree,
what should its type be?
mapTree :: ???
showTree t = mapTree show t
sqrTree t = mapTree (^ 2) t(A) (Int -> Int) -> Tree Int -> Tree Int
(B) (Int -> String) -> Tree Int -> Tree String
(C) (Int -> a) -> Tree Int -> Tree a
(D) (a -> a) -> Tree a -> Tree a
(E) (a -> b) -> Tree a -> Tree b
Mapping over Trees
Let’s write mapTree:
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f Leaf = ???
mapTree f (Node v l r) = ???
Abstracting across Datatypes
Wait, this looks familiar…
mapList :: (a -> b) -> List a -> List b -- List
mapTree :: (a -> b) -> Tree a -> Tree b -- TreeCan we provide a generic map function that works for List, Tree, and other datatypes?
A Class for Mapping
Not all datatypes support mapping over, only some of them do.
So let’s make a typeclass for it!
class Functor t where
fmap :: ???
QUIZ
What type should we give to fmap?
class Functor t where
fmap :: ???(A) (a -> b) -> t -> t
(B) (a -> b) -> [a] -> [b]
(C) (a -> b) -> t a -> t b
(D) (a -> b) -> Tree a -> Tree b
(E) None of the above
class Functor t where
fmap :: (a -> b) -> t a -> t bUnlike other typeclasses we have seen before, here t:
- does not stand for a type
- but for a type constructor
- it is called a higher-kinded type variable
Reuse Iteration Across Types
instance Functor [] where
fmap = mapList
instance Functor Tree where
fmap = mapTreeAnd now we can do
-- >>> fmap show [1,2,3]
-- ["1", "2", "3"]
-- >>> fmap (^2) (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf))
-- (Node 4 (Node 1 Leaf Leaf) (Node 9 Leaf Leaf))
EXERCISE: the Maybe Functor
Write a Functor instance for Maybe:
data Maybe a = Nothing | Just a
instance Functor Maybe where
fmap = ???When you’re done you should see
-- >>> fmap (^ 2) (Just 3)
Just 9
-- >>> fmap (^ 2) Nothing
Nothing
Outline
- Functors [done]
- A Monad for Error Handling
- Writing apps with monads
- A Monad for Mutable State
Next: A Class for Sequencing
Consider a simplified Expr datatype
data Expr
= Num Int
| Plus Expr Expr
| Div Expr Expr
deriving (Show)
eval :: Expr -> Int
eval (Num n) = n
eval (Plus e1 e2) = eval e1 + eval e2
eval (Div e1 e2) = eval e1 `div` eval e2
-- >>> eval (Div (Num 6) (Num 2))
-- 3
But what is the result of
-- >>> eval (Div (Num 6) (Num 0))
-- *** Exception: divide by zero
My interpreter crashes!
- What if I’m implementing GHCi?
- I don’t want GHCi to crash every time you enter
div 5 0 - I want it to process the error and move on with its life
How can we achieve this behavior?
Error Handling: Take One
Let’s introduce a new type for evaluation results:
data Result a
= Error String
| Value aOur eval will now return Result Int instead of Int
- If a sub-expression had a divide by zero, return
Error "..." - If all sub-expressions were safe, then return the actual
Value v
eval :: Expr -> Result Int
eval (Num n) = ???
eval (Plus e1 e2) = ???
eval (Div e1 e2) = ???
eval :: Expr -> Result Int
eval (Num n) = Value n
eval (Plus e1 e2) =
case eval e1 of
Error err1 -> Error err1
Value v1 -> case eval e2 of
Error err2 -> Error err2
Value v1 -> Value (v1 + v2)
eval (Div e1 e2) =
case eval e1 of
Error err1 -> Error err1
Value v1 -> case eval e2 of
Error err2 -> Error err2
Value v2 -> if v2 == 0
then Error ("DBZ: " ++ show e2)
else Value (v1 `div` v2)
The good news: interpreter doesn’t crash, just returns Error msg:
λ> eval (Div (Num 6) (Num 2))
Value 3
λ> eval (Div (Num 6) (Num 0))
Error "DBZ: Num 0"
λ> eval (Div (Num 6) (Plus (Num 2) (Num (-2))))
Error "DBZ: Plus (Num 2) (Num (-2))"
The bad news: the code is super duper gross
Lets spot a Pattern
The code is gross because we have these cascading blocks
case eval e1 of
Error err1 -> Error err1
Value v1 -> case eval e2 of
Error err2 -> Error err2
Value v2 -> Value (v1 + v2)
But these blocks have a common pattern:
- First do
eval eand get resultres - If
resis anError, just return that error - If
resis aValue vthen do further processing onv
case res of
Error err -> Error err
Value v -> process v -- do more stuff with v
Lets bottle that common structure in a function >>= (pronounced bind):
(>>=) :: Result a -> (a -> Result b) -> Result b
(Error err) >>= _ = Error err
(Value v) >>= process = process v
Notice the >>= takes two inputs:
Result a: result of the first evaluationa -> Result b: in case the first evaluation produced a value, what to do next with that value
QUIZ: Bind 1
With >>= defined as before:
(>>=) :: Result a -> (a -> Result b) -> Result b
(Error msg) >>= _ = Error msg
(Value v) >>= process = process vWhat does the following evaluate to?
λ> eval (Num 5) >>= \v -> Value (v + 1)(A) Type Error
(B) 5
(C) Value 5
(D) Value 6
(E) Error msg
QUIZ: Bind 2
With >>= defined as before:
(>>=) :: Result a -> (a -> Result b) -> Result b
(Error msg) >>= _ = Error msg
(Value v) >>= process = process vWhat does the following evaluate to?
λ> Error "nope" >>= \v -> Value (v + 1)(A) Type Error
(B) 5
(C) Value 5
(D) Value 6
(E) Error "nope"
A Cleaned up Evaluator
The magic bottle lets us clean up our eval:
eval :: Expr -> Result Int
eval (Num n) = Value n
eval (Plus e1 e2) = eval e1 >>= \v1 ->
eval e2 >>= \v2 ->
Value (v1 + v2)
eval (Div e1 e2) = eval e1 >>= \v1 ->
eval e2 >>= \v2 ->
if v2 == 0
then Error ("DBZ: " ++ show e2)
else Value (v1 `div` v2)The gross pattern matching is all hidden inside >>=!
NOTE: It is crucial that you understand what the code above
is doing, and why it is actually just a “shorter” version of the
(gross) nested-case-of eval.
A Class for bind
Like fmap or show or ==,
the >>= operator turns out to be useful across many types
(not just Result)
Let’s create a typeclass for it!
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b -- bind
return :: a -> m a -- return
return tells you how to wrap an a value in the monad
- Useful for writing code that works across multiple monads
Monad instance for Result
Let’s make Result an instance of Monad!
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
instance Monad Result where
(>>=) :: Result a -> (a -> Result b) -> Result b
(Error msg) >>= _ = Error msg
(Value v) >>= process = process v
return :: a -> Result a
return v = ??? -- How do we make a `Result a` from an `a`?
instance Monad Result where
(>>=) :: Result a -> (a -> Result b) -> Result b
(Error msg) >>= _ = Error msg
(Value v) >>= process = process v
return :: a -> Result a
return v = Value v
Syntactic Sugar
In fact >>= is so useful there is special syntax for it!
- It’s called the
donotation
Instead of writing
e1 >>= \v1 ->
e2 >>= \v2 ->
e3 >>= \v3 ->
eyou can write
do v1 <- e1
v2 <- e2
v3 <- e3
e
Thus, we can further simplify our eval to:
eval :: Expr -> Result Int
eval (Num n) = return n
eval (Plus e1 e2) = do v1 <- eval e1
v2 <- eval e2
return (v1 + v2)
eval (Div e1 e2) = do v1 <- eval e1
v2 <- eval e2
if v2 == 0
then Error ("DBZ: " ++ show e2)
else return (v1 `div` v2)
The Either Monad
Error handling is a very common task!
Instead of defining your own type Result,
you can use Either from the Haskell standard library:
data Either a b =
Left a -- something has gone wrong
| Right b -- everything has gone RIGHTEither is already an instance of Monad,
so no need to define your own >>=!
Now we can simply define
type Result a = Either String aand the eval above will just work out of the box!
Outline
- Functors [done]
- A Monad for Error Handling [done]
- Writing apps with monads
- A Monad for Mutable State
Writing Applications
In most programming classes, they start with a “Hello world!” program.
In 130, we will end with it.
Why is it hard to write a program that prints “Hello world!” in Haskell?
Haskell is pure
Haskell programs don’t do things!
A program is an expression that evaluates to a value (and nothing else happens)
A function of type
Int -> Intcomputes a single integer output from a single integer input and does nothing elseMoreover, it always returns the same output given the same input (referential transparency)
Specifically, evaluation must not have any side effects
change a global variable or
print to screen or
read a file or
send an email or
launch a missile.
But… how to write “Hello, world!”
But, we want to …
- print to screen
- read a file
- send an email
A language that only lets you write factorial and fibonacci is … not very useful!
Thankfully, you can do all the above via a very clever idea: Recipe
Recipes
This analogy is due to Joachim Brietner
Haskell has a special type called IO – which you can think of as Recipe
type Recipe a = IO a
A value of type Recipe a is
a description of a computation
that when executed (possibly) performs side effects and
produces a value of type
a
Recipes are Pure
Baking a cake can have side effects:
make your oven hot
make your floor dirty
set off your fire alarm
But: merely writing down a cake recipe does not cause any side effects
Executing Recipes
When executing a program, Haskell looks for a special value:
main :: Recipe ()This is a recipe for everything a program should do
- that returns a unit
() - i.e. does not return any useful value
The value of main is handed to the runtime system and executed
The Haskell runtime is a master chef who is the only one allowed to produce effects!
Importantly:
A function of type
Int -> Intstill computes a single integer output from a single integer input and does nothing elseA function of type
Int -> Recipe Intcomputes anInt-recipe from a single integer input and does nothing elseOnly if I hand this recipe to
mainwill any effects be produced
Writing Apps
To write an app in Haskell, you define your own recipe main!
Hello World
main :: Recipe ()
main = putStrLn "Hello, world!"
putStrLn :: String -> Recipe ()The function putStrLn
- takes as input a
String - returns a
Recipe ()for printing things to screen
… and we can compile and run it
$ ghc hello.hs
$ ./hello
Hello, world!
This was a one-step recipe
Most interesting recipes
- have multiple steps
- pass intermediate results between steps
How do I write those?
Multi-Step Recipes
Next, lets write a program that
- Asks for the user’s
nameusing
getLine :: Recipe String- Prints out a greeting with that
nameusing
putStrLn :: String -> Recipe ()Problem: How to pass the output of first recipe into the second recipe?
QUIZ: Multi-Step Recipes
If I had a function andThen for sequencing recipes, e.g.:
getLine :: Recipe String
putStrLn :: String -> Recipe ()
main :: Recipe ()
main = getLine `andThen` putStrLnWhat should the type of andThen be?
(A) String -> () -> ()
(B) Recipe String -> Recipe () -> Recipe ()
(C) Recipe String -> (String -> Recipe ()) -> Recipe ()
(D) Recipe a -> (a -> Recipe a ) -> Recipe a
(E) Recipe a -> (a -> Recipe b ) -> Recipe b
Recipes are Monads
Wait a second, the signature:
andThen :: Recipe a -> (a -> Recipe b) -> Recipe blooks just like:
(>>=) :: m a -> (a -> m b) -> m b
In fact, in the standard library Recipe is an instance of Monad!
So we can put this together with putStrLn to get:
main :: Recipe ()
main = getLine >>= \name -> putStrLn ("Hello, " ++ name ++ "!")or, using do notation the above becomes
main :: Recipe ()
main = do name <- getLine
putStrLn ("Hello, " ++ name ++ "!")
EXERCISE
Modify the above code so that the program repeatedly asks for the users’s name until they provide a non-empty string.
When you are done you should get the following behavior
$ ghc hello.hs
$ ./hello
What is your name?
# user hits return
What is your name?
# user hits return
What is your name?
# user hits return
What is your name?
Nadia # user enters
Hello, Nadia!
Recipes with Results
Let’s write a function that asks the user maximum n times,
and if they fail to provide a non-empty string, it returns a default value d:
main :: Recipe ()
main = do name <- askMany 3 "dummy"
putStrLn $ printf "Hello %s!" name
askMany :: Int -> String -> Recipe String
askMany = ???
To return a result from a recipe, use the return function of Monad!
askMany :: Int -> String -> Recipe String
askMany 0 d = return d
askMany n d = do putStrLn "What is your name?"
name <- getLine
if null name
then askMany (n-1) d
else return name
Outline
- Functors [done]
- A Monad for Error Handling [done]
- Writing apps with monads [done]
- A Monad for Mutable State
Expressions with a Counter
Consider implementing expressions with a counter:
data Expr
= Num Int
| Plus Expr Expr
| Next -- counter value
deriving (Show)Behavior we want:
evalis given the initial counter value- every time we evaluate
Next(within the call toeval), the value of the counter increases:
-- 0
λ> eval 0 Next
0
-- 0 1
λ> eval 0 (Plus Next Next)
1
-- ? ? ?
λ> eval 0 (Plus Next (Plus Next Next))
???
How should we implement eval?
eval (Num n) cnt = ???
eval Next cnt = ???
eval (Plus e1 e2) cnt = ???
QUIZ: State: Take 1
If we implement eval like this:
eval (Num n) cnt = n
eval Next cnt = cnt
eval (Plus e1 e2) cnt = eval e1 cnt + eval e2 cntWhat would be the result of the following?
λ> eval (Plus Next Next) 0(A) Type error
(B) 0
(C) 1
(D) 2
It’s going to be 0 because we never increment the counter!
- We need to increment it every time we do
eval Next - So
evalneeds to return the new counter
Evaluating Expressions with Counter
type Cnt = Int
eval :: Expr -> Cnt -> (Cnt, Int)
eval (Num n) cnt = (cnt, n)
eval Next cnt = (cnt + 1, cnt)
eval (Plus e1 e2) cnt = let (cnt1, v1) = eval e1 cnt
in
let (cnt2, v2) = eval e2 cnt1
in
(cnt2, v1 + v2)
topEval :: Expr -> Int
topEval e = snd (eval e 0)
The good news: we get the right result:
λ> topEval (Plus Next Next)
1
λ> topEval (Plus Next (Plus Next Next))
3
The bad news: the code is super duper gross.
The Plus case has to “thread” the counter through the recursive calls:
let (cnt1, v1) = eval e1 cnt
in
let (cnt2, v2) = eval e2 cnt1
in
(cnt2, v1 + v2)- Easy to make a mistake, e.g. pass
cntinstead ofcnt1into the secondeval! - The logic of addition is obscured by all the counter-passing
So unfair, since Plus doesn’t even care about the counter!
Is it too much to ask that eval looks like this?
eval (Num n) = return n
eval (Plus e1 e2) = do v1 <- eval e1
v2 <- eval e2
return (v1 + v2)
... - Cases that don’t care about the counter (
Num,Plus), don’t even have to mention it! - The counter is somehow threaded through automatically behind the scenes
- Looks just like in the error handing evaluator
Lets spot a Pattern
let (cnt1, v1) = eval e1 cnt
in
let (cnt2, v2) = eval e2 cnt1
in
(cnt2, v1 + v2)These blocks have a common pattern:
- Perform first step (
eval e) using initial countercnt - Get a result
(cnt', v) - Then do further processing on
vusing the new countercnt'
let (cnt', v) = step cnt
in process v cnt' -- do things with v and cnt'
Can we bottle this common pattern as a >>=?
(>>=) step process cnt = let (cnt', v) = step cnt
in process v cnt'
But what is the type of this >>=?
(>>=) :: (Cnt -> (Cnt, a))
-> (a -> Cnt -> (Cnt, b))
-> Cnt
-> (Cnt, b)
(>>=) step process cnt = let (cnt', v) = step cnt
in process v cnt'Wait, but this type signature looks nothing like the Monad’s bind!
(>>=) :: m a -> (a -> m b) -> m b
… or does it???
QUIZ: Type of bind for Counting
What should I replace m t with to make the general type of monadic bind:
(>>=) :: m a -> (a -> m b) -> m blook like the type of bind we just defined:
(>>=) :: (Cnt -> (Cnt, a))
-> (a -> Cnt -> (Cnt, b))
-> Cnt
-> (Cnt, b)(A) It’s impossible
(B) m t = Result t
(C) m t = (Cnt, t)
(D) m t = Cnt -> (Cnt , t)
(E) m t = t -> (Cnt , t)
type Counting a = Cnt -> (Cnt, a)
(>>=) :: Counting a
-> (a -> Counting b)
-> Counting b
(>>=) step process = \cnt -> let (cnt', v) = step cnt
in process v cnt'Mind blown.
QUIZ: Return for Counting
How should we define return for Counting?
type Counting a = Cnt -> (Cnt, a)
-- | Represent value x as a counting computation,
-- don't actually touch the counter
return :: a -> Counting a
return x = ???(A) x
(B) (0, x)
(C) \c -> (0, x)
(D) \c -> (c, x)
(E) \c -> (c + 1, x)
Cleaned-up evaluator
eval :: Expr -> Counting Int
eval (Num n) = return n
eval (Plus e1 e2) = eval e1 >>= \v1 ->
eval e2 >>= \v2 ->
return (v1 + v2)
eval Next = \cnt -> (cnt + 1, cnt)Hooray! We rid the poor Num and Plus from the pesky counters!
The Next case has to deal with counters
- but can we somehow hide the representation of
Counting a? - and make it look more like we just have mutable state that we can
getandput? - i.e. write:
eval Next = get >>= \c ->
put (c + 1) >>= \_ ->
return c
EXERCISE: get and put
Implement functions get and put, which would allow us to implement Next as
eval Next = get >>= \c ->
put (c + 1) >>= \_ ->
return c-- | Computation whose return value is the current counter value
get :: Counting Cnt
get = ???
-- | Computation that updates the counter value to `newCnt`
put :: Cnt -> Counting ()
put newCnt = ???
-- | Computation whose return value is the current counter value
get :: Counting Cnt
get = \cnt -> (cnt, cnt)
-- | Computation that updates the counter value to `newCnt`
put :: Cnt -> Counting ()
put newCnt = \_ -> (newCnt, ())
Monad instance for Counting
Let’s make Counting an instance of Monad!
- To do that, we need to make it a new datatype
data Counting a = C (Cnt -> (Cnt, a))
instance Monad Counting where
(>>=) :: Counting a -> (a -> Counting b) -> Counting b
(>>=) (C step) process = C final
where
final cnt = let
(cnt', v) = step cnt
C nextStep = process v
in nextStep cnt'
return :: a -> Result a
return v = C (\cnt -> (cnt, v))We also need to update get and put slightly:
-- | Computation whose return value is the current counter value
get :: Counting Cnt
get = C (\cnt -> (cnt, cnt))
-- | Computation that updates the counter value to `newCnt`
put :: Cnt -> Counting ()
put newCnt = C (\_ -> (newCnt, ()))
Cleaned-up Evaluator
Now we can use the do notation!
eval :: Expr -> Counting Int
eval (Num n) = return n
eval (Plus e1 e2) = do v1 <- eval e1
v2 <- eval e2
return (v1 + v2)
eval Next = do
cnt <- get
_ <- put (cnt + 1)
return (cnt)
The State Monad
Threading state is a very common task!
Instead of defining your own type Counting a,
you can use State s a from the Haskell standard library:
data State s a = State (s -> (s, a))State is already an instance of Monad,
so no need to define your own >>=!
Now we can simply define
type Counting a = State Cnt aand the eval above will just work out of the box!
Monads are Amazing
This code stays the same:
eval :: Expr -> Interpreter Int
eval (Num n) = return n
eval (Plus e1 e2) = do v1 <- eval e1
v2 <- eval e2
return (v1 + v2)
... We can change the type Interpreter to implement different effects:
type Interpreter a = Except String aif we want to handle errorstype Interpreter a = State Int aif we want to have a countertype Interpreter a = ExceptT String (State Int) aif we want bothtype Interpreter a = [a]if we want to return multiple results- …
Monads let us decouple two things:
- Application logic: the sequence of actions (implemented in
eval) - Effects: how actions are sequenced (implemented in
>>=)
Monads are Influential
Monads have had a revolutionary influence in PL, well beyond Haskell, some recent examples
Big data pipelines e.g. LinQ and TensorFlow
Thats all, folks!