lazy version of mapM

Question

Suppose, I'm getting large list of items while working with IO:

as <- getLargeList

Now, I'm trying to apply fn :: a -> IO b onto as:

as <- getLargeList
bs <- mapM fn as

mapM has type mapM :: Monad m => (a -> m b) -> [a] -> m [b], and that's what I need in terms of type matching. But it builds all the chain in memory until return the result. I'm looking for analog of mapM, which will work lazily, so that I may use head of bs while tail is still building.

Answer 1

Do not use unsafeInterleaveIO or any lazy IO for that matter. This is precisely the problem that iteratees were created to address: avoiding lazy IO, which gives unpredictable resource management. The trick is to never build the list and constantly stream it using iteratees until you are done using it. I will use examples from my own library, pipes, to demonstrate this.

First, define:

import Control.Monad
import Control.Monad.Trans
import Control.Pipe

-- Demand only 'n' elements
take' :: (Monad m) => Int -> Pipe a a m ()
take' n = replicateM_ n $ do
    a <- await
    yield a

-- Print all incoming elements
printer :: (Show a) => Consumer a IO r
printer = forever $ do
    a <- await
    lift $ print a

Now let's be mean to our user and demand they produce the really large list for us:

prompt100 :: Producer Int IO ()
prompt100 = replicateM_ 1000 $ do
    lift $ putStrLn "Enter an integer: "
    n <- lift readLn
    yield n

Now, let's run it:

>>> runPipe $ printer <+< take' 1 <+< prompt100
Enter an integer:
3<Enter>
3

It only prompts the user for one integer, since we only demand one integer!

If you want to replace prompt100 with output from getLargeList, you just write:

yourProducer :: Producer b IO ()
yourProducer = do
    xs <- lift getLargeList
    mapM_ yield xs

... and then run:

>>> runPipe $ printer <+< take' 1 <+< yourProducer

This will lazily stream the list and never build the list in memory, all without using unsafe IO hacks. To change how many elements you demand, just change the value you pass to take'

For more examples like this, read the pipes tutorial at Control.Pipe.Tutorial.

To learn more about why lazy IO causes problems, read Oleg's original slides on the subject, which you can find here. He does a great job of explaining the problems with using lazy IO. Any time you feel compelled to use lazy IO, what you really want is an iteratee library.

Answer 2

The IO monad does have a mechanism to defer effects. It's called unsafeInterleaveIO. You can use it to get the desired effect:

import System.IO.Unsafe

lazyMapM :: (a -> IO b) -> [a] -> IO [b]
lazyMapM f [] = return []
lazyMapM f (x:xs) = do y <- f x
                       ys <- unsafeInterleaveIO $ lazyMapM f xs
                       return (y:ys)

This is how lazy IO is implemented. It is unsafe the sense that the order in which the effects will actually be executed is hard to predict and will be determined by the order in which the elements of the result list are evaluated. For this reason, it is important that any IO effects in f are benign, in the sense that they should be order insensitive. A good example of a usually sufficiently benign effect is reading from a read-only file.