How do I find out whether a monad is commutative?

Question

The documentation for Control.Monad.List.ListT states that it "does not yield a monad unless the argument monad is commutative."

1. How do I find out whether a monad is commutative? Is there a CommutativeMonad typeclass? Should there be?

2. In particular, is Control.Monad.RWS.Lazy.RWS a commutative monad?

Billingsgate

Answer 1

In general, a monad is commutative if the expression a >>= \x -> b >>= \y -> f x y is equivalent to b >>= \y -> a >>= \x -> f x y.

In other words, it is commutative if the order of side effects is not important. We can replace the expression:

do a <- ma
   b <- mb
   f a b

with one which switches the arguments.

do b <- mb
   a <- ma
   f a b

Most Many common monads are commutative, but you can determine if a particular monad is commutative by either looking at the design and logicking it, or by writing a small program to test it with appropriate expressions (which naturally depend on the nature of the monad). As far as I know there is no CommutativeMonad typeclass.

Murvyn

I would say the opposite, most monads are not commutative, can you name any examples besides Maybe and Reader? – Siltstone

I use MonadSupply and Random pretty often, and of course there are the implementations of certain unordered data structures like multisets. But that's a fair criticism. – Murvyn

MonadSupply does not appear to be commutative by your definition. runSupply (do {a <- supply; b <- supply; return (a - b)}) [1,2] → -1 but runSupply (do {b <- supply; a <- supply; return (a - b)}) [1,2] → 1. Is there a mistake in my reasoning? – Billingsgate

@Tarrasch: This talk from ICFP 2009 has some cool examples of commutative monads. – Wickner

I've seen that before. It's a great lecture. – Murvyn

Answer 2

No, there's no CommutativeMonad class. And RWS is not commutative. For a monad to be commutative you have to be able to reorder the effects without anything changing.

Walcoff