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:`7 (Just 2) replicateM 5 Nothing replicateM mapM return [1..10] :: Maybe [Int] mapM return [1..] :: Maybe [Int] return [True, False, True] :: Maybe [Bool] filterM`

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.`Just (Just 3)) join (Just Nothing) join (Nothing join`

## 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:

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

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:

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

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.