Cutting off Lazy List Generation

Question

I was wondering if anyone has any insights on how to make a function that will take a list and only return the terms that can be generated in x amount of time.

For instance, I have a function that takes something like 10 minutes to return only a few terms. Instead of guessing how many terms I'd be able to generate (with take x), I'd like to just feed in an infinite list into my inefficient function and have a separate function decide when to time out.

So something like this: [5,7,10] = takeUntilTime (10 sec) . inefficientFunction $ [1..]

I'm pretty new to haskell, but I think I can write that function to just check the timer after each new term is generated and stopping if the time has elapsed.

However, what if the 4th term takes an eternity? Would there be a way to stop the inefficientFunction from finishing the generation of that 4th term even though it has already started?

I don't have high hopes for a straightforward answer, but I appreciate any intuition on this. Thanks.

Answer 1

Haven't put it through much testing, but this seems to work, at least on a small scale.

import Control.Concurrent
import Control.Exception
import Control.Monad

takeUntilTime :: Int -> [a] -> IO [a]
takeUntilTime limit list = do
    me <- myThreadId
    bracket (forkIO $ threadDelay limit >> throwTo me NonTermination) killThread
        . const $ tryTake list
  where
    (/:/) = liftM2 (:)
    tryTake list = handle (\NonTermination -> return []) $
        case list of
            [] -> return []
            x:xs -> evaluate x /:/ tryTake xs

ghci> takeUntilTime 1000000 [x | x <- [1..], x == 0]
[]
(1.02 secs, 153111264 bytes)
ghci> takeUntilTime 1000000 [maximum [y `mod` x | y <- [1..100000]] | x <- [1..]]
[0,1,2,3]
(1.00 secs, 186234264 bytes)

Answer 2

I think what you want is this: System.Timeout

It allows IO events to time out. It has a function whose type is:

timeout :: Int -> IO a -> IO (Maybe a)

I think you should be able to use that. The way that I would do it is to use the timeout function and the Iterative Deepening approach to feed more and more into your function until it works. That way, when one finally hits the timeout you know that you have gone far enough.