What the hell are Monads?

Noel Winstanley, 1999

Introduction

This is a basic introduction to monads, monadic programming and IO, motivated by a number of people who've asked me to explain this topic, and also by similar queries I've seen on mailing lists.

This introduction is presented by means of examples rather than theory, and assumes a little knowledge of Haskell.

Maybe

Once upon a time, people wrote their Haskell programs by sequencing together operations in an ad-hoc way. The Maybe type, defined in the prelude as:

> data Maybe a = Just a | Nothing

is used to model failure. For instance, a function of type

> f :: a -> Maybe b

takes an a and may produce a result b> (wrapped in the Just constructor) or it may fail to produce a value, and return Nothing.

Example

In a database application, the query operation may have the following form

> doQuery :: Query -> DB -> Maybe Record

That is, doing a Query over the database DB may return a Record or it may fail and return Nothing.

To perform a sequence of queries (where the results of one query form part of the next query), the programmer has to explicitly check for failure after each query :

> r :: Maybe Record > r = case doQuery db q1 of > Nothing -> Nothing > Just r1 -> case doQuery db (q2 r1) of > Nothing -> Nothing > Just r2 -> case doQuery db (q3 r2) of > Nothing -> Nothing > Just r3 -> ...
This gets to be really annoying after a while, so the wise programmer, ever eager to reuse code, defines combinators that capture this pattern of error checking. For instance:

> thenMB :: Maybe a -> (a -> Maybe b) -> Maybe b > mB `thenMB` f = case mB of > Nothing -> Nothing > Just a -> f a
Using the thenMB combinator, the above code can be rewritten as below.

> r :: Maybe Record > r = doQuery q1 db `thenMB` \r1 -> > doQuery (q2 r1) db `thenMB` \r2 -> > doQuery (q3 r2) db `thenMB` ....
This code is more concise, and therefore easier to read, write, understand and debug. Note however, that the type and functionality of the expresion remains the same.

State

Another common computational pattern is threading state through a series of functions; each of which returns an altered copy of the state passed to it. Such functions can be classified as State Transformers We'll define the following synonym to capture this.

> type StateT s a = s -> (a,s)

In full: a value of type StateT s a is a function from an s (the state) to a pair of an a (the result) and a new state.

Back to the (slightly contrived) Example...

In the database application, there'll be operations to add and remove records from the database.

> addRec :: Record -> DB -> (Bool,DB)
> delRec :: Record -> DB -> (Bool,DB)

Each of these state transformers takes a Record and the old database and returns a Bool flag to indicate success or failure and the new database. Using the type synonym described above, we can give more descriptive (but equivalent) signatures for these functions:

> addRec :: Record -> StateT DB Bool
> delRec :: Record -> StateT DB Bool

so addRec and delRec are state transformers, parameterised over a Record (with which presumably they change the state). However, programming with these state transformers can be a little awkward:

>  newDB :: StateT DB Bool
>  newDB db = let (bool1,db1) = addRec rec1 db
>                 (bool2,db2) = addRec rec2 db1
>		  (bool3,db3) = delRec rec3 db2
>		  in (bool1 && bool2 && bool3,db3)

The above code adds and deletes various records from the database: it then returns the new database and the conjunction of the success flags. This thing to notice is that the new database produced by one state transformer has to be explicitly passed to the next state transformer. It is all too easy to get the various intermediate databases confused, passing the wrong value to the next state transformer: this produces hard-to-find bugs.

Learning from the experience of Maybe, the wise programmer will likewise define a combinator to sequence together a series of state transformers:

