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 [] = []
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
- 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
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]
- 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:
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!
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 as?
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
(>>=) = listBindWhat 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
(>>=) = listBindWhat 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 xsYou 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 [] _ = []
listBind (x:xs) f = f x ++ listBind xs for, without recursion:
listBind xs f = concat (map f xs)there’s already a library function for this!
listBind xs f = concatMap f xs
For example:
f = \x -> [x, x+1]
[] >>= 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?
quiz = do x <- ["cat", "dog"]
y <- [0, 1]
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!
quiz = do x <- ["cat", "dog"]
y <- [0, 1]
return (x, y)is equivalent to:
quiz = [ (x, y) | x <- ["cat", "dog"], y <- [0, 1] ]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?
quiz = do x <- ["cat", "dog"]
y <- [0, 1]
[]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:
coPrimes n = take n [(i,j) | i <- [2..],
j <- [2..i],
gcd i j == 1]Rewrite this using the List Monad
- assume that the
gcdfunction is already defined
coPrimes n = take n allCoPrimes
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, y) | x <- ["cat", "dog"], y <- [0, 1] ]
>>> [("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]
bits 0 = return ""
bits n = do
bit <- ['0', '1']
rest <- bits (n - 1)
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:
bits n = mapM (\_ -> ['0', '1']) [1..n]
-- or:
bits n = replicateM n ['0', '1']
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 stateList 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
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 = Either String aif we want to handle errorstype Interpreter a = State Int aif 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) aif 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 -> 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 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 -> Intstill 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 anIntand a newWorldfrom anIntand 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 ()
main = putStrLn "Hello, world!"
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
nameusing
getLine :: IO String- Prints out a greeting with that
nameusing
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 ()
main = getLine `andThen` putStrLnWhat 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 blooks just like:
(>>=) :: m a -> (a -> m b) -> m b
So we can put this together with putStrLn to get:
main :: IO ()
main = getLine >>= \name -> putStrLn ("Hello, " ++ name ++ "!")or, using do notation the above becomes
main :: IO ()
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!
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 ()
main = do name <- askMany 3 "dummy"
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
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
Thats all, folks!