It has been said that the world does not need yet another monad tutorial. Hal Daume III’s Yet Another Haskell Tutorial (copyright 2002 to 2006) is available as a Wikibook and there is a featured wikibook on Haskell itself. The November 2008 edition of Real World Haskell by Bryan O’Sullivan, Don Stewart, and John Goerzen is freely available online, as is Miran Lipovača’s Learn You a Haskell for Great Good! published in April 2011. However, although it is true that a good way to learn to use something is to use it, another good way is to try to teach it.
Values, types and classes
In Haskell, every value has a type (or, more strictly, an expression evaluates to a value and has a type). I think of types as sets of values. Functions map values of one type to values of another type, or the same type, and are themselves expressions. Some types are instances of type classes. Classes (for short) promise the availability of certain functionality, referenced by consistent names. If an instance of a class is well-behaved, the functionality delivered may also follow certain rules or ‘laws’.
Monad is the name of a class, for types that are instances of the Functor and Applicative classes – at least, since version 7.10.1 of the Glasgow Haskell Compiler (GHC) and the associated base-4.8.0.0 package. All these classes are exported by the Prelude. Many types that are commonly encountered are instances of the Monad class, including IO a, the type used for input and output (IO).
Semigroups and monoids
Before turning to monads, it is helpful to lay some other foundations. Module Data.Semigroup is part of package base. (Unless stated otherwise, all identified modules are part of that package.) The Semigroup class in that module promises, amongst other functionality, a function (an operator) (<>):
|
1 2 |
class Semigroup semigroup where (<>) :: semigroup -> semigroup -> semigroup |
(Conventionally, a to z are used as type variables but here I use more descriptive ones: semigroup rather than, say, simply a.)
A well-behaved instance of the class follows the following rule (that is, the <> operator is intended to be an associative one):
x <> (y <> z) = (x <> y) <> z
The Monoid class in module Data.Monoid promises, amongst other functionality, a function mempty for types that are semigroups.
|
1 2 |
class Semigroup monoid => Monoid monoid where mempty :: monoid |
and a well-behaved instance of the class follows the rules below (that is, mempty is an identity element with respect to the <> operator):
x <> mempty = x
mempty <> x = x
For example, for all types a, the type list of type a, [a], is a monoid:
|
1 2 3 4 5 |
instance Semigroup [a] where xs <> ys = xs ++ ys instance Monoid [a] where mempty = [] |
IO and RealWorld
Another foundation is the IO a type, defined in module GHC.Types of package ghc-prims as:
|
1 |
newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #)) |
For all types a, IO a is a type that corresponds directly with the type of a function that maps a ‘state of the real world’ to a tuple (a pair) of another ‘state of the real world’ and a value of type a.
Identity
A final foundation is the type Identity t, defined in module Data.Functor.Identity.
|
1 |
newtype Identity t = Identity { runIdentity :: t } |
Identity t is an instance of a number of classes. Its usefulness comes from it being an instance of the Monad class.
Functor
The starting point for monads is the Functor class exported by module Data.Functor (in fact, exported originally by GHC.Base). The class promises a function: fmap.
|
1 2 |
class Functor functor where fmap :: (a -> b) -> functor a -> functor b |
A well-behaved instance of the class follows the rules below:
fmap id = id
fmap (h . g) = (fmap h) . (fmap g)
Values of types that are functors ‘contain’ (or provide a ‘context’ or ‘wrapper’ for) one or more values of the same type or, in some cases, are an ’empty’ container or only context and no value. fmap maps a function over those contained values.
For example, the list type, [], which is easily seen as a ‘container’, is a functor:
|
1 2 3 |
instance Functor [] where fmap _ [] = [] fmap g (x : xs) = (g x) : (fmap g xs) |
(In fact, for [], fmap = map.)
Either error is also a functor:
|
1 2 3 |
instance Functor (Either error) where fmap _ (Left left) = Left left fmap g (Right right) = Right (g right) |
as is the (,) first type:
|
1 2 |
instance Functor ((,) first) where fmap g (context, x) = (context, g x) |
The first value of the pair provides the ‘context’ for the second value.
The idea of ‘context’ can be more complex than that of a ‘container’. The (->) input type (the type of functions that map from type input) is also a functor:
|
1 2 |
instance Functor ((->) input) where fmap g f = g . f |
Another more complex example of a functor is the following, which is of particular interest given the similarity between IO and StateProcessor state:
|
1 2 3 4 5 6 7 |
newtype StateProcessor state value = StateProcessor { runStateProcessor :: state -> (value, state) } instance Functor (StateProcessor state) where fmap g (StateProcessor p) = StateProcessor $ \s -> let (x, _) = p s in (g x, s) |
Values of type StateProcessor state value are referred to as ‘actions’. (StateProcessor is a descriptive name but cumbersome due to its length. The module Control.Monad.State.Lazy in package mtl defines type synonym State s a and function runState :: State s a -> s -> (a, s).)
Finally, Identity is a functor:
|
1 2 |
instance Functor Identity where fmap = coerce |
coerce :: Coercible type1 type2 => type1 -> type2 is exported by module Data.Coerce. Instances of class Coercible type1 type2 cannot be declared manually but exist if the compiler can infer that types type1 and type2 have the same representation. coerce converts a value of type type1 to a value of type type2. Here, coerce converts a function of type a -> b into the corresponding function of type Identity a -> Identity b.
Applicative
The next step towards monads is the Applicative class exported by module Control.Applicative (in fact, originally exported by GHC.Base). The class promises five functions for types that are functors. Two are: pure, and (<*>). The other three are: liftA2, (*>) and (<*).
|
1 2 3 4 5 6 7 |
class Functor applicative => Applicative applicative where pure :: a -> applicative a (<*>) :: applicative (a -> b) -> applicative a -> applicative b liftA2 :: (a -> b -> c) -> applicative a -> applicative b -> applicative c (*>) :: applicative a -> applicative b -> applicative b (<*) :: applicative a -> applicative b -> applicative a |
A well-behaved instance of the Applicative class follows these rules:
(pure id) <*> x' = x'
(pure g) <*> (pure x) = pure (g x)
g' <*> (pure x) = pure ($ x) <*> g'
(((pure (.)) <*> h') <*> g') <*> x' = h' <*> (g' <*> x')
and also these:
liftA2 g x' y' = (fmap g x') <*> y' (true, by default)
x' *> y' = (fmap (const id) x') <*> y' (true, by default)
x' <* y' = (fmap const x') <*> y' (true, by default)
Only pure and one of (<*>) or liftA2 need to be described to define all of them as, also by default:
g' <*> x' = (liftA2 id) g' x'.
In that regard, the type of liftA2 is:
liftA2 :: (a -> b -> c) -> applicative a -> applicative b -> applicative c
As function arrows associate to the right, that is equivalent to:
liftA2 :: (a -> (b -> c)) -> applicative a -> applicative b -> applicative c
The type of id is, for all types t, id :: t -> t. In the case of liftA2, if id is its first argument, then types t and a must be b -> c, so that:
(liftA2 id) :: applicative (b -> c) -> applicative b -> applicative c
the type of (<*>).
As indicated by its type, pure :: a -< applicative a, applied to an expression puts (lifts) that expression into the ‘container’ or ‘context’.
From the rules above, it follows that:
(pure g) <*> x' = fmap g x'
Examples of familiar types that are applicative help to understand these relationships. The type [] is applicative:
|
1 2 3 |
instance Applicative [] where pure x = [x] gs <*> xs = [g x | g <- gs, x <- xs] |
So is Either error:
|
1 2 3 4 |
instance Applicative (Either error) where pure x = Right x Left left <*> _ = Left left Right g <*> x = fmap g x |
and so is the type (,) first, if first is a monoid:
|
1 2 3 |
instance Monoid first => Applicative ((,) first) where pure x = (mempty, x) (context1, g) <*> (context2, x) = (context1 <> context2, g x) |
The pure function applied to an expression lifts it into a pair where the ‘context’ of the first element is mempty.
The type (->) input is applicative:
|
1 2 3 |
instance Applicative ((->) input) where pure x = const x (h <*> g) x = (h x) (g x) |
The type StateProcessor state can also be applicative, as follows:
|
1 2 3 4 5 6 |
instance Applicative (StateProcessor state) where pure x = StateProcessor $ \s -> (x, s) (StateProcessor p') <*> (StateProcessor p) = StateProcessor $ \s -> let (x, _) = p s (g, _) = p' s in (g x, s) |
Finally, Identity is applicative:
|
1 2 3 |
instance Applicative Identity where pure = Identity (<*>) = coerce |
Here, coerce converts a function of type Identity (a -> b) into the corresponding function of type Identity a -> Identity b.
Monad
Finally, we arrive at monads. The Monad class is exported by module Control.Monad (in fact, it is originally exported by GHC.Base). The class promises a new function (an operator) for types that are applicative, namely: (>>=) (read as bind). It also promises return, intended to be a synonym for pure; (>>) (read as then), intended to be a synonym for (*>); and (for now) fail (see class MonadFail).
|
1 2 |
instance Applicative monad => Monad monad where (>>=) :: monad a -> (a -> monad b) -> monad b |
A well-behaved instance of the Monad class follows these rules:
(pure x) >>= g = g x
x' >>= pure = x'
x' >>= (\x -> (g x) >>= h) = (x' >>= g) >>= h
[] is a monad:
|
1 2 |
instance Monad [] where xs >>= g = [y | x <- xs, y <- g x] |
Either error is a monad:
|
1 2 3 |
instance Monad (Either error) where Left left >>= _ = Left left Right right >>= g = g right |
The type (,) first is a monad, if it is applicative and first is a monoid:
|
1 2 |
instance Monad ((,) first) where (context1, x1) >>= g = case g x1 of (context2, x2) = (context1 <> context2, x2) |
The type (->) input is a monad:
|
1 2 |
instance Monad ((->) input) where f >>= g = \x -> g (f x) x |
The type StateProcessor state can also be a monad, as follows:
|
1 2 3 4 5 |
instance Monad (StateProcessor state) where (StateProcessor p) >>= g = StateProcessor $ \s -> let (x, s1) = p s StateProcessor p' = g x in p' s1 |
An example of the use of that monad is set out below, for StateProcessor String (that is, strings represent the state):
|
1 2 3 4 5 6 7 8 9 10 |
putStrLn' :: String -> StateProcessor String () putStrLn' o = StateProcessor $ \s -> ((), s ++ "Printing: " ++ o ++ ";") getLine' :: StateProcessor String String getLine' = StateProcessor $ \s -> ("dummy input", s ++ "Getting input: dummy input;") main' :: StateProcessor String () main' = putStrLn' "Hi!" >> getLine' >>= putStrLn' |
The expression runStateProcessor main' "" evaluates as: ((),"Printing: Hi!;Getting input: dummy input;Printing: dummy input;"), showing how the monad functionality allows actions to be sequenced.
Finally, Identity is a monad, although (by design) a dull one:
|
1 2 |
instance Monad Identity where x' >>= g = g (runIdentity x') |
do expressions
As explained in the Haskell 2010 Language Report, do expressions provide an alternative syntax for using the then (>>) and bind(>>=) operators.
Trivially, expression is equivalent to do { expression }.
expression >> do { statements } is equivalent to do { expression; statements }. The do syntax replaces then (>>) with a ‘semi-colon’.
let declarations in do { statements } is equivalent to do { let declarations; statements }.
Finally, let g pattern = do { statements } in expression >>= g is equivalent to do { pattern <- expression; statements } (ignoring, for the present purposes, if the pattern does not match the expression).
These equivalences are usually presented the other way around; how the do notation is translated into ‘raw’ syntax.
For example, the following expressions are all equivalent (the last using layout to remove the need for curly brackets and semi-colons):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
let msg = "Hi!" in putStrLn msg >> (getLine >>= putStrLn) let msg = "Hi!" in putStrLn msg >> (getLine >>= (\line -> putStrLn line)) let msg = "Hi!" in putStrLn msg >> (let ok line = putStrLn line in getLine >>= ok) let msg = "Hi!" in putStrLn msg >> do { line <- getLine; putStrLn line } let msg = "Hi!" in do { putStrLn msg; line <- getLine; putStrLn line } do { let {msg = "Hi!"}; putStrLn msg; line <- getLine; putStrLn line } do let msg = "Hi!" putStrLn msg line <- getLine putStrLn line |
Monad transformers
The transformers package provides a library of complex types and functions that are monad transformers – that is, they add a layer of additional functionality to another, underlying, monad. The library is portable – it does not use extensions to the Haskell 98 language. The mtl (Monad Transformers Library) package builds on transformers to provide additional functionality. However, the library is non-portable – it makes use of GHC extensions to the Haskell 2010 language.
For example, the module Control.Monad.Writer of the mtl exports type WriterT log monad' value, where type log is intended to be a monoid and type monad' is intended to be a underlying monad:
|
1 2 3 4 5 6 7 |
newtype WriterT log (monad' :: * -> *) value = WriterT (monad' (value, log)) instance (Monoid log, Monad monad') => Monad (WriterT log monad') instance (Monoid log, Monad monad') => MonadWriter log (WriterT log monad') instance Monoid log => MonadTrans (WriterT log) |
and function runWriterT:
|
1 |
runWriterT :: WriterT log monad' value -> monad' (value, log) |
As indicated above, WriterT log monad' is itself a monad.
MonadWriter, above, is a multi-parameter type class which promises function writer:
|
1 2 |
class (Monoid log, Monad monad) => MonadWriter log monad | monad -> log where writer :: (value, log) -> monad value |
The functional dependency monad -> log identifies that the type log is determined by the type monad.
Class MonadTrans is exported by module Control.Monad.Trans.Class and promises function lift:
|
1 2 |
class MonadTrans transformer where lift :: Monad monad' => monad' value -> transformer monad' value |
The simplest underlying monad that WriterT log can build upon is Identity, and module Control.Monad.Writer exports a type synonym:
|
1 |
type Writer log value = WriterT log Identity value |
and function runWriter :: Writer log value -> (value, log).
The mtl package provides other monad transformers, including:
ReaderT env(withrunReaderT :: ReaderT env monad' value -> env -> monad' value). This gives read-only access to an environment;StateT state(withrunStateT :: StateT state monad' value -> state -> monad' (value, state)). This provides access to a state that can be changed; andRWST env log state(withrunRWST :: RWST env log state monad' value -> env -> state -> monad' (value, state, log)). This provides combined Reader, Writer and State functionality.