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
- A Monad for Mutable State
- a monad for Non-Determinism
- Writing apps with monads
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 [] :ns) = n^2 : sqrList ns sqrList (n
Common Pattern: map
over a list
Refactor iteration into mapList
mapList :: (a -> b) -> List a -> List b
= []
mapList f [] :xs) = f x : mapList f xs mapList f (x
Reuse mapList
to implement showList
and sqrList
showList xs = mapList (\n -> show n) xs
= mapList (\n -> n ^ 2) xs sqrList 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
Leaf = ???
showTree Node v l r) = ??? showTree (
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
Leaf = ???
sqrTree Node v l r) = ??? sqrTree (
QUIZ: Mapping over a Tree
If we refactor iteration into mapTree
,
what should its type be?
mapTree :: ???
= mapTree show t
showTree t = mapTree (^ 2) t sqrTree 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
Leaf = ???
mapTree f Node v l r) = ??? mapTree f (
Abstracting across Datatypes
Wait, this looks familiar…
mapList :: (a -> b) -> List a -> List b -- List
mapTree :: (a -> b) -> Tree a -> Tree b -- Tree
Can 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 b
Unlike 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 = mapTree
And 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
- A Monad for Mutable State
- a monad for Non-Determinism
- Writing apps with monads
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
Num n) = n
eval (Plus e1 e2) = eval e1 + eval e2
eval (Div e1 e2) = eval e1 `div` eval e2
eval (
-- >>> 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 a
Our 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
Num n) = ???
eval (Plus e1 e2) = ???
eval (Div e1 e2) = ??? eval (
eval :: Expr -> Result Int
Num n) = Value n
eval (Plus e1 e2) =
eval (case eval e1 of
Error err1 -> Error err1
Value v1 -> case eval e2 of
Error err2 -> Error err2
Value v1 -> Value (v1 + v2)
Div e1 e2) =
eval (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 e
and get resultres
- If
res
is anError
, just return that error - If
res
is aValue v
then 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 v (
What 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 v (
What 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
Num n) = Value n
eval (Plus e1 e2) = eval e1 >>= \v1 ->
eval (>>= \v2 ->
eval e2 Value (v1 + v2)
Div e1 e2) = eval e1 >>= \v1 ->
eval (>>= \v2 ->
eval e2 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
do
notation
Instead of writing
>>= \v1 ->
e1 >>= \v2 ->
e2 >>= \v3 ->
e3 e
you can write
do v1 <- e1
<- e2
v2 <- e3
v3 e
Thus, we can further simplify our eval
to:
eval :: Expr -> Result Int
Num n) = return n
eval (Plus e1 e2) = do v1 <- eval e1
eval (<- eval e2
v2 return (v1 + v2)
Div e1 e2) = do v1 <- eval e1
eval (<- eval e2
v2 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 RIGHT
Either
is already an instance of Monad
,
so no need to define your own >>=
!
Now we can simply define
type Result a = Either String a
and the eval
above will just work out of the box!
Outline
- Functors [done]
- A Monad for Error Handling [done]
- A Monad for Mutable State
- a monad for Non-Determinism
- Writing apps with monads
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:
eval
is 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
?
Num n) cnt = ???
eval (Next cnt = ???
eval Plus e1 e2) cnt = ??? eval (
QUIZ: State: Take 1
If we implement eval
like this:
Num n) cnt = n
eval (Next cnt = cnt
eval Plus e1 e2) cnt = eval e1 cnt + eval e2 cnt eval (
What 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
eval
needs to return the new counter
Evaluating Expressions with Counter
type Cnt = Int
eval :: Expr -> Cnt -> (Cnt, Int)
Num n) cnt = (cnt, n)
eval (Next cnt = (cnt + 1, cnt)
eval Plus e1 e2) cnt = let (cnt1, v1) = eval e1 cnt
eval (in
let (cnt2, v2) = eval e2 cnt1
in
+ v2)
(cnt2, v1
topEval :: Expr -> Int
= snd (eval e 0) topEval e
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
+ v2) (cnt2, v1
- Easy to make a mistake, e.g. pass
cnt
instead ofcnt1
into 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?
Num n) = return n
eval (Plus e1 e2) = do v1 <- eval e1
eval (<- eval e2
v2 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
+ v2) (cnt2, v1
These blocks have a common pattern:
- Perform first step (
eval e
) using initial countercnt
- Get a result
(cnt', v)
- Then do further processing on
v
using 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 b
look 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
Num n) = return n
eval (Plus e1 e2) = eval e1 >>= \v1 ->
eval (>>= \v2 ->
eval e2 return (v1 + v2)
Next = \cnt -> (cnt + 1, cnt) eval
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
get
andput
? - i.e. write:
Next = get >>= \c ->
eval + 1) >>= \_ ->
put (c return c
EXERCISE: get and put
Implement functions get
and put
, which would allow us to implement Next
as
Next = get >>= \c ->
eval + 1) >>= \_ ->
put (c 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
= \cnt -> (cnt, cnt)
get
-- | Computation that updates the counter value to `newCnt`
put :: Cnt -> Counting ()
= \_ -> (newCnt, ()) put 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
= let
final cnt = step cnt
(cnt', v) 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
= C (\cnt -> (cnt, cnt))
get
-- | Computation that updates the counter value to `newCnt`
put :: Cnt -> Counting ()
= C (\_ -> (newCnt, ())) put newCnt
Cleaned-up Evaluator
Now we can use the do
notation!
eval :: Expr -> Counting Int
Num n) = return n
eval (Plus e1 e2) = do v1 <- eval e1
eval (<- eval e2
v2 return (v1 + v2)
Next = do
eval <- get
cnt <- 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 a
and the eval
above will just work out of the box!
Outline
- Functors [done]
- A Monad for Error Handling [done]
- A Monad for Mutable State [done]
- A monad for Non-Determinism
- Writing apps with monads
Recall: Computations that may fail
-- | Result sans the error message
data Result a = Value a | Error
instance Monad Result where
Error >>= _ = Error
Value v) >>= process = process v
(
return v = Value v
A computation of type Result a
returns zero or one a
Can we generalize this to computations that return zero or more a
s?
Replacing Failure by a List of Successes
Instead of Result a
let’s return [a]
!
- Instead of
Error
, return the empty list[]
- Instead of
Value v
, return the singleton list[v]
… can we do something fun with many elements?
QUIZ
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
instance Monad [] where
return = listReturn
>>=) = listBind (
What must the type of listReturn
be ?
A. [a]
B. a -> a
C. a -> [a]
D. [a] -> a
E. [a] -> [a]
Return for Lists
Let’s implement return
for lists?
listReturn :: a -> [a]
= ??? listReturn x
What’s the only sensible implementation?
QUIZ
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
instance Monad [] where
return = listReturn
>>=) = listBind (
What must the type of listBind
be?
A. [a] -> [b] -> [b]
B. [a] -> (a -> b) -> [b]
C. [a] -> (a -> [b]) -> b
D. [a] -> (a -> [b]) -> [b]
E. [a] -> [b]
EXERCISE: Bind for Lists
What is the most sensible implementation of listBind
?
listBind :: [a] -> (a -> [b]) -> [b]
= ??? listBind
HINT: What does “sensible” mean?
Recall how we discussed that the implementation of map
is the only sensible one for its type:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
You could of course implement:
map f xs = []
- or
map f (x:xs) = [f x]
but this is silly because it doesn’t use all the elements of the input list!
Bind for Lists
listBind :: [a] -> (a -> [b]) -> [b]
= []
listBind [] _ :xs) f = f x ++ listBind xs f listBind (x
or, without recursion:
= concat (map f xs) listBind xs f
there’s already a library function for this!
= concatMap f xs listBind xs f
For example:
= \x -> [x, x+1]
f
>>= f ==> []
[]
1] >>= f ==> f 1 ==> [1,2]
[
1,2] >>= f ==> f 1 ++ f 2 ==> [1,2,2,3]
[
1,2,3] >>= f ==> f 1 ++ f 2 ++ f3 ==> [1,2,2,3,3,4] [
QUIZ
What does the following program evaluate to?
= do x <- ["cat", "dog"]
quiz <- [0, 1]
y return (x, y)
A. []
B. [("cat", 0)]
C. ["cat", "dog", 0, 1]
D. ["cat", 0, "dog", 1]
E. [("cat", 0), ("cat", 1), ("dog", 0), ("dog", 1)]
Does this behavior ring a bell?
Whoa, behaves like a list comprehension!
= do x <- ["cat", "dog"]
quiz <- [0, 1]
y return (x, y)
is equivalent to:
= [ (x, y) | x <- ["cat", "dog"], y <- [0, 1] ] quiz
List comprehensions are just a syntactic sugar for the List Monad!
For those who are not comfortable with list comprehensions, think nested for-loops
Lets work it out.
do {x <- ["cat", "dog"]; y <- [0, 1]; return (x, y)}
== ["cat", "dog"] >>= (\x -> [0, 1] >>= (\y -> return (x, y)))
Now lets break up the evaluation
0, 1] >>= (\y -> [(x, y)])
[
==> [(x, 0)] ++ [(x, 1)]
==> [(x, 0), (x, 1)]
So
"cat", "dog"] >>= (\x -> [(x, 0), (x, 1)])
[
==> [("cat", 0), ("cat", 1)] ++ [("dog", 0), ("dog", 1)]
==> [("cat", 0), ("cat", 1), ("dog", 0), ("dog", 1)]
QUIZ
What does the following evaluate to?
= do x <- ["cat", "dog"]
quiz <- [0, 1]
y []
A. []
B. [[]]
C. [()]
D. [("cat", 0)]
E. [("cat", 0), ("cat", 1), ("dog", 0), ("dog", 1)]
EXERCISE: Co-primes
Recall finding co-primes using list comprehensions:
-- first n pairs of co-primes:
= take n [(i,j) | i <- [2..],
coPrimes n <- [2..i],
j gcd i j == 1]
Rewrite this using the List Monad
- assume that the
gcd
function is already defined
= take n allCoPrimes
coPrimes n where
= ??? allCoPrimes
Beyond List Comprehensions
List comprehensions / nested for-loops = cartesian product of a fixed number of lists
For example:
-- cartesian product of 2 lists
| x <- ["cat", "dog"], y <- [0, 1] ]
[ (x, y) >>> [("cat", 0), ("cat", 1), ("dog", 0), ("dog", 1)]
What if we want to do the same thing for an arbitrary number of lists?
- this gets REALLY HAIRY in imperative languages
- but ridiculously easy in Haskell
Example: All Bit Strings of Length n
Let’s implement a function:
bits :: Int -> [String]
Such that
>>> bits 0
""]
[>>> bits 1
"0", "1"]
[>>> bits 2
"00", "01", "10", "11"]
[
>>> bits 3
"000", "001", "010", "011", "100", "101", "110", "111"] [
bits :: Int -> [String]
0 = return ""
bits = do
bits n <- ['0', '1']
bit <- bits (n - 1)
rest return (bit:rest)
Useful Library Functions
We can often eliminate recursion from monadic computations using library functions:
-- From Control.Monad:
-- | Map a monadic computation over a list, get list of results:
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
-- | Repeat the same monadic computation n times, get list of results:
replicateM :: Monad m => Int -> m a -> m [a]
-- For example:
= mapM (\_ -> ['0', '1']) [1..n]
bits n
-- or:
= replicateM n ['0', '1'] bits n
Summary
Three monads and their meaning of sequencing:
Result
/ Either
monad for error handling:
- if step 1 fails, then stop
- if step 1 succeeds, then do step 2
State
monad for mutable state:
- do step 1 to get a new state
- do step 2 in that new state
List
monad for non-determinism / enumeration:
- do step 1 to get a list of intermediate results
- for each intermediate result, do step 2
Monads are Amazing
This code stays the same:
eval :: Expr -> Interpreter Int
Num n) = return n
eval (Plus e1 e2) = do v1 <- eval e1
eval (<- eval e2
v2 return (v1 + v2)
...
We can change the type Interpreter
to implement different effects:
type Interpreter a = Either String a
if we want to handle errorstype Interpreter a = State Int a
if we want to have a countertype Interpreter a = [a]
if we want to return multiple results- …
You can also combine effects with something called monad transformers!
type Interpreter a = ExceptT String (State Int) a
if we want to have both errors and a counter!
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
Outline
- Functors [done]
- A Monad for Error Handling [done]
- A Monad for Mutable State [done]
- A monad for Non-Determinism [done]
- Writing apps with monads
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 -> Int
computes 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 using a special monad called IO
!
The IO Monad
Just like our other monads allowed computations to have different effects:
- errors
- mutable state
- non-determinism
IO
allows the effect of communicating with the outside world
- you can think of it as “state on steroids”, where the state type is
World
!
Importantly, referential transparency is preserved:
A function of type
Int -> Int
still computes a single integer output from a single integer input and does nothing elseA function of type
Int -> IO Int
, on the other hand, computes anInt
and a newWorld
from anInt
and the oldWorld
(so it has the right to read a file, print to screen, or launch a missile)
Writing Apps
When executing a standalone program, Haskell looks for a special value:
main :: IO ()
This is a computation that
- returns a unit
()
(i.e. does not return any useful value) - potentially communicates with the outside world
To write an app in Haskell, you define your own main
Hello World
main :: IO ()
= putStrLn "Hello, world!" main
putStrLn :: String -> IO ()
The function putStrLn
- takes as input a
String
- returns a
IO ()
for printing things to screen
… and we can compile and run it
$ ghc hello.hs
$ ./hello
Hello, world!
This was a one-step app
Most interesting apps
- have multiple steps
- pass intermediate results between steps
How do I write those?
Multi-Step Apps
Next, lets write a program that
- Asks for the user’s
name
using
getLine :: IO String
- Prints out a greeting with that
name
using
putStrLn :: String -> IO ()
Problem: How to pass the output of first step into the second step?
QUIZ: Multi-Step Apps
If I had a function andThen
for sequencing app steps, e.g.:
getLine :: IO String
putStrLn :: String -> IO ()
main :: IO ()
= getLine `andThen` putStrLn main
What should the type of andThen
be?
(A) String -> () -> ()
(B) IO String -> IO () -> IO ()
(C) IO String -> (String -> IO ()) -> IO ()
(D) IO a -> (a -> IO a) -> IO a
(E) IO a -> (a -> IO b) -> IO b
Multi-Step Apps via bind
Wait a second, the signature:
andThen :: IO a -> (a -> IO b) -> IO b
looks just like:
(>>=) :: m a -> (a -> m b) -> m b
So we can put this together with putStrLn
to get:
main :: IO ()
= getLine >>= \name -> putStrLn ("Hello, " ++ name ++ "!") main
or, using do
notation the above becomes
main :: IO ()
= do name <- getLine
main 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!
Steps 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 :: IO ()
= do name <- askMany 3 "dummy"
main putStrLn $ printf "Hello %s!" name
askMany :: Int -> String -> IO String
= ??? askMany
To return a result from a step, use the return
function of Monad
!
askMany :: Int -> String -> IO String
0 d = return d
askMany = do putStrLn "What is your name?"
askMany n d <- getLine
name if null name
then askMany (n-1) d
else return name
Thats all, folks!