The FunctorM library

[Ross Paterson]

On Thu, Mar 24, 2005 at 10:24:50AM +0100, Thomas Jäger wrote:
> The following distributive laws [1] might be postulated:
> 1) fsequence . fmap return === return
> 2) fsequence . return === fmap return
> 3) fsequence . fmap join === join . fmap fsequence . fsequence

also

4) fsequence . join === fmap join . fsequence . fmap fsequence

These are all necessary for the composition to be a monad.

> Identity, Maybe, Either e and Writer w (for monoids w) are perfect
> instances; the list monad doesn't obey law 3. I don't believe any of
> the monads that is based a function type can be made an instance of
> FunctorM, and if we impose additional restrictions, such as a finite
> domain in case of the reader monad, we lose laws 2 and 3.

M1 o M2 is a monad if M2 is one of those you mentioned, or if M1 is
a reader monad.

> The laws 1 and 3 can be formulated without requiring f to be a monad
> (and law 2 only needs return),

Yes, laws 1 and 3 are equivalent to saying that fmapM defines a functor
on the Kleisli category, i.e.

	fmapM return = return
	fmapM (f >>> g) = fmapM f >>> fmapM g
where
	(>>>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
	(f >>> g) a = f a >>= g

> but Array i, the only non-monad that
> can be made a FunctorM I'm currently aware of, only satisfies law 1.

Isn't Array i a reader monad with a finite domain?  (i.e. return fills
the array with copies, and join selects the diagonal)

> [1] Barr, Wells: Toposes, Triples and Theories
> http://www.cwru.edu/artsci/math/wells/pub/ttt.html, p. 298