Abstraction: functors, monads and folding

This chapter introduces some of the key abstractions of the Haskell type / class system, central to which is the notion of a monad. A monad provides the infrastructure for sequencing and naming used in the do notation, and we will show instances of the Monad class for lists, the Maybe type, a parsing monad and more. Before we do that we also introduce the Functor and Applicative classes on which Monad is built.

The chapter then looks again at I/O in Haskell, particularly focussing on the do notation which we can use to write all sorts of different programs, including ones that manipulate state, that non-deterministically return more than one result, or indeed none, as well as programs that may fail, or raise exceptions.

As well as looking at these definitions, we will program a number of examples, showing how a monadic style, using do, makes programs more readable and flexible. Each instance of a monad gives a ‘little language’ for writing programs, and we’ll come back to look at this in detail in the next chapter.

Abstraction

This section talks about abstraction and the way it is reflected in some of the standard type classes of Haskell. We talked earlier about abstraction as a question of spotting a pattern — maybe in some data, or maybe in a computation — and representing it directly as an object, as something in the language: an artifact in the language. We talked about spotting the pattern of mapping along a list: taking a function and applying that function f to every element of the list.

map :: (a -> b) -> [a] -> [b]

In this definition we’re saying: apply f to every element of the list. But why just lists? We could think, why not apply f to every element in the data structure? In other words, we can think of mapping across data structures other than lists.

We also saw the idea of folding: taking a function which combines all the elements of a list.

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr g s []     = s
foldr g s (x:xs) = g x (foldr g s xs)   

We saw that this pattern embodied primitive recursion, so we could define all sorts of functions over lists by means of that fold. Just as we did with map, we could think of combining all the elements in a data structure using a function, using an operator.

So can we think of types that might be “mappable”, types that might be “foldable”. The way that we do that is by representing it in a type class, and that’s what we’re going to do in this chapter. We’re going to look at the type classes of Functor and Applicative, and then we’ll move on to Monad, which is really where all this discussion began — how we represent computation inside our Haskell type system.

The Functor class

We began to look at the type classes built into Haskell in A tour of the built-in Haskell classes, and we looked mainly at the numeric type classes and some of the simpler ones, like Eq and Ord. This chapter looks at what was not covered there, namely the type classes at the bottom of the diagram — those that represent “mappable” and “foldable”. Building on top of mappable we get Applicative, and then Monads, we talk about each of those type classes, except Traversable, in the sections to come.

First we need to introduce a piece of terminology. Before talking about mappable types, let us talk about a functor as a function taking types to types. For example, Maybe is a function: it takes the type Int to the type Maybe Int, which is the type of “maybe-integers”. Similarly, we can build trees of a particular type — that’s applying the Tree functor to a particular type like Int or Bool.

Similarly, you can think of list formation as a functor: it takes a type like Bool to the type of lists of Booleans. So functors are these things that take types to types. And often many of these type functions — these functors — are mappable. For example, if we have a list of Bool, we can turn that list of Bool into a list of Int by taking a function that turns Bools into Ints and applying it to each element of the list.

So let’s reflect that in a type class definition. What we say here is: class Functor g. So for g to be in this type class, g must be a functor — a function from types to types.

class Functor g where
  fmap :: (a -> b) -> g a -> g b

How do we declare an instance of the Functor type class? We have to have a function called fmap, which, given a function from a to b and something of type g a, gives us back something of type g b where, for example, g is the list type. In the case of lists, this is just the familiar map function; but what we do in general is traverse the data structure, typically recursively, and apply f to anything of type a that we find — we know the definition for lists, but what are these other types?

A first example is the Maybe type.

data Maybe a =  
  Nothing |
  Just a

There are two kinds of elements: one is Nothing, and the other is Just x where x is of type a. In other words, something of type a, or nothing. What does fmap do over that type?

instance Functor Maybe where
  fmap f Nothing  = Nothing
  fmap f (Just x) = Just (f x)

If we apply fmap f to Nothing, we get Nothing. Whereas if we apply fmap f to Just x, f can be applied to x and return Just (f x), which is of type Maybe b. In both cases we start off with something of type Maybe a and we finish up with something of type Maybe a.

We can do a similar thing for a binary tree. We can map across all the objects of type a inside a tree — remember, here’s the type of the tree.

data Tree a =
   Nil |
   Node a (Tree a) (Tree a)

An element of this type is either empty, Nil, or it’s a node with a value of type a, a left subtree, and a right subtree. (This is the same Tree type we use later in the chapter, in Example: monadic computation over trees.) What do we do to apply f to everything of type a in the tree?

