haskell join multi-level monad

Question

I'm learning haskell, and trying to use applicative functors as much as possible instead of monad. It is very neat and easy to compose. However, occasionally some types like IO [IO [a]] or IO Maybe IO Maybe a will rise in the code, which cause me big trouble. Apparently monad become inevitable in these scenarios.

I know there is a flat operation like join:: m (m a) -> m a for single level monads. Is there anything similar for multi-level monads? Anything in monad transformers?

Thanks a lot!

Answer 1

If you note that m (n _) is a monad transformer then you can define this operation. This is certainly the case when we notice that IO (Maybe a) is the same as MaybeT IO a: we then just use MaybeT's join. We can do this in no small part due to the fact that Maybe and IO "layer" especially nicely.

On the other hand, not all "composed" monads are monad transformers. In particular, IO [a] isn't really one. The true ListT transformer we'd like to have and to join looks like

newtype ListT m a = ListT { runListT :: m (Maybe (a, ListT m a)) }

It is the case that we can turn IO [a] into ListT IO a and visa-versa, but it is not the case that these operations invert one another. Truly, IO [a] is not a monad in its own right and cannot be joined.

• J. Abrahamson: The short answer is that newtype ListT m a = ListT (m [a]) follows the pattern of other types which are successfully monads, but fails to follow the rules itself for general m. I was being a little imprecise—such a ListT m is a monad exactly when [] and m commute, e.g. m [a] is isomorphic to [m a]. This is noted in the docs. There's also this page on the Wiki.
• J. Abrahamson: From a more operational POV, the problem is that m [a] varies from the ListT I gave in my answer by consolidating all of the m-effects to the top. This means that the list effects and the m-effects run in batches instead of interwoven which is necessary to satisfy the monad transformer laws in general.
• J. Abrahamson: If you look at my gist detailing the ListT-done-right implementation you'll see that the stream function allows us to convert from ListT m a to m [a]. Notably, this operation demonstrates the "smashing all of the m-effects together" problem. It also, as I noted, "blows stacks" since it means you cannot actually stream the list lazily—all of the m-effects get forced at once. (I'm not sure, in the light of the morning now, why I called it stream, actually)
• ccaapton: I kind of feel it is similar to the case of zipList but can not prove/disprove against the monad laws. For IO [ IO [a] ], currently I use fmap sequence to transform them into IO IO [[a]], then do join and fmap join. It will become IO [a] but I think it is pretty ugly.
• J. Abrahamson: That mechanism completely pulls apart the IO and [] effects. It works so long as the particular effects you're interested in have that IO [a] ~ [IO a], e.g. the effects commute. This might be the case for some IO effects, but you'll notice that your consumption of the result list and the effects that occur in the real world will become desynchronized. This is most patently bad in the case of "lazy IO" which is either forced to be strict (by the joins and sequences on IO) or non-deterministic due to the fact that resource utilization (e.g. file handles) doesn't commute with list use.

Answer 2

Monads do not commute in general, but you can provide all particular cases, that you need:

{-# LANGUAGE MultiParamTypeClasses #-}
import Control.Monad
class (Monad m, Monad n) => Swappable m n where
 swap :: m (n a) -> n (m a)
instance Swappable [] IO where
 swap = sequence
instance Swappable Maybe IO where
 swap Nothing = return Nothing
 swap (Just mx) = fmap return mx
cut :: Swappable m n => m (n (m a)) -> n (m a)
cut = liftM join . swap
squash :: Swappable m n => n (m (n (m a))) -> n (m a)
squash = (>>= cut)

An example:

x :: IO [IO [()]]
x = return $ map (\s -> putStrLn s >> return [()]) ["ab","c"]
y :: IO (Maybe (IO (Maybe ())))
y = return $ Just $ putStrLn "z" >> return (Just ())
main = squash x >> squash y

prints

ab
c
z

EDIT

You can avoid defining new typeclass by providing an instance of Traversable (there are instances for Maybe and [] in Data.Traversable):

import Data.Traversable as T
import Control.Monad
cut :: (Traversable t, Monad t, Monad m) => t (m (t a)) -> m (t a)
cut = liftM join . T.sequence
squash :: (Traversable t, Monad t, Monad m) => m (t (m (t a))) -> m (t a)
squash = (>>= cut)

• ccaapton: Thanks a lot! But I feel it is more like another adhoc transformer implementation...