> thenST :: StateT s a -> (a -> StateT s b) -> StateT s b > st `thenST` f = \s -> let (v,s') = st s > in f v s'
thenST 'plumbs' the states together, by passing the result state from the first state transformer onto the second transformer. Another combinator, returnST, can be defined. This lifts a normal value up into a state transformer.

> returnST :: a -> StateT s a > returnST a = \s -> (a,s)
Using these combinators, the previous example can be rewritten as

> newDB :: StateT DB Bool > newDB = addRec rec1 `thenST` \bool1 -> > addRec rec2 `thenST` \bool2 -> > delRec rec3 `thenST` \bool3 -> > returnST (bool1 && bool2 && bool3)
Here the combinators take care of threading the changing database through the state transformers : this programming style shares the benefits of the Maybe example using thenMB.

It's obvious that the style of programming shown above - using combinators to manage parameter passing or computational flow - is a powerful technique for structuring code and results in clearer programs. In fact, the same ideas can be used for many other computational idioms:

Data Structures : lists, trees, sets.
Computational Flow : Maybe, Error Reporting, non-determinism
Value Passing : StateT, environment variables, output generation
Interaction with external state: IO, GUI programming, foreign language interfaces
More Exotic stuff : parsing combinators, concurrency, mutable data structures.

So, Monads

It would be nice to be able to use the same combinators for each of these idioms - as well as a uniform notation, this would allow a library of more general functions, that would operate over any of these idioms, to be built up.

Luckily, it was realised that all these examples correspond to the mathematical notion of a monad. For our purposes, a monad is a triple of a type and then> & return operators defined over it so that the following laws apply:

return a `then` f === f a m `then` return === m m `then` (\a -> f a `then` h) === (m `then` f) `then` h

The Monad Class

Haskell defines a constructor class for Monad:

>  class Monad m where
>    >>= :: m a -> (a -> m b) -> m b
>    >> :: m a -> m b -> m b
>    return :: a -> m a
>    
>    m >> k = m >>= \_ -> k

Here, the infix operator >>= is used instead of then, and a shorthand version >> is defined, which ignores the result of the first action.

Now, any type with combinators that obey the above laws can be made an instance of the Monad class. In the case of Maybe this is

> instance Monad Maybe where > (>>=) = thenMB > return a = Just a
A similar instance can be given for StateT

Technical Notes:

Haskell does not allow class instances for type synonyms, so we'd need to re-define StateT using a data declaration, and alter the definitions of thenST and returnST to accomdate the type constructor.
For all instances of the Monad class, the above laws must hold. However, Haskell compilers have no way of enforcing this. Therefore, there is a programmer proof obligation when declaring new instances

As all monads now have a common notation, combinators that operate over all monads can now be defined. The prelude contains a few, and there are more in the statdard library module 'Monad'. An example from the prelude is sequence: it takes a list of monadic computations, executes each one in turn and returns the list of their results. Using the combinators of the Monad class, it can be defined as follows.

> sequence :: Monad m => [m a] -> m [a] > sequence [] = return [] > sequence (c:cs) = c >>= \x -> > sequence cs >>= \xs -> > return (x:xs)

Do notation

Haskell has syntactic support for monadic programming - Do notation. This has a simple translation to the (>>=,>>,return) combinators, and is probably best learned from comparing examples. (although a rigourous definition is given in the Haskell report). For instance, the definition of accumulate in the prelude looks like this:

> accumulate       :: Monad m => [m a] -> m [a]
> accumulate []     = return []
> accumulate (c:cs) = do x  <- c
>	 	         xs <- accumulate cs
>		         return (x:xs)

The basic rules are

The do keyword introduces a series of monadic computations, delimited by the offside rule, as with other Haskell blocks such as let expressions.
<-> is used to bind a variable to the result of a monadic computation (instead of using >>=)
Computations whose result are ignored are simply set in line with the offset rule (no need for >>)
The do statement must finish with a return or a monadic computation (not a <-)

Further Monadic Classes

Haskell contains more classes which contain combinators related to monads. Although we won't examine them here, for reference they're called Functor and MonadPlus (defined in Prelude and Monad respectively, along with informative instances)

Monadic IO

Input/Output has been a long standing problem for pure functional languages. One of the holy grails of such languages is that the result of every function must be defined by its parameters alone. However, this is not possible for functions that perform IO. As an example, lets invent the function getChar which returns the next character from a FileHandle:

> getChar :: FileHandle -> Char

Unfortunately, this function doesn't return the same value each time it is called, and so breaks the above rule. This is because it depends on the state of the file, which changes every time getChar is used.

One solution to this is to pass the state explicitly to getChar and return a new state. Generalising, we can represent the state of the entire world by a type World. The function would now have type:

> getChar :: FileHandle -> World -> (Char,World)
Using this technique, every function performing IO is passed a World state, and returns an altered World. This works fine - the results of functions performing IO are now defined only by parameters passed to the function. However, we need to ensure that each World state is only used once - being able to re-use a World> would mean that the program would have to maintain a store of all previous states of the entire external environment: incredibly inefficient!

A solution taken by some languages (such as Clean) is to extend the type system to ensure that World values are only used once - Uniqueness Types

However, Haskell solves the single-use problem using monads. Notice that getChar is simply a state transformer (over the state of the external world) and can be rewritten as

> getChar :: FileHandle -> StateT World Char
Now using the monadic combinators defined for StateT, we can ensure that each World is only passed to one IO function, and the resulting new state is passed on to the next. The only problem remaining is that the world can be accessed at the end of a sequence of StateT computations. This leaves it open to misuse - for instance passing the resulting state to two new StateT computations. This is solved by declaring an Abstract Datatype (ADT) called IO, which itself can be made an instance of the Monad class.

> data IO a = IO (StateT World a)
The essence of an ADT is that the programmer cannot access the components of the type. This prevents the user manipulating the World returned by a IO action. getChar and friends now have types such as:

> getChar :: FileHandle -> IO Char
The only way IO actions may be executed is by defining a function main :: IO () which contains a series of IO actions. The main function implicitly passes in the world state to the sequence of actions. In this way a defined order of execution for side-effecting functions is ensured.

NB: The type IO () is used to denote an IO action that returns no interesting result, i.e. is only important for it's side-effects. An example is the dual of getChar:

putChar :: Char -> IO ()

Programming in the IO Monad

The prelude defines functions for performing IO on standard input and output. The standard module IO provides more advanced functions that operate over file handles. In addition, many of the general monad combinators in 'Monad' are especially useful for IO programming.

As well as IO functions which operate on a per-character basis (as is typical in imperative languages) there are powerful functions such as:

> getContents :: IO String > readFile :: FilePath -> IO String > writeFile :: FilePath -> String -> IO ()
getContents and readFile read an entire stream lazily (stdin or a file respectively), returning a lazily constructed list. writeFile does the opposite, writing a (possibly lazy) list as a file.

This is a nice way to get input into a program while still keeping the majority of the program monad-free. A simple example is the UNIX utility wc, a simplified version of which is:

> import System (getArgs) > main :: IO () > main = do > args <- getArgs > case args of > [fname] -> do fstr <- readFile fname > let nWords = length . words $ fstr > nLines = length . lines $ fstr > nChars = length fstr > putStrLn . unwords $ [ show nLines > , show nWords > , show nChars > , fname] > _ -> putStrLn "usage: wc fname"

Notes

getArgs :: IO [String] returns the list of commandline arguments (like C's argv).
We then check that the commandline is valid (i.e. contains one item, a filename). If it isn't we print a message and terminate. Otherwise the file is opened lazily by readFile and the statistics calculated.
The statistics are produced using length :: [a] -> Int to count the length of the lists of words, lines and characters in the file. The first two are produced using the Prelude> functions words :: String -> [String] and lines :: String -> [String].
The statistics are formatted using show :: Show a => a -> String and unwords :: [String] -> String before being output by putStrLn.
Notice the use of nested do blocks, the interaction of layout between case and do statements, and the do notation's version of a let expression (whose extent is defined by layout, so doesn't require a terminating in).
Observe that we must perform the getArgs action and get a result to pass to the case statement. Doing something like case getArgs of .. won't work - getArgs has type IO [String], not [String]. As IO is an ADT, we can't pattern match against values of this type.
This solution is inefficient -- it traverses the file string five times. A more efficient implementation would calculate the statistics simultaneously, either using a hand-coded recursive function, or by using foldr.

Summary and Further Reading

Approached from the right direction, monads aren't as obtuse as they first appear. Once an understanding is gained, it is possible to define & use monads in many different problems. They are especially useful for structuring large systems. In fact, there's a danger of programming in this style too much (I know I do), and almost forgetting about the 'pure' style of Haskell.

There's a wealth of publications available about monads. However, much of it is aimed at a different audience than 'Joe Programmer'. Here's a quick summary of some web-accessible documentation:

Theory: Phillip Wadler is one of the researchers who introduced the use of Monads to functional programming. He maintains a comprehensive list of his monad-based publications. You may find some of these hard-going: they get advanced quickly, and the notation used varies from that commonly used in Haskell. However, certainly worth a look.
Monadic Parser Combinators: Graham Hutton and Erik Meijer have published a paper on this topic which serve as a tutorial to the subject, and also describes in general the use of monads to structure functional programs. Libraries of the parser combinators are also provided. Definately one to read.
The rest: Simon Peyton Jones has a fine list of papers published by himself and colleagues. Especially relevant are the sections on foreign language integration, monads, state & concurrency, and graphical user interfaces.

© Noel Winstanley, 17/02/99
12/10/00: tidied up, rewritten
14/06/99: updated for Haskell'98
Thanks to Steve Messick, Joe English, Richard Watson, Lazlo Nemeth, Alain Van Kern, Dean Harrington and Erik Meijer for their comments.

Errors / Suggestions? nww@dcs.gla.ac.uk

nww@dcs.gla.ac.uk, 18/10/00