instance Functor Tree where
  fmap f Nil  = Nil
  fmap f (Node x t1 t2) =
       Node (f x) (fmap f t1) (fmap f t2)

If we apply fmap f to Nil, we get Nil; if we apply fmap f to a Node, we recursively apply fmap f to the left subtree t1 and the right subtree t2, and we apply f to the value x of type a sitting at the node, and that gives us a value of type b. In summary, a tree is a complicated structure, but at each internal node there is a value of type a, and what we have done is to apply f to transform that to something of type b.

Of course, we shouldn’t forget lists themselves — we write the list type constructor as [].

instance Functor [] where
  fmap f []  = []
  fmap f (x:xs) = 
       f x : fmap f xs

The instance for lists defines fmap f on the empty list as the empty list, and on (x:xs) to be f x : fmap f xs; in other words, fmap is map over lists. There are many more examples, but they follow the pattern that we have seen here.

The Applicative class

You will not be surprised to learn that there are ways of generalizing what we have just talked about for Functor, and one way of doing it is to build the Applicative type class. Applicative takes a two argument function, and applies it to two objects of the data type, to deliver something of that type. An example of this is the zipWith function over lists

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

zipWith g [] _ = []
zipWith g _ [] = []
zipWith g (x:xs) (y:ys) =
  g x y : zipWith g xs ys

With zipWith we have two lists and a two-argument function, and we apply that function to corresponding elements of the lists and built a list of the answers we found.

zipWith is not the only way of applying a two argument function to the values contained in two lists: rather than taking corresponding pairs of elements, as in

ghci> zipWith (+) [2,3] [20,30]
[22,33]

we could take all pairs of elements like this:

ghci> let zipAll g xs ys = [ g x y | x<-xs, y<-ys ]
ghci> zipAll (+) [2,3] [20,30]
[22,32,23,33]

The zipAll option is more satisfactory, because it doesn’t “lose” any elements, as zipWith does when lists are of unequal length, but obviously either could be used to make a definition of the function liftA2 in an instance of the Applicative class:

class Functor g => Applicative g where
  pure :: a -> g a
  (<*>) :: g (a -> b) -> g a -> g b
  liftA2 :: (a -> b -> c) -> g a -> g b -> g c   

This class definition adds some other things too.

• Applicative is built on top of Functor. That seems natural, and in fact it is possible to define fmap using the functions defined in the signature of the class; see the exercises below.

• The signature includes an operator <*>, which is like application, but for things in the data type. Thinking of lists, it takes a list of functions and a list of arguments and returns a list of results: just as before, these could be all the possible applications (by analogy with zipAll), or the application of a function to the corresponding element of the argument list (as for zipWith).

• In fact, <*> and liftA2 can be defined in terms of each other; see the exercises below.

• Finally, the pure function is added. This takes an element, x say, and lifts it to the data type: for lists this would return [x], for Maybe it would return Just x.

Because we have talked about generalizing zipWith or zipAll, we can think of writing instances of Applicative for lists. But what else can we do? Well, the Maybe type again comes to mind.

instance Applicative Maybe where
  pure x = Just x

  liftA2 f (Just x) (Just y) =
    Just (f x y)
  liftA2 _ _ _ = Nothing

Suppose we’re lifting a function f. We take two arguments of type Maybe a. If we have Just x and Just y, we can apply f to x and y and return Just (f x y). In every other case, we don’t have something of both types a and b, so we return Nothing. We can also define an instance for trees.

instance Applicative Tree where
  pure x = Node x Nil Nil

  liftA2 f Nil _ = Nil
  liftA2 f _ Nil = Nil
  liftA2 f (Node x t1 t2) (Node y s1 s2) =
    Node (f x y)
         (liftA2 f t1 s1)
         (liftA2 f t2 s2)

Let’s look at the Nil cases first. If you’ve got Nil on the left, there are no values on the left-hand side; if you’ve got Nil on the right, there are no values on the right-hand side. So in both those cases, we return Nil.

What about the remaining case, where we have two Nodes — we have a value x of type a and a value y of type b? We can apply f to those, giving us f x y of type c. Then, on the left, we recursively apply liftA2 f to t1 and s1, the left subtrees; and on the right we apply it to t2 and s2, the right subtrees. So only in the case where there are corresponding values of type a and b are we able to apply f — otherwise we simply return Nil. (This definition is by analogy with zipWith; is there also a definition analogous to zipAll?)

We can also define instances in another way — defining the <*> operator — which says we can think of applying a structure of functions to a structure of arguments: we traverse the function data structure and the argument data structure, and we apply a function that we find to an element of type a that we find. Let’s see how those definitions work out. In the case of Maybe, if we have Just f and Just x, we can return Just (f x); otherwise we return Nothing.

