Re: The FunctorM library

On Wed, 23 Mar 2005 17:11:21 -0800, John Meacham  wrote:
> On a tangent, I was thinking that fsequence is a nice way to commute
> monads. of course, not all monads can universally commute with every
> other monad, but those that can can be made an instance of FunctorM
> giving us a nice reusable routine...
> 
> fsequence :: f (m a) -> m (f a)
> 
> Monads that are an instance of FunctorM can always be pushed
> inside of an arbitrary monad.
> 
> Control.Monad.Identity can obviously be made an instance,
> can any of the other standard mtl monads?
> We should provide those instances.
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

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.

The laws 1 and 3 can be formulated without requiring f to be a monad
(and law 2 only needs return), but Array i, the only non-monad that
can be made a FunctorM I'm currently aware of, only satisfies law 1.

Thomas

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