Monadic list comprehension in Haskell

Question

List comprehension is very easy to understand. Look at h in the following definition. It uses pure_xs of type [Int], and pure_f of type Int -> String, using both in the list comprehension.

pure_xs :: [Int]
pure_xs = [1,2,3]

pure_f :: Int -> String
pure_f a = show a

h :: [(Int,Char)]
h = [(a,b) | a <- pure_xs, b <- pure_f a]
-- h => [(4,'4'),(5,'5'),(6,'6')]

Great. Now take two slightly different expressions, monadic_f and monadic_xs. I would like to construct g using list comprehensions, to look as similar to h as possible. I have a feeling that a solution will involve generating a sequence of IO actions, and using sequence to generate a list of type [(Int,Char)] in the IO monad.

monadic_xs :: IO [Int]
monadic_xs = return [1,2,3]

monadic_f :: Int -> IO String
monadic_f a = return (show a)

g :: IO [(Int,Char)]
g = undefined -- how to make `g` function look
              -- as similar to `h` function as possible, i.e. using list comprehension?
-- g => IO [(4,'4'),(5,'5'),(6,'6')]

Answer 1

The natural way to write this would be

do xs <- monadic_xs
   ys <- mapM monadic_f xs
   return (zip xs ys)

But we can't translate that naturally into a list comprehension because we need the (>>=) binds in there to extract the monadic values. Monad transformers would be an avenue to interweave these effects. Let's examine the transformers ListT monad transformer — even though it's not actually a monad transformer.

newtype ListT m a = ListT { runListT :: m [a] }

listT_xs :: ListT IO Int
listT_xs = ListT monadic_xs

listT_f :: Int -> ListT IO String
liftT_f = ListT . fmap return . monadic_f

>>> runListT $ do { x <- listT_xs; str <- listT_f x; return (x, str) }
[(1,"1"),(2,"2"),(3,"3")]

So that appears to work and we can turn on MonadComprehensions to write it in a list comprehension format.

>>> runListT [ (x, str) | x <- listT_xs, str <- listT_f x ]
[(1,"1"),(2,"2"),(3,"3")]

That's about as similar to the result you get with the pure version as I can think of, but it has a few dangerous flaws. First, we're using ListT which may be unintuitive due to it breaking the monad transformer laws, and, second, we're using only a tiny fraction of the list monadic effect---normally list will take the cartesian product, not the zip.

listT_g :: Int -> ListT IO String
listT_g = ListT . fmap (replicate 3) . monadic_f

>>> runListT [ (x, str) | x <- listT_xs, str <- listT_g x ]
[(1,"1"),(1,"1"),(1,"1"),(2,"2"),(2,"2"),(2,"2"),(3,"3"),(3,"3"),(3,"3")]

To solve these problems you might want to experiment with pipes. You'll get the "correct" solution there, though it won't look nearly as much like a list comprehension.