instance Applicative Maybe where
  …
  (Just f) <*> (Just x) = Just (f x)
  _ <*> _ = Nothing

So that’s the way this other Applicative operation works — it’s a sort of applicative application, applying a structure of functions to a structure of argument values. Now, for lists, we can see there are two ways we can define lists as an instance of Applicative. We can traverse the data structures simultaneously, applying functions to arguments, or we can traverse the data structures returning every combination of a function applied to an argument. So which is the correct one? Well, the answer is that the one that fits better with what we want to say later is the second one, and it’s the basis on which we build our explanation of how lists form a monad.

And that’s what we’re going to talk about next section: what monads are, and how they’re defined in Haskell, after revisiting the do notation.

Exercises

The do notation revisited

We have seen that the type IO a comes with various functions, including

return  :: a -> IO a
putStr  :: String -> IO ()
getLine :: IO String

but also items of the IO a type can be sequenced using the do construct. In this section we look ‘under the bonnet’ to see how the do works, as this will lead to us seeing IO as just one example of a general phenomenon.

The key to understanding the do is the operation (>>=), which is often pronounced ‘bind’, which sequences two operations, one after the other, binding the result of the first and making it available as a parameter to the second.

(>>=) :: IO a -> (a -> IO b) -> IO b

What is the effect of this operation? It combines an IO a

with a function taking the result of this (of type a) into an IO b, that is an object of type a -> IO b,

We can join them together, passing the result of the first as an argument to the second, thus:

The result of putting them together is something which does some I/O before returning a value of type b:

in other words, an object of type IO b.

How does this relate to the do notation? The bind operation, (>>=), is one of the simplest possible things we can define using do:

m >>= f =
    do
      res <- m
      f res

First what we do is execute m, which is to type IO a, and name its result res; we then pass that to the function f, giving f res ,which is of type IO b.

In fact we can translate every use of do into calls to (>>=); do is just syntactic sugar to make writing IO programs more readable. Let’s look at a particular example; consider what happens in the program

addOneInt :: IO ()
addOneInt 
  = do line <- getLine
       putStrLn (show (1 + read line :: Int))       

The value returned by getLine is called line and then used in the subsequent interaction. Using (>>=) we have to sequence the interaction with a function expecting an argument of type String, so we write

addOneInt 
  = getLine >>= \line ->
    putStrLn (show (1 + read line :: Int))       

where recall that \x -> e is the function which takes the parameter x to result e, so here the parameter is called line, and used just as above. More complex examples are translated in a similar way.

As you can see from this simple example, using (>>=) makes programs more difficult to read and understand: the do notation highlights the essential features of I/O programming:

• sequencing operations, and,

• binding the results of statements for use later on in the program.

and gives a readable and comprehensible way of writing these programs within Haskell.

We’ll continue to use the do notation, but will keep in mind that it essentially boils down to the existence of a function (>>=) which does the work of sequencing I/O programs, and binding their results for future use.

Exercises

Monads: languages for functional programming

The do notation allows us to write programs which perform I/O while calculating results; as we discussed in the last section, all we need to support the do notation is to have the ‘bind’ function and ‘return’ functions:

(>>=) :: IO a -> (a -> IO b) -> IO b
return :: a -> IO a

The IO types give one kind of program which we can describe with the do notation, but there are other kinds of program we might want to write in a similar way, such as

• programs that are non-deterministic: we can think of these as programs which return a collection of results, as a list, say;

• programs that might give no answer at all;

• programs that work by manipulating a state: that is programs that have variables in the sense of imperative languages like Java and C;

• programs that raise exceptions, and can have those exceptions handled within the program.

Well, we can do this, so long as the types have the analogue of the bind and return functions. In other words, we need to implement functions in a particular kind of interface, and we know from Overloading, type classes and type checking that this is given in Haskell by the Monad class, like this:

class Applicative m => Monad m where
  (>>=)  :: m a -> (a -> m b) -> m b
  return :: a -> m a

Once we have an instance of this class we can use the do notation over the type.

Let’s look at the example of programs that might might give no answer, the second in the list of examples above. We looked at these in Modelling program errors where we saw that the Maybe type was a good model for values including a potentially absent result:

data Maybe a = Nothing | Just a

and we developed a number of functions which worked with Maybe types to transmit errors through the code. Alternatively we can use the do notation, because we have this instance for Monad:

instance Monad Maybe where
  (Just x) >>= k  =  k x
  Nothing  >>= k  =  Nothing
  return x        =  Just x

