COMP90045 Programming Language Implementation
Haskell with Monads
Harald Søndergaard Lecture 5
Semester 1, 2019
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 1 / 23
Monadic Programming
Monads allow dys-functional language features like sequencing, dereferencing, destructive assignment and input/output to be expressed entirely within a pure functional language.
The resulting programs look imperative but retain all the nice properties of functional programs.
Monads are first-class objects, and the type system can ensure that they are used correctly.
An example of monadic programming is Haskell’s way of dealing with input/output.
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 2 / 23
Monadic Input/Output
The type of output actions is IO () (ignore the () for now.)
IO () is an instance of a monad. A term a :: IO () denotes an
action.
> putChar :: Char -> IO ()
The expression putChar ’!’ denotes the action of printing an
exclamation mark.
> putStr :: String -> IO () >print ::Showa=>a->IO()
Those are defined in the Prelude.
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 3 / 23
Monadic Input/Output
Also defined in the Prelude is the function (>>) for combining actions. (In fact (>>) and return come from the Monad type class.)
> (>>) :: IO () -> IO () -> IO () > puts :: String -> IO ()
> puts [] = return ()
> puts (c:s) = putChar c >> puts s
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 4 / 23
The Variable main
So far we only have expressions denoting actions. How does one actually get actions to happen?
> main = print ([(n,2^n) | n <- [0..19]]) The distinguished variable main makes things happen. > main = puts “ha” >> puts “ha”
is equivalent to
> main = let m = puts “ha” in m >> m
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 5 / 23
Input
Input yields a value, which is why IO is parameterised.
> getChar :: IO Char
> getLine :: IO String
> interact :: (String -> String) -> IO ()
The function getChar returns the first character from input. The function getLine returns the first line.
The function interact takes a function f as its argument. The entire input is passed to the function, and the result is output.
> main = interact (filter isAscii)
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 6 / 23
Using Files
> type FilePath = String
> writeFile :: FilePath -> String -> IO ()
> appendFile :: FilePath -> String -> IO ()
> readFile :: FilePath -> IO String
> main
> = appendFile “squares” (show [(x,x*x) | x <- [1..9]])
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 7 / 23
Plumbing
There are two ways of sequencing actions, depending on whether we want to use the result from the first action. The >>= operation passes the result of the first action to the next.
>(>>=) ::IOa->(a->IOb)->IOb >(>>) ::IOa->IOb->IOb
> return :: a -> IO a
> m >> k = m >>= \_ -> k
> main = >
>
readFile “inp” >>= \s -> writeFile “out” (filter isAscii s) >> putStr “Filtering successful\n”
Exercise: Is this expression well-typed, and if so, what is the result?
> putChar ’a’ >>= print
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 8 / 23
Do Expressions
It is just a matter of syntactic sugar to make monadic style look truly imperative. The do expression supports this:
> main > = do
> putStr “Input file: ”
> ifile <- getLine
> putStr “Output file: ”
> ofile <- getLine
> s <- readFile ifile
> writeFile ofile (filter isAscii s)
> putStrLn “Filtering successful”
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 9 / 23
Monadic Programming Example
Interactively inspect nodes in a binary tree.
> data Direction = MyLeft | MyRight | MyQuit >
> inspectTree :: Show a => Tree a -> IO () > inspectTree Void
> > > > > > > > >
= putStr “Empty”
inspectTree (Tr left node right)
=do
putStrLn (show node) cmd <- response case cmd of
MyLeft -> inspectTree left MyRight -> inspectTree right MyQuit -> return ()
PLI (Sem 1, 2019)
Haskell with Monads ⃝c University of Melbourne 10 / 23
Monadic Programming Example
> response :: IO Direction > response
> > > > > > > > > > >
=do
putStrLn “(L)eft or (R)ight or (Q)uit?” c<- getLine
case c of
"l" -> return MyLeft “L” -> return MyLeft “r” -> return MyRight “R” -> return MyRight “q” -> return MyQuit “Q” -> return MyQuit _ -> response
PLI (Sem 1, 2019)
Haskell with Monads
⃝c University of Melbourne
11 / 23
Type and Data Constructors
I should have given the definition of the type Tree a:
> data Tree a
> =Void
> |Tr(Treea)a(Treea) > deriving (Eq,Show)
Here Tr is a data constructor, used to construct elements of type Tree a. Note that it is nothing but a function.
Tree is a type constructor, a higher-order type. It is a function from types to types.
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 12 / 23
Higher-Order Types
The Prelude defines
> class Functor f where
> fmap::(a->b)->fa->fb
Note how the type variable f is applied to other types: In other words, it is a type constructor.
Types that are instances of Functor allow a “map” function which “lifts” a function of type a -> b to some higher level f a -> f b.
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 13 / 23
The Functor Class
Lists are instances of Functor, with fmap = map.
> > > > >
> > > > >
instance Functor [] where fmap f []
=[]
fmap f (x:xs)
= f x : fmap f xs
We can make any other “container” type an instance of Functor:
instance Functor Tree where fmap f Void
=Void fmapf(Trtnt’)
= Tr (fmap f t) (f n) (fmap f t’)
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 14 / 23
The Monad Class
Another class that utilises higher-order types is the monad class.
> class Monad m where
> (>>=) :: ma->(a->mb)->mb
> (>>) :: ma->mb->mb
> return:: a->ma >
>m>>k = m>>=\_->k
The operator >>= is called “bind”, and the operator >> is called “sequence”.
Clearly we’ve already seen an instance of the monad class: the type constructor IO.
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 15 / 23
The Maybe Instance
A useful data type is the “maybe” type:
> data Maybe a = Nothing | Just a
For example, we can use “Nothing” to denote unsuccessful search:
> linSearch :: Eq a => [a] -> a -> Maybe Int >
> linSearch xs y
> |occs==[] = Nothing
> | otherwise = Just (head occs)
> where
> occs = [i | (x,i) <- zip xs [0..], x==y]
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 16 / 23
The Maybe Instance
Maybe is also a monad:
> instance Monad Maybe where > return = Just
> Justx>>=f = fx
> Nothing >>= f = Nothing
As well as a functor:
> instance Functor Maybe where
> fmapf(Justx) = Just(fx) > fmap f Nothing = Nothing
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 17 / 23
The Maybe Instance
Why do we want Maybe as a monad, and why that particular definition of >>=?
Because it helps us write neater programs!
Assume that f and g are functions that both can have some abnormal outcome (hence we want to give them a Maybe type), and we want to use their composition g (f x).
This involves tedious plumbing:
> case (f x) of
> > > >
Nothing -> Nothing Justy ->case(gy)of
Nothing -> Nothing
Just z -> Just z
PLI (Sem 1, 2019)
Haskell with Monads
⃝c University of Melbourne
18 / 23
The Maybe Instance
But since Maybe is a monad we can write
> f x >>= \y -> >gy>>=\z-> > return z
> do y <- f x > z<-gy > return z
(On the right, same thing in do notation.) We can even simplify: > f x >>= \y ->
> g y >>= return
which, by the so-called monad law for return is just
> f x >>= \y -> g y
and this in turn is just
> f x >>= g
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 19 / 23
The MonadPlus Class
Many monads have more structure, namely a natural “zero” element and a “plus” operator, obeying
m >>= (\x -> mzero) = mzero
mzero >>= f
m ‘mplus‘ mzero
mzero ‘mplus‘ m
with the class definition
= mzero = m
= m
> class Monad m => MonadPlus m where > mzero::ma
> mplus::ma->ma->ma
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 20 / 23
MonadPlus Examples
> instance MonadPlus [] where > mzero = []
> mplus = (++)
> instance MonadPlus Maybe where > mzero = Nothing > Nothing ‘mplus‘ ys = ys
> xs ‘mplus‘ ys = xs
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 21 / 23
State Monads
State monads have types of the form
> data SM a = SM (S -> (S,a))
where S is some “state” type, and a is some “value” type. The idea is that an action not only produces a value, it also changes a “state”.
>
>
>
>
>
>
> in
> sm1 s1 >)
instance Monad SM where return a
= SM (\s -> (s,a)) SMsm0>>=f
=SM(\s0->let(s1,a1)=sm0s0 SMsm1 =fa1
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 22 / 23
State Monads
Strange as it may seem, this can be very useful as a tool to “hide the plumbing” in state-threading programs.
We shall see an example in a later lecture, when we use a state monad for parsing.
PLI (Sem 1, 2019) Haskell with Monads ⃝c University of Melbourne 23 / 23