Monads here, monads there, monads everywhere!


--------------------------------------------------------------------

> import System.IO

More literate Haskell ...

The State Monad
===============

An important monad -- that it is usueful to know about -- is the
state monad.  To get the state monad going it is necessary to
introduce the "state changing" type as a datatype:

> data (SM s a) = Sm (s -> (a,s))

There is only one constructor, Sm, so this means the type is essentially
s -> (a,s) i.e. a function which given a state produces a paired value
and new state. As the class system requires we have an explicit
data constructor.

A useful bit of code is the "running" or "application" of the monad type
on a state.

> runSM:: (SM s a) -> s -> (a,s)
> runSM (Sm h) s = h s

As before to get a monad going we need to introduce its curried kind
as a functor (recall SM:: * -> * -> * is a type constructor with two
arguments and the functor class wants a type constructor with just one
argument (SM s):: * -> *):

> instance Functor (SM s) where
>     fmap f (Sm h) = Sm (\s -> (\(a,s') -> (f a, s')) (h s))

Next one needs to define SM s as an applicative:

> instance Applicative (SM s) where
> --    pure:: a -> (SM s a)
>     pure a = Sm (\s -> (a,s))
> --    (<*>) ::(SM s (a->b)) -> (SM s a) -> (SM s b)
>     u <*> v
>           = Sm (\s -> (\(f,s') -> (\(a,s'') -> (f a, s'')
>                                   ) (runSM v s')
>                       )(runSM u s))

The applicative here is the state change given by running the
state change mandated by u to obtain a function, f, and a new state, s',
then one uses this state, s', to run the state change mandated by , v,
to obtain the value, a, and a new state, s''.  One returns
the state s'' paired with the evaluation of f a.

Once you have the monad this can be expressed as
       u <*> v =  do f <- u
                     a <- v
                     return (f a)

Finally, we can declare this state changing device as a monad:

> instance Monad (SM s) where
>     return a = Sm (\s -> (a,s))
>     (Sm f) >>= g = Sm (\s -> (\(a,s') -> runSM (g a) s') (f s))

Numbering the leaves of an  expression:
=======================================

Here is an example of using the state monad to number the leaves
of an expresssion:

> data Exp f v = Var v
>              | Opn f [Exp f v]
>    deriving (Eq,Show)

Numbering the leaves of an expression

> number_exp :: (Exp a b) -> (SM Int (Exp a Int))
> number_exp (Var x) 
>    = do n <- Sm (\n -> (n,n+1))
>         return (Var n)
> number_exp (Opn f args) 
>    = do args' <- number_args args
>         return (Opn f args')

> number_args :: [(Exp a b)] -> (SM Int [(Exp a Int)])
> number_args [] = return []
> number_args (x:xs)
>    = do x' <- number_exp x
>         xs' <- number_args xs
>         return (x':xs')
                   
> ex1 = runSM (number_exp (Opn "f" [Var "a",Var "b",Var"a"])) 0

Replacing variable names with numbers:
======================================

A more sophisticated example: substituting the variables of an
expression with (new) numbers.  This is useful if you are trying
to standardize the names of variables ...

> type ISubs v = [(v,Int)]

> data SF a = SS a | FF -- success or fail data type
>    deriving (Eq,Show)

The substitution of a string either replaces the string with a number
as specified in the list of substitutions or adds a substitution using
the least number still available ...

> subst:: Eq v => v -> (SM (ISubs v) Int)
> subst str = 
>   Sm (\subs -> case (insubs str subs) of
>                   SS n -> (n,subs)
>                   FF ->(next_free str 0 subs))
>    where
>        insubs:: Eq v => v -> (ISubs v) -> (SF Int)
>        insubs str [] = FF
>        insubs str ((str',n):subs)| str==str' = SS n
>                                  | otherwise = insubs str subs
>        next_free:: Eq v => v -> Int -> (ISubs v) -> (Int,ISubs v)
>        next_free str n [] = (n,[(str,n)])
>        next_free str n ((str',m):subs)
>                   | n < m = (n,(str,n):((str',m):subs))
>                   | otherwise = (\(m',subs') -> (m',((str',m):subs')))
>                                 (next_free str (n+1) subs)

So here the function "insubs" finds the substitution (the number which is
to replace the variable) from a list of substitutions -- if it is there.
If it is not there then a new substituion must be generated: in this case
"next_free" finds the least number no yet used for a substitution. It does
this by looking through the substitution list (which is held in order) until
it finds a number which has no been used.

Here then is code for substitution/replacement of the variables an expression by
integers using the state monad ...

> subst_exp:: Eq v => (Exp f v) -> (SM (ISubs v) (Exp f Int))
> subst_exp (Var x) = do n <- subst x
>                        return (Var n)
> subst_exp (Opn f ts) = do ts' <- subst_list ts
>                           return (Opn f ts')
>  where
>         subst_list [] = return []
>         subst_list (t:ts) = do t' <- subst_exp t
>                                ts' <- subst_list ts
>                                return (t':ts')

> ex2 = runSM (subst_exp (Opn "f" [Var "a",Var "b",Var "a"])) []

Applying game moves
===================

In the checkers program you have to apply a move (which is a list of touch
down coordinates of a piece) to a game state: this can be programmed as a
state monad.  Now you should not take this example as me advising you to
implement it in this manner.  By using features which are more sophisticated
may make your code harder to debug.  However, this is a way to implement
things and it does illustrate the utility of the state monad.

To statr with we need a datatype to represent the various sorts of pieces
which inhabit a checkers board:

data PieceType = RedPiece | BlackPiece | RedKing | BlackKing | NoPiece

Now the idea is we need to write "apply_move":

apply_move::Move ->  GameState -> GameState
apply_move mv st | member mv (moves st) = snd (runSM (mover mv) st)
                             | otherwise = setmessage st "Illegal move!"
                             
First we check that the move is legal by generating the legal moves using
"move".  If the move is legal we run the state monad on a function
called "move" and extract the state (which is a Gamestate) from the result.

Now we must write the mover fuction and here we rely on the state monad:

mover:: Move -> (SM GameState ())
mover [end] = return ()
mover (m1:m2:ms) =
             do   pt <- remove_piece m1
	          _  <- remove_piece (jumped m1 m2)
		  () <- add_piece  pt m2
		  mover (m2:ms)

You can actually do "apply_move" for the simple moves and jump moves all
together: the trick is in the function "jumped".  It should return the
position jumped over ... but what if there is nothing to jump over? That
is it was a simple move ... well you could return SF(Coord) and then modify
the "remove_piece" function to do nothing when it recieves a fail (it can
return any memebre of Piecetype say NoPiece).

Here we shall just boot this problem down the road (to you) and give the basic
idea of the code:

remove_piece:: Coord -> SM(GameState,PieceType)
remove_piece xy = SM (piece_remover xy)
   where
      piece_remover:: Cood -> GameState -> (GameState,PieceType)
      piece_remover xy st| member xy (_redKings st)
               = (st{_redKings = remove xy (_redKings st)},RedKing)
                         | member xy (_redPieces st)
               = ...

add_piece:: PieceType -> Coord -> SM(GameState,())
add_piece RedKing xy = Sm (\st -> (st{_redPieces = xy:(_redPieces st)},()))
...


Monadic I/O
===========

Haskell implements I/O using monads and the type IO a.  It has various
functions for I/O in particular:

    putstr:: String -> IO ()
    getLine:: IO String

The type () is the "unit type": it is an empty tuple so contains
no information ... but is useful if you want to NOT convey any
information!!

The I/O monad is builtin on the type IO: * -> * an this means  one can
use the do synatx to do some simple I/O.  For example:

> myhead (x:xs) = SS x
> myhead _ = FF

> moodtest = do  putStr "Are you happy?\n"
>                ans <- getLine
>                case myhead ans of
>                      SS 'y' -> putStr "Hurrah!\n"
>                      SS 'n' -> putStr "Oh dear!\n"
>                      FF -> putStr "Not sure ... hmmm!\n"

There are lots of functions associated with I/O which you can explore ...