Laws for Monad and MonadPlus.

[Theodore Norvell]

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?

Cheers,
Theodore Norvell

----------------------------
Dr. Theodore Norvell                                    theo@engr.mun.ca
Electrical and Computer Engineering         http://www.engr.mun.ca/~theo
Engineering and Applied Science                    Phone: (709) 737-8962
Memorial University of Newfoundland                  Fax: (709) 737-4042
St. John's, NF, Canada, A1B 3X5