[Haskell-cafe] Algebraic Effects?

[Olaf Klinke]

> Have distributive laws [1] ever been used for monad composition in
> Haskell? After all, two monads with a distributive law compose.
> 
> Till
There is the distributive package on Hackage, which at least matches the type of the nLab definition. 

Many common monad transformers stem from monads that are "universally distributive" in the following sense:
If t is a monad transformer, then for all other monads m a function with one of the following types can be defined: 

t Identity (m a) -> m (t Identity a)
m (t Identity a) -> t Identity (m a)

For which transformers is this the case? For those where t m a is isomorphic to one of the two types
t Identity (m a)
m (t Identity a)

Examples:

distr_Reader :: Functor m => m (r -> a) -> r -> m a
distr_Reader = \m -> \r -> fmap ($r) m

distr_Writer :: Functor m => (w,m a) -> m (w,a)
distr_Writer = \(w,m) -> fmap ((,) w) m

distr_Either :: Applicative m => Either e (m a) -> m (Either e a)
distr_Either (Left e) = pure (Left e)
distr_Either (Right m) = fmap Right m

distr_Maybe :: Applicative m => Maybe (m a) -> m (Maybe a)
distr_Maybe Nothing = pure Nothing
distr_Maybe (Just m) = fmap Just m

More generally, two monads distribute when one is an endofunctor on the Kleisli category of the other. 
(The nLab page says Eilenberg-Moore category, I'm not sure whether the two statements are equivalent.) 
A morphism in the Kleisli category of m is a function
a -> m b.
An endofunctor f on the Kleisli category must map such a function to a function
f a -> m (f b).
For example, 

kleisli_Maybe :: Applicative m => (a -> m b) -> Maybe a -> m (Maybe b)
kleisli_Maybe _ Nothing = pure Nothing
kleisli_Maybe k (Just a) = fmap Just (k a)

kleisli_Reader :: Functor m => (a -> r -> b) -> m a -> r -> m b
kleisli_Reader k x r = fmap (flip k r) x

Notice that in the former case we used the Kleisli category of m whereas in the latter case we used the Kleisli category of Reader. 

The more general picture involves an adjunction and the monad m. This covers StateT and the continuation monad. It is well-known that any adjunction F -| G between two categories gives rise to a monad, namely GF. 
Suppose F:C->D and G:D->C are functors. The adjuntion says that the hom-sets D(Fa,b) and C(a,Gb) are naturally isomorphic. 
For the state monad,
C = Hask (the category of Haskell types and functions)
D = Hask,
F = (,) s
G = (->) s
and the isomorphism of hom-sets is currying and uncurrying between (s,a) -> b and a -> (s -> b).

In case of the continuation monad Cont r a = (a -> r) -> r, we have
C = Hask,
D = Hask^op (Hask with direction of arrows reversed)
F a = (a -> r)
G b = (b -> r)
and the isomorphism of hom-sets is between a -> (b -> r) and b -> (a -> r)
where the latter is Hask^op(Fa,b).

In the case of StateT, since the intermediate category D is Hask, any functor m is an endofunctor on the intermediate category. I do not recall under which conditions the composite GMF is a monad. 

Olaf