Part 6: Monads

In this part of the course, we observe how we can abstract from certain recurring patterns that arise in larger Haskell developments and thereby discover monads (and applicative functors) as useful interfaces. The advantage of having these interfaces explicit in the form of type classes is that we can build substantial libraries just in terms of these interfaces. This, in turn, means that once we have identified a particular type as a monad, we get a large amount of functionality for free.

We start by discussing the Maybe type, and then move on to a new type that is called State. We later discuss other types as well, and also revisit IO.

Accompanying materials

6–1 Preparation: Finite Maps

As a starting point for our discussion of Maybe, we return to our example of key-value tables. But this time, we use proper efficient tables as implemented by the containers package.

Self Test

  • Assuming that Data.Map.Strict is imported qualified as M, what is the result of M.lookup 1 (M.insert 1 'x' (M.insert 1 'y' M.empty))?

  • What is the result of M.lookup 1 (M.insert 2 undefined M.empty)? Does the result change if you import Data.Map.Lazy instead of Data.Map.Strict?

  • The Map type from Data.Map.Strict and Data.Map.Lazy is an instance of the Functor and Foldable classes. Try some invocations. Is fmap-ping over a finite map affecting the keys or the values? What does length on a finite map compute? What does sum compute?

6–2 Sequencing Possibly Failing Computations

We consider an example that involves running several possibly failing computations in sequence, leading to a rather noisy nested case expression that we are then trying to abstract from. As a result of this abstraction process, we discover a function with a similar type as (>>=) had in the context of IO.

Self Test

  • Given the definitions of (>>>=) from the video, what is the result of the following invocations?

    Nothing >>>= Just
Just 3 >>>= Just
Just 3 >>>= Just . (+1)
Just (Just 3) >>>= id
Just 3 >>>= const Nothing

  • Define a function someLookups :: Int -> Int -> Maybe Int where someLookups n i is performing n successive lookups in the style of the threeLookups function, starting with i, also incrementing the final result by 1. In particular, someLookups 3 should be the same as threeLookups. Do this with and without the use of (>>>=).

6–3 The Monad Class

We notice that Maybe does not just support a (>>=)-like, but also a return-like function. Types supporting these two operations are called monads. We discuss the monad class and see that Maybe is indeed an instance of this class. We observe that do notation is actually available for all instances of Monad, so we can use it to further simplify our example. And all functions that can be defined in terms of just return and bind, functions such as sequence or mapM or filterM, become available to use on Maybe computations as well.

Self Test

  • Import Control.Monad and predict the results of the following calls:

    replicateM 7 (Just 2)
replicateM 5 Nothing
mapM return [1..10] :: Maybe [Int]
mapM return [1..] :: Maybe [Int]
filterM return [True, False, True] :: Maybe [Bool]

  • Is mapM incremental? Should it be? Can it be?

  • Define a function safeDiv :: Integral a => a -> a -> Maybe a that produces Nothing rather than an exception on division by 0 and otherwise behaves like div; then define a function divisions :: Int -> [Int] -> Maybe [Int] that divides the given integer by all the integers in the list, failing if any of the divisions fail.

  • By looking at the type and trying a few example calls on Maybe inputs, try to figure out what the function join does. Try e.g.

    join (Just (Just 3))
join (Just Nothing)
join Nothing

6–4 More Functions for Free

We explore the implications of the Monad type class a bit further, by discussing for a few more functions we have previously discussed only in the context of IO how they can in fact be generalised to arbitrary instances of the Monad class, and how they behave specifically in the Maybe setting.

Self Test

  • Reproduce the definition of lookups from the video.

  • Try to define join from the previous self test just in terms of return and (>>=) (and/or do notation).

  • Recall the functions follow and search from Assignments B. Do they benefit from the fact that Maybe is an instance of Monad? If yes, rewrite them? If not, why not?

  • Recall the function mapM_ from the Self Test of Video 5–6. Is mapM_ ever useful for the Maybe type?

6–5 Recap: Labelling Trees

As another and entirely independent example, we consider a task from Assignments B, that of labelling all the nodes in a binary tree with unique labels. As a preparation, we first solve this task in classic pattern-matching style. We need to introduce an auxiliary function that has an extra integer as an input (representing the label from which we want to start labelling the current tree), and an extra integer as an output (representing the label that is the first label free to use after we are done with labelling the current tree).

