Joe English
Sat, 10 Mar 2001 09:34:28 -0800

Eduardo Ochs wrote:
> Frank Atanassow wrote:
> > G Murali wrote (on 09-03-01 00:43 +0000):
> > > I'm new to this monads stuff.. can you tell me what it is simply ?
> > A monad on category C is a monoid in the category of endofunctors on C.
> > Is that simple enough? ;)
> Uh-oh. I'm a junior categorist and toposopher and I confess that all
> my few attempts to understand what Haskell's monads have to do with
> the categorical notion of a monad have failed more or less miserably.
> Can someone point me to a relevant paper, or give a quick explanation?

The relevant category for Haskell is the one in which
objects are types and arrows are functions.  The identity
arrow for object 't' is 'id' instantiated at type 'id :: t -> t',
and composition of arrows is function composition.

Single-argument type constructors like '[]', Maybe, etc.,
map types to types (objects to objects).  If equipped with a
suitable function 'fmap :: (a -> b) -> (T a -> T b)'
(i.e., taking arrows to arrows), they form a categorical
functor (specifically, an endofunctor), and can be made instances
of the Haskell Functor class.

Polymorphic functions are natural transformations: a function
'f :: forall a. F a -> G a' gives, for each object (type) 't'
an arrow from 'F t' to 'G t'.

One of the definitions of a monad is: a functor M equipped
with two natural transformations: eta : Id -> M and mu : MM -> M
(obeying certain laws).  Translating this into Haskell,
this is a type constructor M along with polymorphic functions
'return :: forall a. a -> M a' and 'join :: forall a. M (M a) -> M a'
(again obeying certain laws).

The 'join' function makes intuitive sense for "container-like"
monads like List (join = concat :: [[a]] -> [a]) and Maybe
(join (Just (Just x)) = Just x ; join Just Nothing = join Nothing = Nothing).
For other monads like state transformers, parsers, and IO it's
less intuitive, so it's more common to define Haskell Monads
in terms of the "bind" operation ">>=",

    (>>=) :: (M a) -> (a -> M b) -> M b

which is a close relative of the Kleisli composition operator.
Join, bind, and Kleisli composition are all interdefinable:

    (>>=) :: (M a) -> (a -> M b) -> M b
    join  :: M (M a) -> M a
    o     :: (b -> M c) -> (a -> M b) -> (a -> M c)

    m >>= k  = join (fmap k m)
    join mm  = mm >>= id
    f `o` g  = join . fmap f . g

Wadler's "Comprehending Monads" gives a very good presentation
using the fmap/return/join formulation (called map/unit/join
in that paper).  "The Essense of Functional Programming"
is another very good presentation using the return/>>=
formulation (there called "unitM/bindM").  See

    <URL: >

--Joe English