so that we get this behaviour using do:

Prelude> do { x <- Just 1; y <- Just 2; return (x+y) }
Just 3
Prelude> do { x <- Just 1; y <- Nothing; return (x+y) }
Nothing
Prelude> do { x <- Nothing; y <- Just 2; return (x+y) }
Nothing

where we are using the braces ‘{’, ‘}’ and explicit separator ‘:’ to put the statements in the do program on a single line, as first introduced in Designing and writing programs. In a similar way, lists form a monad:

instance Monad [] where
  xs >>= f  = concat (map f xs)
  return x  = [x]

and we can use do notation over lists, like this:

Prelude> do { x <- [1,2]; y <- [3,4]; return (x+y) }
[4,5,5,6]

From this example we can see that lists model non-deterministic computation: each of x and y have two possible values, and that gives four possibilities for (x+y). The definition of (>>=) over lists reflects this: f is applied to all the possibilities in xs and the results are concatenated together.

In the next section we fill in some of the formalities about monads, but this latter section can be skipped on first reading, if you wish. We then look at some more examples of monads.

Why ‘monad’?

Why is this type class called ‘monad’? The name originates in category theory, which was used by Eugenio Moggi to build mathematical models of different kinds of computations. However, that doesn’t mean that you need to learn category theory to use them, any more than you need to understand the intricacies of modern microprocessors to use your computer! Understanding that the do notation gives sequencing and binding (or naming) is all you need to understand to get started.

Monads, formally

A monad is a family of types m a, based on a polymorphic type constructor m, with functions return, (>>=) and (>>):

class Applicative m => Monad m where
  (>>=)  :: m a -> (a -> m b) -> m b
  return :: a -> m a
  (>>)   :: m a -> m b -> m b

This is an example of a class, whose instances are type constructors – that is functions which build types from types – rather than types. Examples of type constructors are ‘list’, written [] in Haskell, and IO as we have seen already.

The definition of Monad also contains a default declaration for >>:

m >> k = m >>= \_ -> k 

From this definition it can be seen that >> acts like >>=, except that the value returned by the first argument is discarded rather than being passed to the second argument.

In order properly to be a monad, the functions return and (>>=) should have some simple properties. Informally we can state the requirements like this:

• The operation return x should simply return the value x, without any additional computational effect, such as input or output in the case of the IO monad.

• The sequencing given by >>= should be irrelevant of the way that expressions are bracketed.

The laws are much clearer when stated in terms of a derived operator, >=>, pronounced ‘fish’, that is defined in Control.Monad:

(>=>) :: Monad m => (a -> m b) ->
                    (b -> m c) ->
                    (a -> m c)

f >=> g = \x -> (f x) >>= g

This operator generalizes function composition¹ in that it composes objects

to give

Note also that return is of this shape, as its type is a -> m a.

Now we can state formally the rules that the operations of a monad should satisfy. First, return is an identity for the operator >=>:

return >=> f = f  -- (M1)
f >=> return = f  -- (M2)

and the operator >=> should be associative:

(f >=> g) >=> h = f >=> (g >=> h)  -- (M3)

The derived sequencing operator, >>, is also associative.

Of course, there is no way that we can make the requirements (M1)–(M3) a part of the Haskell definition of Monad. We can also restate the rules in terms of do, since, as we saw earlier,

m >>= f  =  do { x <- m; f x }

The first two rules become

do { y <- return x; f y } =  f x
do { x <- m; return x }   =  m

and the third is implicit in the fact that the do construct is associative.

Adding failure, MonadFail

This type class adds a function marking that a computation has failed, fail, to an existing monad.

class Monad m => MonadFail m where
  fail   :: String -> m a

The value fail s corresponds to a computation which fails, giving the error message s. The definition of MonadFail does not contains a default declaration for fail; it is expected that each instance should explicitly implement it.

The do notation provides binding to patterns, such as x <- e and [x] <- e in case of the list monad. The former pattern is irrefutable: whatever e returns, x is guaranteed to be bound to a value (if e terminates); the latter pattern is more problematic. If the value returned by e is not a singleton list, then the binding should fail, and this has the knock-on effect that the do block itself should fail: the semantics for this is provided by calling the fail function.

Exercises

Some more examples

Now we have seen the definition of what it means to be a monad, with or without failure, we look at some more examples of monads in Haskell.

The parsing monad

A more substantial example is given by parsing, where we can show that Parse a is a monad. To make a formal declaration of this we need to wrap it in a newtype constructor, MP, which clutters the definition a bit.

newtype MP a b = MP { mp :: (Parse a b) }

