State Monad

AFP Exercise 1: Write your own State Monad

(Please read the submission instructions on the Course Organization page carefully.)

The first exercise for AFP is to create your own Monad. In fact, you have to extend the well-known state monad (see Control.Monad.State in the hierarchical libraries), and add some extra features to it.

The first step is to introduce a type constructor for the new monad:

data StateMonadPlus s a = ...

The type variables s and a have the standard meaning: s is the type of the state to carry and a is the type of the return value. Make the new monad an instance of the MonadState type class. Hence, you have to include:

import Control.Monad.State

The MonadState type class uses a functional dependency: this is an extension of Haskell 98 type classes. Functional dependencies will be covered in detail in a later lecture. For now, it is sufficient to know that some compiler flags have to be set to enable the extensions that are necessary. The easiest way is to include the following pragma on the first line of your program.

{-# OPTIONS -fglasgow-exts #-}

Alternatively, you can start ghci with the -fglasgow-exts flag. We now discuss the three additional features that your monad has to support.

Feature 1: Diagnostics

We want to gather information about the number of calls to all primitive functions that work on a StateMonadPlus. For this, you have to write a function diagnostics with the following type.

diagnostics :: StateMonadPlus s String

This function should count the number of binds (>>=) and returns (and other primitive functions) that have been encountered, including the call to diagnostics at hand.

Example:

do return 3 >> return 4
   return 5
   diagnostics

gives "[bind=3, diagnostics=1, return=3]" as return value. Note that >> is implemented using >>=, and thus also counts as a bind.

Secondly, provide a function

annotate :: String -> StateMonadPlus s a -> StateMonadPlus s a

which allows a user to annotate a computation with a given label. The functions for Feature 2 and Feature 3, as well as get and put, should also be part of the diagnosis.

Feature 2: Failure

A second feature of your monad is that it can fail during a computation. The Monad type class offers the following member function:

fail :: forall m a. (Monad m) => String -> m a

Calling this function should not result in an exception. To facilitate this, the function runStateMonadPlus (which will be explained later) returns an Either value: Left indicates that the computation failed, Right indicates success. You may have to change the StateMonadPlus data type to cope with this.

Feature 3: History of states

The last feature is to save the current state, and to restore a previous state as the current state. Include the following type class definition in your code, and make StateMonadPlus an instance of this type class.

class MonadState s m => StoreState s m | m -> s where
   saveState :: m ()
   loadState :: m ()

Saving and loading states should be implemented as a stack: saving a state means pushing the current state on the stack, while loading a state means popping a state from the stack to replace the current one. If loadState is called with an empty stack, then the computation in the monad should fail (as explained for Feature 2).

Example:

do i1 <- get ; saveState
        modify (*2)
        i2 <- get ; saveState
        modify (*2)
        i3 <- get ; loadState
        i4 <- get ; loadState
        i5 <- get
        return (i1, i2, i3, i4, i5)

returns the value (1,2,4,2,1) if we start with the state consisting of the integer 1.

Running the monad

You have to write a function

runStateMonadPlus :: StateMonadPlus s a -> s -> Either String (a, s)

for running the monad. Given a computation in the StateMonadPlus and an initial state, runStateMonadPlus returns either an error message if the computation failed, or the result of the computation and the final state.

To complete this exercise, you also have to think about which functions should be exposed to outside this module, and which functions should be hidden (and only be visible inside the current module). You might want to consider re-exporting all functionality offered by the Control.Monad.State module.

Keep in mind that your code will also be judged on elegance and clarity. It is good practice to write a number of examples to test your code. You may submit your examples for testing: supply these functions in a separate file.

Questions to be answered

Question 1: Do the monad laws hold for StateMonadPlus? Explain your answer.

Question 2: What are the advantages of hiding (constructor) functions? How important is this for each of the three additional features supported by StateMonadPlus?

Question 3: Suppose that we want to write a function

diagnosticsFuture :: StateMonadPlus s String

which provides information about the computations in StateMonadPlus that are still to come. Explain how this would affect your code. (If you feel that such a facility cannot be implemented, then you should give some arguments for your opinion.) It is optional to implement this feature.