7

Is there a way to implement bind for nested monads? What I want is the following signature:

(>>>=) :: (Monad m, Monad n) => m (n a) -> (a -> m (n b)) -> m (n b)

It looks like it should be a trivial task, but I somehow just can't wrap my head around it. In my program, I use this pattern for several different combinations of monads and for each combination, I can implement it. But for the general case, I just don't understand it.

Edit: It seems that it is not possible in the general case. But it is certainly possible in some special cases. E.g. if the inner Monad is a Maybe. Since it IS possible for all the Monads I want to use, having additional constraints seems fine for me. So I change the question a bit:

What additional constraints do I need on n such that the following is possible?

(>>>=) :: (Monad m, Monad n, ?? n) => m (n a) -> (a -> m (n b)) -> m (n b)
Lykos
  • 1,039
  • 6
  • 25
  • 14
    I believe you just empirically discovered that monads don't compose. This is why we have monad transformers. – chi Oct 17 '15 at 16:56
  • I see. I slightly weakened the question. Now it should be possible. – Lykos Oct 17 '15 at 17:57
  • 2
    Read the linked question above: its accepted answer contains some discussion for this as well. That is, if a suitable commutativity condition between `n` and `m` holds, you do have composition. – chi Oct 17 '15 at 17:59
  • I found [another question](http://stackoverflow.com/questions/29453915/composing-monads-v-applicative-functors), whose answer has an intriguing comment that it might work if the inner monad is a `Traversable`. (That allows you to create a `join` of the right *type*, not sure about the monad laws.) I'm a bit out of time right now, but I think I'll reopen this question. – Ørjan Johansen Oct 17 '15 at 18:19
  • By which I mean, I think this question is not quite a duplicate and that `Traversable` viewpoint gives a possible way of answering it. – Ørjan Johansen Oct 17 '15 at 18:27
  • 1
    Reopening seemed to remove [the link to the related question](http://stackoverflow.com/questions/7040844/applicatives-compose-monads-dont). – Ørjan Johansen Oct 17 '15 at 18:33
  • 1
    @ØrjanJohansen `sequence` will provide a solution in cases where the commutativity condition referenced by chi holds. This condition requires a uniformity to the "shape" of the monad structures that cannot be captured by the Haskell type system. For example, Richard Bird's sudoku solution uses this uniformity of structure to commute a grid of choices (`[[]] . []`) into a choice of grids (`[] . [[]]`), which depends on the grid being rectangular (no ragged inner lists). – Rein Henrichs Oct 17 '15 at 21:59

1 Answers1

8

Expanding on the comments: As the linked questions show, it is necessary to have some function n (m a) -> m (n a) to even have a chance to make the composition a monad.

If your inner monad is a Traversable, then sequence provides such a function, and the following will have the right type:

(>>>=) :: (Monad m, Monad n, Traversable n) => m (n a) -> (a -> m (n b)) -> m (n b)
m >>>= k = do
    a <- m
    b <- sequence (fmap k a)
    return (join b)

Several well-known transformers are in fact simple newtype wrappers over something equivalent to this (although mostly defining things with pattern matching instead of literally using the inner monads' Monad and Traversable instances):

  • MaybeT based on Maybe
  • ExceptT based on Either
  • WriterT based on (,) ((,) doesn't normally have its Monad instance defined, and WriterT is using the wrong tuple order to make use of it if it had - but in spirit it could have).
  • ListT based on []. Oh, whoops...

The last one is in fact notorious for not being a monad unless the lifted monad is "commutative" - otherwise, expressions that should be equal by the monad laws can give different order of effects. My hunch is that this comes essentially from lists being able to contain more than one value, unlike the other, reliably working examples.

So, although the above definition will be correctly typed, it can still break the monad laws.

Also as an afterthought, one other transformer is such a nested monad, but in a completely different way: ReaderT, based on using (->) as the outer monad.

K. A. Buhr
  • 45,621
  • 3
  • 45
  • 71
Ørjan Johansen
  • 18,119
  • 3
  • 43
  • 53
  • In the definition of `>>>=` in this answer is there a type problem? The variable `a` has type `n a` (right?) and `k` has type `a -> m (n b)`, so how can `k` be applied to `a`? And how can `map` be applied to the result, which isn't necessarily a list? Sorry if this is obvious; I am a newbie. – jacobsa Nov 04 '22 at 05:55
  • 1
    Fixed. `map` should have been `fmap`. Since `a :: n a`, we can specialize the type `fmap k :: n a -> n (m (n b))`, so `fmap k a :: n (m (n b))` and `sequence (fmap k a) :: m (n (n b))`, so `b :: n (n b)` and `join b :: n b`, giving `return (join b) :: m (n b)`, as required. – K. A. Buhr Nov 04 '22 at 15:02