Monads here, monads there, monads everywhere!



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

I am continuing to use literate Haskell ...

Monads as we discussed are introduced using the class system.
Annoyingly they have been implemented to be dependent on "Applicative" and
"Functor".  So let us walk through these various definitions and try to
explain them.

The Functor Class
=================

The simplest (higher-order) class is the Functor class:

     class Functor m where
          fmap: (a -> b) -> (m a) -> (m b)

It is defined in the prelude and we shall let the definition there stand.

Here are some instances of this class:

(1) for lists (this in the prelude):

     instance Functor [] where
         fmap f [] = []
         fmap f (a:as) = (f a):(fmap f as)

(2) for the success or fail datatype:

> data SF a = SS a | FF
>    deriving (Eq,Show)
>
> instance Functor SF where
>       fmap f FF = FF
>       fmap f (SS x) = SS (f x)

(3) For the datatype of binary trees:

> data Tree a = Leaf a
>             | Node (Tree a) (Tree a)
>     deriving (Eq,Show)
>
> instance Functor Tree where
>        fmap f (Leaf x) = Leaf (f x)
>        fmap f (Node t1 t2) = Node (fmap f t1) (fmap f t2)

(4) For the datatype of expressions:

> data Exp f v = Opn f [Exp f v]
>              | Var v

> instance Functor (Exp f) where
>        fmap f (Var x) = Var (f x)
>        fmap f (Opn g args) = Opn g (fmap (fmap f) args)

The functor thus does a replacement of the variables of an expression.

Note also the "currying" form of the type constructor.  As defined
expressions -- the type constructor Exp -- has the "kind" type
      Exp:: * -> * -> *
so when f::* if follows that:
      Exp f:: * -> *
The latter is the kind type the functor class needs.


The Applicative class
=====================

This, unfortunately, is a class which is hard to justify and stands
between us and monads.  Here is its definition:

  class (Functor m) => Applicative m where
       pure:: a -> (m a)
       (<*>):: (m (a -> b)) -> (m a) -> (m b)

The infix operation <*> is the applicative its intuitive idea is that
one should be able to apply a function through a functor.  So let give some
examples:

(1) For lists:

     instance Applicative [] where
         pure x = [x]
         (f:fs) <*> as = (fmap f as)++(fs <*> as)

For lists this takes a list of functions and applies it to a list of
arguments by applying each f to each element of the list.  We could write
this as a list comprehension:

         fs <*> xs = [ f x | f <- fs, x <- xs]

Or using the do syntax this is:

         fs <*> xs = do f <- fs
                        x <- xs
                        return (f x)
      

However, list comprehension relies on having a monad so we cannot really
do this ...

(2) For the success or fail datatype the applicative is quite
straightforward:

> instance Applicative SF where
>         pure x = SS x
>         FF <*> _ = FF
>         (SS f) <*> m = fmap f m

One we have the exception monad defined we can express the applicative as:

     fs <*> xs = do f <- fs
                    x <- xs
                    return (f x)

which is the same as for lists.

(3) For the datatype of binary trees the applicative is:

> instance Applicative Tree where
>      pure x = Leaf x
>      (Leaf f) <*> ts = fmap f ts
>      (Node t1 t2) <*> ts = Node (t1 <*> ts) (t2 <*> ts)

Again once we have the tree monad in place we may regard this, using
the do syntax, as:

     fs <*> xs = do f <- fs
                    x <- xs
                    return (f x)

(4) For the datatype of expressions the applicative is:

> instance Applicative (Exp f) where
>       pure x = Var x
>       (Var g) <*> ts = fmap (\x -> g x) ts
>       (Opn f args) <*> ts = Opn f (fmap (\gs -> gs <*> ts) args) 


The Monad class
===============

The way the monad class is set up in the prelude is as follows:

   class (Applicative m) => Monad m where
      return:: a -> (m a)
      (>>=):: (m a) -> (a -> m b) -> (m b)

"return" is called the UNIT of the monad and ">>=" is called the SEQUENCER.

We can now set up monads for lists, exceptions and trees:

(1) For lists this is already done in the prelude. It looks something like:

  instance Monad [] where
      return x = [x]
      xs >>= f = concat (fmap f xs)

we can now use the do syntax to write functions here is the
pairing function:

> pairing:: [a] -> [b] -> [(a,b)]
> pairing as bs = do a <- as
>                    b <- bs
>                    return (a,b)

Recall the way of writing this as a list comprehension:

     pairing as bs = [(a,b)| a <- as, b <- bs ]

The syntaxes are almost interchangeable.  However, list comprehension
allows predicates: in the "do" syntax predicates need to be replaced with functions which return empty lists (for false) and singletons (for true).

(2) For the success or fail datatype the instance of a moad looks like:

> instance Monad SF where
>      return x = SS x
>      (SS x) >>= f = f x
>      FF >>= _ = FF

Here is the code for the function "sflist" using the do syntax:

> sflist:: [SF a] -> (SF [a])
> sflist [] = SS []
> sflist (a:as) = do a' <- a
>                    as' <- sflist as
>                    return (a':as')

Here is the banner example of quick sort in the do syntax:

> qs:: (Ord a) => [a] -> [a]
> qs [] = []
> qs (x:xs) = (qs (do x1 <- xs
>                     if x1 < x then return x1 else []))
>                 ++ [x] ++
>             (qs (do x2 <- xs
>                     if x2 >= x then return x2 else []))


(3) For trees here is the instance of a monad:

> instance Monad Tree where
>       return x = Leaf x
>       (Leaf x) >>= f = f x
>       (Node t1 t2) >>= f = Node (t1 >>= f) (t2 >>= f)

Here is an example of the use of this monad: consider the problem
of substituting the variable (or leaf) of a tree:

> subst:: (Eq v) => (v,Tree v) -> (Tree v) -> (Tree v)
> subst (v,s) t = do x <- t
>                    if x==v then s else (return x)


(4) Here is the monad instance for expressions:

> instance Monad (Exp f) where
>        return x = Var x
>        (Var x) >>= f = f x
>        (Opn g args) >>= f = Opn g (fmap (\arg -> arg>>=f) args)

Lets redo substitution but for expressions:

> substExp:: (Eq v) => (v,Exp f v) -> (Exp f v) -> (Exp f v)
> substExp (v,s) t = do x <- t
>                       if x==v then s else return x


Translating the "do" syntax
===========================

The special "do" syntax for monads which makes them much more
convenient to use is just syntax!  The sysntax can be translated out
as follows:

      do { r } = r
      do { x <- p ; C ; r } = p >>= q   where q x = do { C ; r }
      do { r' ; C ; r } = r' >>= \_ -> ( do { C ; r } )