instance Monad (MP a) where
  return x = MP (succeed x)
  (MP pr) >>= f 
    = MP (\st -> concat [ mp (f x) rest | (x,rest) <- pr st ])

instance MonadFail (MP a) where
  fail s   = MP none

The crux of the definition of (>>=) is like that of (>*>) – a parse is done by one parser, pr, and the remains of the input are passed to a second parser f, here dependent on the result of the first parse, and so a result of the first parse, x, is passed to f to give a second parser, which is applied to the remaining input, rest.

How does the monadic approach to parsing look in practice? Let’s go back to the calculator example, and in particular the definition of opExpParse in Case study: parsing expressions. If we redefine it monadically, we get

opExpParseM :: MP Char Expr
opExpParseM =
    do
      tokenM '('
      e1 <- parseExprM 
      bop <- spotM isOp
      e2 <- parseExprM
      tokenM ')'
      return (Op (charToOp bop) e1 e2)

where tokenM is the monadic equivalent of token, and so forth. How do the definitions differ? It is mainly in the handling of the results: in the earlier treatment we built the results into a nested tuple, gathering a result for each step whether or not we needed it, and then passed the tuple to a function, via build. The approach here has the advantage that

• we only name the results of the sub-parses that we need, and

• we can build the final result directly, using these names, rather than having to use a function to re-jig the tuple into the value we want.

The disadvantage of the non-monadic approach is reminiscent of the discussion of ‘point-free’ programming: under both we combine functions, when the judicious use of names (of variables, of intermediate results) make the program substantially easier to read, write and understand.

The identity monad

The identity monad, which takes a type to itself, is the simplest example of a monad, with the definitions

x >>= f = f x 
return = id

In order for this to be a legal Haskell definition we need to define the identity type constructor, and, within Haskell 2010, any instance declaration needs to be for a data type, newtype or primitive type. So, we define, as in Control.Monad.Identity,

newtype Identity a = Identity { identity :: a }

where the constructor Identity ‘wraps’ the value up, and the field name, identity is used to ‘unwrap’ them.. Now we can define the instance itself,

instance Monad Identity where
    (Identity x) >>= f = f x          --  x >>= f = f x 
    return a           = Identity a   --  return = id 

We can then run things in this monad, if we give a Show instance for Identity

instance Show a => Show (Identity a) where
    show (Identity x) = show x

as in this example, which also shows how we can give multi-line input to GHCi interactively.

*UseMonads> :{
*UseMonads| do { x <- return 'c' :: Identity Char;
*UseMonads|      y <- return 'd';
*UseMonads|      return [x,y] }
*UseMonads| :}
"cd"

Computationally, this monad represents the trivial state in which no actions are performed, and values are returned immediately.

The state monad

Later in this chapter we will give an example of a state monad, State a b. An operation of this type can change the state (of type a) before returning a value of type b.

Some standard functions and the Functor class

There is a set of standard functions over monads, some defined in Control.Monad and some inherited from the Functor class; we just look at two of these here. Their types should be familiar from the list case

fmap :: Functor m => (a -> b) -> m a -> m b
join :: Monad m => m (m a) -> m a

and their (re-)definitions are

fmap f m 
  = do x <- m 
       return (f x)
join m  
  = do x <- m
       x

Over lists these functions are called map and concat; many of the properties of map and concat over lists lift to these functions. For instance, we can show using properties (M1) to (M3) that for all f and g

fmap (f.g) = fmap f . fmap g  -- (M4)

As we said earlier, fmap is defined over a wider set of types that monads, and it is the function that characterises the Functor class that we saw earlier:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

The definition given here redefines fmap for Functor instances that are also instances of Monad; that the redefinition defines the same function is a consequence of the Functor and Monad laws.

Exercises

data Error a = OK a | Error String

join . return = join . fmap return
join . return = id

Example: monadic computation over trees

We now illustrate how computations over the type of

data Tree a = Nil | Node a (Tree a) (Tree a)

can be given a monadic structure. We first look at a simple example, and then we look at a rather more realistic one.

We see that with a monadic approach the top-level structure of the two solutions is exactly the same. This structure guides the way that we build the implementation of the second example, as we shall see.

The moral of these examples is that monads provide an important structuring mechanism for program construction, as they encourage a separation of concerns. The top-level structure of the computation is given in terms of a monad whose specific properties are only touched upon. Within the monad itself is the appropriate computational behaviour to, for example, maintain a state or to perform some IO (or both); the particular sequencing operation of the monad will ensure that values are passed between the parts of the program in an appropriate way.

