Exercise State Monad

Afp0506
---++ 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:

<verbatim>
data StateMonadPlus s a = ...
</verbatim>

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:

<verbatim>
import Control.Monad.State
</verbatim>

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.

<verbatim>
{-# OPTIONS -fglasgow-exts #-}
</verbatim>

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.

<verbatim>
diagnostics :: StateMonadPlus s String
</verbatim>

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.
Secondly, provide a function

<verbatim>
annotate :: String -> StateMonadPlus s a -> StateMonadPlus s a
</verbatim>

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.

*Example:*
<verbatim>
do return 3 >> return 4
   return 5
   diagnostics
</verbatim>

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

*Example:*
<verbatim>
do annotate "A" (return 3 >> return 4)
   return 5
   diagnostics
</verbatim>

gives ="[A=1, bind=3, diagnostics=1, return=3]"= as return value.

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

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

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.

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

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:*
<verbatim>
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)
</verbatim>

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

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

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*: What are the modifications required to make a monad transformer for =StateMonadPlus=?
It is optional to implement this extension.

*Question 4*: Suppose that we want to write a function

<verbatim>
diagnosticsFuture :: StateMonadPlus s String
</verbatim>

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.
If you believe it can be done, it is optional to implement this feature.