Observations

I believe we can.

Generally speaking, say, we have two monads, T and U; their composition T ∘ U is a functor which is not always a monad. Unit is okay, but multiplication, T ∘ U ∘ T ∘ U → T ∘ U does not always exist. It would exist if the two monads commuted, that if, if we had U ∘ T → T ∘ U, which is also known as traversal of U over T; in case U comes from a monoid, this is the famouse "map/reduce".

I was working on a simple example in Java programming language, say, take Reader monad and Maybe monad, the latter also known as Option in Scala and in various Java libraries. It is almost obvious that if we have a Maybe wrapped into a Reader, it cannot be naturally transformed into Reader wrapped into a Maybe.

Maybe in Java can be thought of as a function that may throw some kind of exception, and we don't care which, just catch it (and log it, that's what Java people do with exceptions).

Reader in Java can be represented as "dependency injection" - we have a function that is supposed to return something, but its behavior depends on some external circumstances unknown to client code. This is different from State, an example of which is a Random Numbers Generator; with "dependency" we are tied to the same environment during the lifetime of the program.

For the utmost simplicity, let's imagine that we have only two possible "environment values", say, DEBUG, which is either TRUE or FALSE.

So, in this case, what the client thinks of as a function: X → Y, in our Reader is actually a function: X → Y2 whereby we potentially produce two values, one for DEBUG=TRUE and another for DEBUG=FALSE.

If we deal with Maybe, what a client sees as a function: X → Y is actually function: X → 1+Y, where failures map values into this 1, which in Java is represented via null.

Okay.

Now one composition is (1 + Y)2 == 1 + 2×Y + Y2, and the other is 1 + Y2.

We can easily embed the second one into the first one, but there's no general natural way to transform the first one to the second one; what will we do with the two instances of 1×Y? Unless we have Y as an algebra over Maybe, that is, a natural transformation 1 → Y.

Nevertheless, I will show that the composition of Maybe ∘ Reader is a monad.

First, let's generalize Reader to a dependency on a certain type E of "environment: Reader<E>.

So, Reader amounts to having a functor X ↦ XE, where unit X → XE amounts to constant, and multiplication (XE)E → XE is dual to diagonal Δ E → E×E, that is, XΔ.

Now, can we naturally transform Reader(Maybe(Reader(Maybe(X)))) to Reader(Maybe(X))? Not only naturally, but with all the monadic properties of multiplication (unit and associativity, that is).

We have (1 + (1 + X)E)E, and we need to produce (1 + X)E

This is dual to (thanks to Yoneda Lemma) having a good transformation
E × (1 + (1 + X)E)E → (1 + X)

Let's throw in Δ E → E×E, and build
E × (1 + (1 + X)E)E → E × E × (1 + (1 + X)E)E → (1 + X)

Using eval: E × AE, have
E × E × (1 + (1 + X)E)E → E × (1 + (1 + X)E)

So it would be enough to have a good
E × (1 + (1 + X)E) → (1 + X)
which amounts to having

E × 1 + E × (1 + X)E) → (1 + X)

Which is obvious: the first component maps to 1, the second is eval again.

That's it.

Questions? Errors? Remarks? Suggestions.

(One question is how come Java types are not Maybe-algebras, they are, are not they?)