[Haskell-cafe] Switching monadic encapsulations

[Ross Paterson]

On Mon, Jun 28, 2004 at 02:59:39PM +0100, Graham Klyne wrote:
> Is there a function that switches monadic layering?
> 
>     f :: (Monad m1,Monad m2) => m1 (m2 a) -> m2 (m1 a)
> 
> Does this even make sense in the general case?  I'm thinking along the 
> lines of a generalization of sequence to non-list monads.

Such a function is called a distributive law of m1 over m2 if it satisfies
the following equations (subscripts added for readability):

	f . return_1 = liftM_2 return_1
	f . liftM_1 return_2 = return_2
	f . join_1 = liftM_2 join_1 . f . liftM_1 f
	f . liftM_1 join_2 = join_2 . liftM_2 f . f

The composition m2.m1 can be made a monad in a standard way:

	return = return_2 . return_1
	join = liftM_2 join_1 . join_2 . liftM_2 f

if and only if such a distributive law exists.  See section 9.2 of
"Toposes, Triples and Theories", by Michael Barr and Charles Wells,
online at

	http://www.cwru.edu/artsci/math/wells/pub/ttt.html

("triple" is another name for a monad)

> [...], and sequence does 
> for the List monad what I am seeking to generalize:
> 
>    sequence :: [m a] -> m [a]

Yes, it's a distributive law of [] over m, but only if m is a
commutative monad (lists are so sequential).

Some more distributive laws:

* the exception monad distributes over any other monad:

	either (return . Left) (liftM Right)
		:: Monad m => Either x (m a) -> m (Either x a)

* so does the writer monad:

	uncurry (liftM . (,)) :: (Monoid w, Monad m) => (w, m a) -> m (w,a)

* any monad distributes over the reader monad:

	flip (liftM . flip ($)) :: Monad m => m (r -> a) -> r -> m a