This separation of concerns comes into its own when changes are required in the details of the computation: it is usually possible to change the monad implementing a computation with at most minimal changes required at the top level. This is in stark contrast to a non-monadic computation in which data representations are visible: a wholesale restructuring is often required in such a situation.

Summing a tree of integers

Suppose we are asked to give the sum of a tree of integers,

sTree :: Tree Integer -> Integer

A direct recursive solution is

sTree Nil            = 0
sTree (Node n t1 t2) = n + sTree t1 + sTree t2

In writing this we give no explicit sequence to the calculation of the sum: we could calculate sTree t1 and sTree t2 one after the other, or indeed in parallel. How might a monadic solution proceed?

sumTree :: Tree Integer -> St Integer

where St is a monad which we have yet to define. In the Nil case,

sumTree Nil = return 0

while in the case of a Node we calculate the parts in a given order:

sumTree (Node n t1 t2)  -- (sumTree)
  = do num <- return n
       s1  <- sumTree t1
       s2  <- sumTree t2
       return (num + s1 + s2)

How is the definition structured? We put the operations in sequence, using do. First we return the value n, giving it the name num. Next we calculate sumTree t1 and sumTree t2, naming their results s1 and s2. Finally we return the result, which is the sum num+s1+s2.

Now, since all we are doing here is calculating values and not trying to do any I/O or other side-effecting operation, we make the monad St the identity monad Identity which we mentioned earlier, so we have

sumTree :: Tree Integer -> Identity Integer

There is a similarity between the definition (sumTree) and an imperative program, bearing in mind that do performs a sequencing and j <- ... gives (or assigns) a value to j. In an imperative setting, we might well write

num := n ;
s1  := sumTree t1 ;
s2  := sumTree t2 ;
return (num + s1 + s2) ;

where ‘num :=’ corresponds to the ‘<-’ and do puts a sequence of commands one after the other, as does the semi-colon. Remember, though, that this is a single-assignment language, so that num, s1 and so on are names not variables!

To give a function of type Tree Integer -> Integer we compose with the identity function to give

identity . sumTree

where

identity :: Identity a -> a
identity (Identity x) = x

takes the wrapper off an element Identity x to give the element x. In the next section we tackle a more complex problem, but see the same monadic structure repeated.

Using a state monad in a tree calculation

Building on the experience of the last section in defining sumTree we tackle here a rather more tricky problem. We want to write a function

numTree :: Eq a => Tree a -> Tree Integer

so that given an arbitrary tree we transform it to a tree of integers in which the original elements are replaced by natural numbers, starting from 0. An example is given in Replacing the elements of a tree with natural numbers.. The same element has to be replaced by the same number at every occurrence, and when we meet an as-yet-unvisited element we have to find a ‘new’ number to match it with.

Describing the calculation

How does our definition appear? We give the function a type,

numberTree :: Eq a => Tree a -> State a (Tree Integer)

in which the monad State a will have to carry about enough information to allow us to replace the elements in the correct way. The structure of the program then is

numberTree Nil = return Nil

numberTree (Node x t1 t2)  -- (numberTree)
  = do num <- numberNode x
       nt1 <- numberTree t1
       nt2 <- numberTree t2
       return (Node num nt1 nt2)

The structure here is exactly the same as that of (sumTree); we perform the operations on the components x, t1 and t2 (for the subtrees we use recursion) and then combine them in the result (Node num nt1 nt2).

What else do we have to define to give the result? We need to identify the monad State a and to define the function which replaces an individual entry,

numberNode :: Eq a => a -> State a Integer

We now have to think about the implementation of the monad. We have called it State since it keeps a record of the state, that is of which values are associated with which numbers. This we do in a table:

type Table a = [a]

where the table [True,False] indicates that True is associated with 0 and False with 1.

The State monad

What then is the state monad? It consists of functions

data State a b = State (Table a -> (Table a , b))

which, after we strip off the constructor State, we can think of as taking the state before doing the operation to the state after the operation, together with its result. In other words, we return a value of type b, but perhaps we change the value of the state of type Table a as a side-effect.

Next we have to define the two monad operations.

instance Monad (State a) where

To return a value, we leave the state unchanged.

  return x = State (\tab -> (tab,x))

How do we sequence the operations? The intended effect here is to do st, pass its result to f and then do the resulting operation.

In more detail, to perform st, we pass it the table tab; the output of this is a new state, newTab, and a value y. This y is passed to f, giving an object of type State a b; this is then performed starting with the new state newTab.

  (State st) >>= f 
    = State (\tab -> let 
                     (newTab,y)    = st tab
                     (State trans) = f y 
                     in
                     trans newTab)

Here we can see that the operations are indeed done in sequence, leading from one state value to the next.

