List with first value from IO

Viewed 187

I've created an infinite list whose first element takes a little while to generate:

slowOne = do
  threadDelay (10 ^ 6)
  return 1

infiniteInts :: [IO Integer]
infiniteInts = loop slowOne
where
  loop :: IO Integer -> [IO Integer]
  loop ioInt = ioInt : loop (fmap (+1) ioInt)

When I print the list, I can observe the delay occuring not only at the first element but at all the elements:

main =
  mapM_
      (\ioInt -> do
        i <- ioInt
        print i
      )
    infiniteInts

I'm trying to improve my intuition about IO: Why is there a delay for each element, not only for the first that's generated with slowOne?

3 Answers

I'm not sure the intuition you've developed (as described in your self-written answer to this question) is all that accurate. Let me try to give you some better intuition. You may also find this old answer of mine helpful, though the question there was quite different.

In Haskell, a value of type IO a (for any type a, so an IO Int or an IO String or whatever) is sometimes referred to as an "IO action", but as @WillNess mentioned in a comment, it's best thought of as an "IO recipe". For these recipes, we think of "evaluation" and "execution" as being completely separate operations. Evaluating an expression of type IO a is like writing down the recipe. The result of evaluating an expression of type IO Int is a value of type IO Int. Producing this value performs no I/O and takes no time to speak of, even if the underlying I/O involves delays or other slow operations. This evaluated IO a value can be passed around, stored, duplicated, modified, combined with other IO recipes, or completely ignored, all without performing any actual I/O.

In contrast, executing the resulting recipe is the process of actually performing the I/O operations. The result of executing an IO Int is an Int. If it involves 20 minutes of delays, file accesses, and/or carrier pigeon requisitioning to get that Int, the operation will take a while. If you execute the same recipe twice, it won't go any faster the second time around.

Almost all of the code we write in Haskell evaluates IO recipes without executing them.

When the code:

slowOne = do
  threadDelay (10 ^ 6)
  return 1

is run, it actually just evaluates (writes down) an IO recipe. Evaluating this recipe obviously involves evaluating a do-block. This doesn't do the I/O; it just evaluates (writes down) each of the recipes in the do-block and combines them into a larger written recipe.

Specifically, evaluating slowOne involves:

  1. Evaluating the recipe threadDelay (10 ^ 6). This involves evaluating the arithmetic expression 10 ^ 6 and calling the function threadDelay on it. This function is implemented (for the non-threaded runtime) as:

     threadDelay :: Int -> IO ()
     threadDelay time = IO $ \s -> some_function_of_s
    

    That is, it wraps a function in an IO constructor to produce a value of type IO (). Critically, it doesn't actually delay the thread. It just creates a (wrapped) functional value. There's nothing magical about the IO constructor, by the way. This threadDelay function is similar to writing the equally non-magical:

     justAFunction :: Int -> Maybe (Int -> Int)
     justAFunction c = Just (\x -> c*x)
    
  2. Evaluating the recipe return 1. This, too, just creates a value wrapped in an IO constructor. Specifically, it's the (wrapped and completely non-magical) functional value that looks something like:

     IO (\s -> (s, 1))
    
  3. Combining these two evaluated recipes sequentially into a longer recipe. This new combined recipe is the value of type IO Int that will be assigned to slowOne.

Similarly, when the following code is evaluated:

infiniteInts :: [IO Integer]
infiniteInts = loop slowOne
  where
    loop :: IO Integer -> [IO Integer]
    loop ioInt = ioInt : loop (fmap (+1) ioInt)

you aren't executing any IO. You're just evaluating IO recipes and data structures that contain IO recipes. Specifically, you're evaluating this expression to a value of type [IO Integer] consisting of an infinite list of IO Integer values/recipes. The first recipe in the list is slowOne. The second recipe in the list is:

fmap (+1) slowOne

This requires a word of explanation. When this expression is evaluated, it constructs a new recipe that could be written using an equivalent do-block:

fmap_plus_one_of_slowOne = do
  x <- slowOne
  return (x + 1)

Given how slowOne is defined, this is actually equivalent to the self-contained recipe we get by evaluating:

fmap_plus_one_of_slowOne = do
  threadDelay (10 ^ 6)
  return 2

Similarly, the third recipe on the list:

fmap (+1) (fmap (+1) slowOne)

evaluates to the equivalent of the recipe:

fmap_plus_one_of_fmap_plus_one_of_slowOne = do
  threadDelay (10 ^ 6)
  return 3

Now, the last part of your program is:

mapM_
    (\ioInt -> do
      i <- ioInt
      print i
    )
  infiniteInts

It might surprise you to hear that, when this code is evaluated, we're still only evaluating and not executing recipes. When this mapM_ function is evaluated, it constructs a new recipe. The recipe it constructs could be described in words as:

