Laws for Monad and MonadPlus.

Theodore Norvell
Tue, 13 Mar 2001 16:15:31 -0330

Hi all.  I was revising a short article I've written about
Monads in Haskell and started wondering about the identities
associated with Monads.

I think it is generally agreed (and in the report) that the
following identities should be true of a Monad:

Left identity:  return a >>= k   =   k a
Right identity:   p >>= return   =   p
Associativity:  (p >>= j) >= k   =   p >>= (\x->(j x >>= k))
                [provided x is not free in j or k]

What about MonadPlus?  By analogy with semirings, I came up with:

Zero:                    mzero >>= k   =  mzero  =  p >>= (\x -> mzero)
Identity:             p `mplus` mzero  =  p      =  mzero `mplus` p
Commutativity:             p `mplus` q  =  q `mplus` p
Right distributivity: (p `mplus` q) >>= k  =  (p >>= k) `mplus` (q >>= k)
Left distributivity:  p >>= (\x->j x `mplus` k x)  =  (p >>= j) `mplus` (p >== k)
                [provided x is not free in j or k]

But commutativity does not hold for Maybe or [], left distributivity
does not hold for Maybe and right distributivity does not hold for [],
so these can't be right.

Are the other identities I've listed ok?

Are there other identities that I've missed?

Theodore Norvell

Dr. Theodore Norvell                          
Electrical and Computer Engineering
Engineering and Applied Science                    Phone: (709) 737-8962
Memorial University of Newfoundland                  Fax: (709) 737-4042
St. John's, NF, Canada, A1B 3X5