How to generate a list of repeated applications of a function to the previous result of it in IO context

Question

As a part of a solution for the problem I'm trying to solve I need to generate a list of repeated application of a function to it's previous result. Sounds very much like iterate function, with the exception, that iterate has signature of

iterate :: (a -> a) -> a -> [a]

and my function lives inside of IO (I need to generate random numbers), so I'd need something more of a:

iterate'::(a -> IO a) -> a -> [a]

I have looked at the hoogle, but without much success.

Answer 1

You can actually get a lazy iterate that works on infinite lists if you use the pipes library. The definition is really simple:

import Pipes

iterate' :: (a -> IO a) -> a -> Producer a IO r
iterate' f a = do
    yield a
    a2 <- lift (f a)
    iterate' f a2

For example, let's say that our step function is:

step :: Int -> IO Int
step n = do
    m <- readLn
    return (n + m)

Then applying iterate to step generates a Producer that lazily prompts the user for input and generates the tally of values read so far:

iterate' step 0 :: Producer Int IO ()

The simplest way to read out the value is to loop over the Producer using for:

main = runEffect $
    for (iterate' step 0) $ \n -> do
        lift (print n)

The program then endlessly loops, requesting user input and displaying the current tally:

>>> main
0
10<Enter>
10
14<Enter>
24
5<Enter>
29
...

Notice how this gets two things correct which the other solutions do not:

• It works on infinite lists (you don't need a termination condition)
• It produces results immediately. It doesn't wait until you run the action on the entire list to start producing usable values.

However, we can easily filter results just like the other two solutions. For example, let's say I want to stop when the tally is greater than 100. I can just write:

import qualified Pipes.Prelude as P

main = runEffect $
    for (iterate' step 0 >-> P.takeWhile (< 100)) $ \n -> do
        lift (print n)

You can read that as saying: "Loop over the iterated values while they are less than 100. Print the output". Let's try it:

>>> main
0
10<Enter>
10
20<Enter>
30
75<Enter>
>>> -- Done!

In fact, pipes has another helper function for printing out values, so you can simplify the above to a pipeline:

main = runEffect $ iterate' step 0 >-> P.takeWhile (< 100) >-> P.print

This gives a clear view of the flow of information. iterate' produces a never-ending stream of Ints, P.takeWhile filters that stream, and P.print prints all values that reach the end.

If you want to learn more about the pipes library, I encourage you to read the pipes tutorial.

Answer 2

Your functions lives in IO, so the signature is rather:

iterate'::(a -> IO a) -> a -> IO [a]

The problem is that the original iterate function returns an infinite list, so if you try to do the same in IO you will get an action that never ends. Maybe you should add a condition to end the iteration.

iterate' action value = do
    result <- action value
    if condition result
        then return []
        else 
            rest <- iterate' action result
            return $ result : rest