Completing the definition

This has given us the monad; all that remains is to define the function numberNode. Our definition is

numberNode :: Eq a => a -> State a Integer
numberNode x = State (nNode x)

nNode :: Eq a => a -> (Table a -> (Table a , Integer))
nNode x table
  | elem x table        = (table      , lookup x table)
  | otherwise           = (table++[x] , integerLength table)
    where
    integerLength = toInteger.length

If x is an element of table, we return its position in the table, given by lookup; if it is not, we add it to the end of the table, and return its position, which is the length of the table. The definition of

lookup :: Eq a => a -> Table a -> Integer

is standard, and we leave it as an exercise for the reader.

Running the program

Standing back, we can see that we have completed our definition of the function

numberTree :: Eq a => Tree a -> State a (Tree Integer)

but one ingredient of the solution is still needed. If we form

numberTree exampleTree

for some exampleTree of the tree type, we have an object in

State a (Tree Integer)

In order to extract the result of running the program, we have to write a function

runST :: State a b -> b

This has to perform the calculation, starting with some initial table, and return the resulting value of type b. The definition is

runST :: State a b -> b
runST (State st) = snd (st [])

where we see that st is applied to the initial state []. The result of this is a pair, from which we select the second part, of type b. Now we can define our function

numTree :: Eq a => Tree a -> Tree Integer
numTree = runST . numberTree

which has the effect we require.

Discussion

To conclude, we have shown how a complex calculation over a tree, (numberTree), can be structured in exactly the same way as a simple one, (sumTree). In the case of a tree type the advantage is tangible, but for more complex types a monadic structure becomes almost essential if we are to follow a computation with complicated side-effects.

To see how much the monadic approach has tidied up the computation, it’s interesting to see what the computation would look like if we passed the state around explicitly. Each function would need to take a ‘before’ state as part of its input, and return an ‘after’ state as part of its result. We’d then have to thread state values through the functions so that state is updated as we compute. With the monadic approach, all the explicit threading is in the definition of (>>=) and the rest is given by the do notation.

The Control.Monad.State module

What we have presented here gives the essential idea behind the state monad in Haskell. The monad contained in Control.Monad.State is more complicated than the version presented here; our simplified version still gives the essential idea of a monad which threads state through a calculation.

Taking it further

What we have presented here just scratches the surface of monadic programming in Haskell. We have covered the basic monads, but not looked how multiple monads – such as state and exceptions – can be combined into a single monad: this is done using monad transformers, for which a number of libraries are available.

We have also not looked in any detail at monadic approaches to parsing, beyond showing how our earlier, non-monadic, parser combinators could support a monadic view too. Most of the available Haskell parsing libraries – which extend the basic approach in both expressivity and efficiency – are monadic.

There are extensions to the Monad interface: many monads, including lists and the Maybe monad, have a natural notion of a sum and zero: this gives the MonadPlus interface. At the same time, there are various weakenings of the notion of monad, including applicative functors and arrows, each with their own advantages and disadvantages.

There is no shortage of online tutorials on monads and these other features, and other texts cover them in more detail too. A standout among these is Peyton Jones’ tutorial (Peyton Jones 2001) on the ‘awkward squad’ of monads that support IO, exceptions and other computational effects.

Exercises

lookup :: Eq a => a -> Table a -> Int

look :: Eq a => a -> Table a -> Int -> Int

Folding over data: Foldable

Finally, we can get back to something we saw when we first started looking at GHCi. We saw that you can ask GHCi for the type of a function, and when we started looking at lists, we saw that the length function on a list in fact involves the Foldable type class — it says you can apply length to anything that’s an instance of Foldable.

ghci> :type length
length :: Foldable t => t a -> Int

Let’s try to understand what’s going on with Foldable. The idea is that Foldable embodies the fact that you can fold elements together, in the way that we do with list recursion. So, for example, here foldr takes two parameters: the function which embodies the recursion step — a function of type a -> b -> b — and the value that’s the starting value, of type b; and it folds together a [a] into a single b.

foldr :: (a -> b -> b) -> b -> [a] -> b
length = foldr (\_ n -> n+1) 0

Here you see the definition of the length function: it takes the particular value in the list and the length so far, n, and adds one to it for that extra node in the list, and it starts off with the value zero.

This is how we define the Foldable type class — we say what you have to do for a type function t to be in the Foldable class.

class Foldable t where
  foldr :: (a -> b -> b) -> b -> t a -> b
  -- see :info Foldable for rest of the API