"Take each recipe in the list infiniteInts. Sorry about the bad choice of name -- this isn't a list of integers, but a list of IO recipes for making integers. It's a good thing you're a computer and won't get confused by this, huh? Anyway, take each of those recipes in sequence and pass them to this function I have here to generate a new recipe. Then, run that list of recipes in order. You're writing this down, right? Stop, don't execute anything yet! Just write it down!"

So, let's recap:

  • slowOne is the recipe

    do threadDelay (10 ^ 6)
       return 1
    
  • fmap (+1) slowOne is the same as the recipe:

    do threadDelay (10 ^ 6)
       return 2
    
  • similarly, fmap (+1) (fmap (+1) slowOne) is really just the recipe

    do threadDelay (10 ^ 6)
       return 3
    

    and so on

  • therefore, infiniteInts is the list of recipes:

    infiniteInts =
      [ do { threadDelay (10 ^ 6); return 1 }
      , do { threadDelay (10 ^ 6); return 2 }
      , do { threadDelay (10 ^ 6); return 3 }
      , ... ]
    

Given the meaning of the mapM_ ... recipe, if Haskell allowed infinitely long programs, we could have written this entire recipe from scratch as follows:

do   -- first recipe
     threadDelay (10 ^ 6)
     i <- return 1
     print i

     -- second recipe
     threadDelay (10 ^ 6)
     i <- return 2
     print i

     -- third recipe
     threadDelay (10 ^ 6)
     i <- return 3
     print i

     -- etc.

That's the recipe that results from evaluating the mapM_ ... expression.

Finally, then, we get to the only part of your program that executes an IO recipe rather than simply evaluating it. That part is:

main = ...

When you name a recipe main, you tell Haskell to execute it when the program is run. As you can see from the evaluated value of the recipe you've assigned to main, it's a combined recipe involving interleaved threadDelay and print recipes, so when it's executed, it prints an increasing list of integers with delays before each integer.

A note on laziness versus strictness... Laziness plays no role in the process above (well, except for allowing us to construct an infinite list without locking up the machine). When I say "evaluate" above, it makes no difference whether the evaluation is strict and occurs immediately or if the evaluation is technically delayed until it's needed. The point at which it's needed might be when it's being executed, but the evaluation (writing of the recipe) and execution (following the recipe) are still distinct processes, even if they occur one right after the other.

Warning:

This answer is incorrect with regards to running expressions. Refer to K. A. Buhr's answer first to get a better understanding of how this list of IO values works.


We can understand this behavior by

Here are the rewritings of infiniteInts for getting different numbers of elements:

Getting one element

slowOne : loop (fmap (+1) slowOne)

Since Haskell's : operator is non-strict, we run slowOne once → this takes one second.

Getting two elements

slowOne : (fmap (+1) slowOne) : loop (fmap (+1) (fmap (+1) slowOne))

Taking two elements (up till the second :) causes slowOne to be called twice → this takes two seconds.

Getting three elements

slowOne : (fmap (+1) slowOne) : (fmap (+1) (fmap (+1) slowOne)) : loop (fmap (+1) (fmap (+1) (fmap (+1) slowOne)))

Taking three elements (up till the third :) causes slowOne to be called three times → this takes three seconds.

Summary

From the rewritings we can see that slowOne is called for each element (e.g., three times for three elements) and given that GHC won't cache results created inside IO (which is the case for slowOne) it follows that each element takes a second to be created.

Every number is delayed because they're all coming from slowOne. Consider your loop:

loop ioInt = ioInt : loop (fmap (+1) ioInt)
     ^----This is slowOne              ^
                                       └----This is also slowOne

My own intuition about what it is that your fmap is doing is simply acting on the IO value (the Integer in IO Integer), but keeping all of its context (the "IO" part) intact.

As Will Ness's commented:

fmap (1+) takes an IO value (a pure value of type IO t for some t) which describes I/O action that will return a pure value x :: t when that action will run; and creates a new pure IO value describing an augmented I/O action that will return the pure value x+1 after performing the I/O actions as described by the first IO value.

As an example of this, we could replace slowOne by another function timedOne:

timedOne = do
  time <- getPOSIXTime
  putStrLn $ "time: " ++ show time
  return 1

Calling loop with timedOne instead of slowOne would print this out, showing how fmap affects the value without affecting the context:

time: 1583715559.051068s
1
time: 1583715559.051705s
2
time: 1583715559.052311s
3
... and so on

You see that each number that gets used, still carries its own IO "baggage", only this time that baggage is "get the time from the system clock and print it out". If you want to change this behaviour so that only the first number will be delayed, you need to purge the tail of the list built by loop of any thread-delaying IO baggage. One way to do that is by using a pure list and wrapping each element in IO:

loop ioInt = ioInt : (return <$> [2..])
Related