Identify commutative monads to provide better type safety

[jwiegley]

Imagine we have some Monad m, we can easily use the Applicative to do something like:

combine x y = liftA2 (,) x y

However, using MonadBaseControl, we cannot safely lift an operation like this through a base monad:

combineM x y = liftBaseWith (\run -> liftA2 (,) (run x) (run y))
                   >>= (\(a, b) -> liftA2 (,) (restoreM a) (restoreM b))

The reason is that in combineM, x and y are executed independently from each other, and then their contexts are recombined, rather than executing within a single, new context.

It turns out that this works for commutative monads, just not for non-commutative ones. Thus, functions like concurrently from lifted-async become dangerous to use, because there is no type-checking done to guard against using non-commutative monads.

I'm not sure what the best solution to this problem is, other than having a new set of "law only" type classes to identity the monads we can safely use in such operations:

-- | Monoids which are also commutative
--
-- This type class introduces no new operations, but rather a single law:
-- @
-- mappend x y = mappend y x
-- @
class Monoid m => Commutes m

instance Commutes ()
instance Commutes m => Commutes (Maybe m)
instance Num a => Commutes (Sum a)
instance Num a => Commutes (Product a)
instance Commutes Ordering
instance Commutes Any
instance Commutes All
instance Commutes b => Commutes (a -> b)
instance (Commutes a, Commutes b, Commutes c, Commutes d)
         => Commutes (a, b, c, d)
instance (Commutes a, Commutes b, Commutes c) => Commutes (a, b, c)
instance (Commutes a, Commutes b) => Commutes (a, b)
instance Commutes a => Commutes (Const a b)

-- | Applicative functors which are also commutative
--
-- This type class introduces no new operations, but rather a single law:
-- @
-- liftA2 ($) x y = liftA2 (flip ($)) y x
-- @
class Applicative f => Commutative f

instance Commutative IO
instance Commutative (ST s)
instance Commutative STM
instance Commutative Identity
instance Commutative Maybe                   -- false if we consider bottoms
instance Commutes w => Commutative (Either w) -- false if we consider bottoms
instance Commutative ((->) r)
instance Commutative m => Commutative (IdentityT m)
instance Commutative m => Commutative (ReaderT r m)
instance (Monad m, Commutative m) => Commutative (MaybeT m)
instance (Commutative m, Commutes w) => Commutative (WriterT w m)
instance (Monad m, Commutative m, Commutes w) => Commutative (EitherT w m)
instance Commutes w => Commutative (Const w)

Now we can safely lift concurrently:

concurrently :: (MonadBaseControl IO m, Commutative m) => m a -> m b -> m (a, b)
concurrently f g =
    liftBaseWith (\run -> Async.concurrently (run f) (run g))
        >>= (\(x, y) -> liftA2 (,) (restoreM x) (restoreM y))

I'm opening this issue to invite discussion on this.

[jwiegley]

Pinging @snoyberg, whose monad-unlift library aims at solving some of the consequences of this problem.

[snoyberg]

Are there examples of a commutative monad which doesn't fit into MonadUnlift?

[jwiegley]

WriterT -- where the accumulator is a commutative monoid -- since in that case StM m a is not equivalent to a, as it holds the accumulated value from the action.

[jwiegley]

This should have been obvious to me, but IO is not commutative, so my notes here may not apply as I had thought before.