You have to have a foldr function, which takes things of type t a, the recursion function, and the starting value, and gives back a b. Obviously the list type is an instance of Foldable just by the traditional definition of foldr, but there are other things we can do as well. Maybe is also an instance of the Foldable class — what do we do there?

instance Foldable Maybe where
  foldr g a Nothing  = a
  foldr g a (Just x) = g x a

Well, if we have Nothing, we return the value a, the starting value. Otherwise, if we have Just x, we have a single value of the data type, and folding that with g and a, we apply g to x and a. You can see that if Nothing were represented as an empty list, and Just x as a singleton list, this is exactly the definition we’d have for those two using foldr over lists. So you can see it’s a special case of folding over lists.

Let’s look at something a bit more interesting: we can take the type of binary trees, Tree a, where a tree is either Nil or a Node with a value of type a, a left subtree l, and a right subtree r, and we can fold over that:

instance Foldable Tree where
  foldr f z Nil          = z
  foldr f z (Node v l r) = foldr f (f v (foldr f z r)) l

So we’re folding with a function f and the starting value z, and on a Nil tree we return the starting value z. But more interestingly, what do we do on a node with a value v, a left subtree l, and a right subtree r? The answer is: we fold over the left subtree, with the initial value being the fold over the rest of the tree — that is, the fold over the right subtree, with the value v included as well. So it’s f v applied to foldr of the right subtree. Let’s see what folding over a tree looks like.

ghci> exT = Node 3 (Node 6 Nil Nil) (Node 2 Nil Nil)
ghci> length exT
3
ghci> sum exT
11

In GHCi we can ask for the length of a tree — in this case a tree with three nodes, and we get the answer that it is of length three. We could also ask for the sum of that tree, and we get the answer 11.

Or indeed, we could explicitly define a fold ourselves:

ghci> (foldr (:) []) exT
[6,3,2]

As you can see, this turns the tree into a list by “flattening” it. It flattens the tree, and you can see it’s traversing the tree from left to right — first through the left subtree, then the value, then the right subtree. We’ve seen that we can take non-trivial data structures, things other than lists, and fold over them; in fact, GHC can also derive a Foldable instance automatically, with the DeriveFoldable extension. That derived instance won’t, in general, match a hand-written one like ours: it folds over the fields in the order they’re declared in the constructor, so for Node a (Tree a) (Tree a) it would visit the value, then the left subtree, then the right subtree, rather than the left-to-right traversal we defined by hand above.

Summary

In this chapter we have seen how the do notation, which we first saw used for I/O programming, can be used to support a whole lot of different kinds of program: non-deterministic, stateful, parsing and so on. The mechanism which underlies the do notation is the Monad class, which embodies the functionality needed to sequence sub-programs, and to name their results for use later on in the program.

Like any abstract data type interface, the advantage of programming against the interface is that it is possible to modify the underlying implementation without changing the higher-level program. We saw this in action in the final section of the chapter, where two very different computations over a tree had the same top-level structure, described in a monad.

We will come back to monads in the next chapter, where we look at how Haskell is a host for ‘little languages’ that describe how to compute in a particular application area.

We’ve only just touched the surface of what’s going on with the Foldable type class — there’s comprehensive coverage of the way laziness and strictness interact with folding, and also infinite corecursion. The documentation for Data.Foldable, the module that contains all these definitions, is the place to look; it has a very nice exposition of examples and the various different approaches you might use to folding to produce different kinds of recursion, including discussion of laziness and infinite “corecursions”. And that’s just the start — there are type classes such as Traversable, and Monoid and Semigroup, and so on. There isn’t space or time to look at those in this course, but if you look in the Haskell wiki² you’ll find abundant information about them.

Now, as I’m perhaps beginning to hint here, Haskell has become a complicated language. There are large numbers of extensions to the type system, and large libraries, and that’s a good thing — it allows us to build things quickly. But it can mean that if we use, particularly, cutting-edge features — like type-level values, or some approaches to lenses — it can make code harder to read, and, more worryingly, harder to maintain. If libraries come and go, if libraries change, it can be difficult if code was written two or three years ago using a cutting-edge library and that library is no longer maintained.

It can be very difficult to maintain the codebase itself. So some of us, I think, would argue for a more modest Haskell — would argue that, if you’re using Haskell, don’t use every new feature, don’t use every new library. Think about the simplest way, at least to start with, of expressing what you want to do, and only make it more complicated when you really find the need to. In particular, that applies to generalization and abstraction: write the simplest version first, and then, if you can see a useful generalization, do that later on.

But don’t over-generalize without knowing why you’re doing it.

1. In category theory, this operation is called Kleisli composition. ↩

2. wiki.haskell.org/Foldable_and_Traversable ↩