Self Test

  • How do we have to adapt labelTreeAux if we want to label the element in the current node before we label the left and the right subtree?

  • Define a variant of labelTree that is of type completeTree :: BinTree (Maybe Int) -> BinTree Int. It should should fill all the occurrences of Nothing in the tree with unique counter values from left to right.

6–6 Counter

As an intermediate step before we identify a recurring pattern in the tree-labelling example, we introduce a Counter type to represent computations that maintain an Int-typed counter in order to come up with a result. We refactor the definition to make use of this Counter type and additionally introduce a helper function stepCounter to make the overall shape of the code more regular.

Self Test

  • What is the type and result of the following expression? Predict before you try:

    runCounter (MkCounter (\ c -> (True, c + 1))) 5

  • Define a version of stepCounter that resets the counter to 0 as soon as it becomes larger than 5. How does this change the behaviour of the labelTree function?

6–7 Monad Operations for Counter

We derive a “bind” and a “return” operation for counters and see how we can rewrite and now drastically simplify the definition of labelTreeAux by applying these functions, hiding the threading of the counter completely and thereby removing the potential for making mistakes.

Self Test

  • What is the result of the following calls:

    runCounter (return 0) 5
runCounter (stepCounter >>>>= \ x -> stepCounter >>>>= \ y -> returnCounter (x + y)) 5
runCounter (stepCounter >>>>= \ x -> stepCounter >>>>= \ _ -> returnCounter x) 5

  • Change the type of the Empty constructor so that it also contains an element of type a. Then adapt labelTreeAux accordingly to label these elements as well.

6–8 Functor, Applicative, Monad

In order to actually make Counter and instance of the Monad class, we have to navigate the Haskell class hierarchy and also provide instance declarations for the Applicative and Functor classes. Fortunately, if we have “bind” and “return” both available, all other methods we have to define can be mechanically completed in terms of just these two basic ingredients.

Self Test

  • Define an isomorphic copy of Maybe as follows:

    data Option a = None | Some a

    Make your Option type an instance of Monad by defining all the necessary instances.

  • The “identity type” can also be made an instance of the Monad class. It can be defined as follows:

    newtype Id a = Id { unId :: a }

    For this type, a is isomorphic to Id a, and therefore the type of return is isomorphic to the identity function, and the type of “bind”,

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

    is isomorphic to flipped function application. Define a Monad instance accordingly. (This type is available under the name Identity in the module Data.Functor.Identity.)

6–9 Optional: Using the Applicative Interface

The definition of labelTreeAux does not actually require the full power of “bind”. None of the counter-maintaining computations depend on the results of previous computations. The shape of the tree alone determines the sequence of computations we want to build. This means that we do not have to use “bind” or do notation in the definition. We can use operations provided by the Applicative class. We take a look at a common pattern sequencing operations with the help of the “applicative star” operator (<*>), which is resembling function application.

Self Test

  • Can the threeLookups example be rewritten in applicative style? If so, then do so; if not, argue why not.

  • The function filterM as defined in the Control.Monad module, somewhat ironically, has not a Monad, but only an Applicative constraint. Try to provide a definition of filterM using only the applicative interface.

6–10 Generalising from Counter to State

While Counter is a type that we have defined for the purposes of our examples, a more general form of Counter actually exists in the libraries, called State. We show how we can access the general functionality.

Self Test

  • Define a version of labelTree that, as a state, takes a list of labels, i.e.,

    labelTreeFromSupply :: BinTree a -> [b] -> BinTree (a, b)

    If the given list is not long enough, the function is exceptionally allowed to crash.

  • Try to define the accumulator-based reverse function using State. (This is not recommended in general, the pattern of foldl' is too simple to justify using State normally. It just serves as an exercise here.)

6–11 Optional: Other Monads

The monad interface is so compelling because there are, in fact, lots of types that can be made an instance. However, many types are in fact variants or combinations of the cases we have now already discussed. We discuss a few such variants. We also mention lists as an example of a Monad instance that has a rather different flavour from the examples we have seen so far.

6–12 Assignments F

The final assignments are again distributed as a zip file here.

You can unpack this file into a local directory and then work on the contents in your editor and using cabal repl. As usual, the source file contains several skeletons of functions that you are supposed to complete, as well as a few other questions.

Note that in this public version of the course, there is no way to submit the assignments.

6–13 Conclusion of the Course

We have reached the end of the course. In this short video, I reflect on what we have achieved now and provide some pointers on how you can continue your Haskell journey.