How to generically compose monadic functions that return different monads?

Question

From what I understand if you have many functions of the type f: a -> m[b] and as long as they all return values wrapped in m you should be able to chain them via do/bind/flatMap:

f: A -> M[B]
g: B -> M[C]
h: C -> M[D]

This is fairly straightforward to chain via >>= or flatMap (Scala).

How would one go about composing functions that differed in the monad "boxes" but the values inside were "chainable"?

f: A -> M[B]
g: B -> N[C]
h: C -> P[D]

I've never seen/read of this case and I understand that we can lift monads but that'll defeat the purpose IMO. Is this a limitation of the monadic construct? Can we even chain them? What's the canonical way to solve this problem?

Answer 1

As @Luis Miguel Mejía Suárez said, monads do not compose. If you have M[A], N[B] and O[C] you cannot just take them and combine into... exactly into what?

You might want to combine them into something like M[N[O[D]]]. But there flatMap would only work on the outermost monad. If you make the computation go through all layers you would have to have a monad transformer for each layer except the outermost.

Could that combined type be generated out of the box? Also not because M[N[O[D]]] would not be the same as O[N[M[D]]] and there should be some way of deciding the order in deterministic way.

You could pass natural transformations into Target[_] from each of types, which would let you transform M[A], N[B] and O[C] into Target[A], Target[B] and Target[C] and combine them as monad, but that is far from straightforward.

Then there were approaches where instead of using specific M[_], N[_], O[_], you pass them as parameters, pass Target as parameter and somehow be able to add and effect to type and execute it - Freer, its optimized form Eff and algebraic effects are such a way of creating a type=level list of effects and adding and removing them (by interpreting/running one layer). As far as I can tell these attempts were successful in that they made it possible in general to do what they promised... but the mental overhead made them super non-practical and hard to understand for majority of people. Definitively, not straightforward. Also sometimes misleading, because they sometimes pretend that order in which we interpret effects doesn't matter while in fact it does.

Currently, if you need to stack effects you are more likely using tagless final to use one, composed effect everywhere, use MTL type classes to provide state/reader/writer/etc abilities next to monadic interface. And if you had to convert between effects you would have to pass natural transformations.

So to summarize, in general this problem is not solved and even now Haskell community searches for some new solutions. Even now there is a development on libraries like Eff and Polysemy which as far as I can tell are freer/eff monad but with build-in compiler support. For now at best you can decide on you aggregated effect upfront or defer the choice via TTFI and MTL. Just taking different monads and lumping them together... not possible without thinking and writing how.