Bound the runtime of a computation in haskell

Question

I'm writing a game AI in Haskell, and I want to search the game state tree for a specified amount of time (i.e. I always want to AI to take 3 seconds to make its decision on what move to make)

How can I do this in a pure language like Haskell? I expect that I'll need to do some diving into threads and such but I would prefer to minimize that as much as I can.

Answer 1

One idea: Combine timeout (suggested by @MathematicalOrchid) with mutable variables from SafeSemaphore to store intermediate values every time your process computes a partial result:

import Control.Monad
import Control.Concurrent.MSampleVar
import System.Timeout

fac :: Integer -> Integer
fac 0 = 1
fac n = n * fac (n - 1)

tmo :: Int -> ((a -> IO ()) -> IO ()) -> IO (Maybe a)
tmo ms f = do
    mvar <- newSV Nothing
    timeout ms (f (writeSV mvar . (Just $!)))
    readSV mvar

longComp :: (Integer -> IO ()) -> IO ()
longComp save = let loop n = save (fac n) >> loop (n + 1)
                in loop 0

main :: IO ()
main = tmo 10000 longComp >>= print

The function passed to tmo gets as its first argument an IO action that it can use to save intermediate results. If it gets timeouted, the last saved result is returned. The result is converted to WHNF so that the real computation happens in the thread that saves the result, not in the one that processes it when it's returned from tmo.

In this variant, the function passed to tmo has to save its output, it cannot return it. But it would be easy to modify it so that it's signature would be (a -> IO ()) -> IO a.

If you want to keep things more pure I'd suggest to create your own monad that encapsulates this idea without letting IO out.

---

Update: Note that:

There is no guarantee that the exception will be delivered promptly, although the runtime will endeavour to ensure that arbitrary delays don't occur. In GHC, an exception can only be raised when a thread reaches a safe point, where a safe point is where memory allocation occurs. Some loops do not perform any memory allocation inside the loop and therefore cannot be interrupted by a throwTo.

(from the documentation of throwTo). In the example above, fac doesn't allocate any memory and so for large numbers it won't get interrupted immediately.

Update: I created a small library based on those ideas that defines a monads for computations that can return partial results before returning the final one or dying on a timeout. See https://github.com/ppetr/timeout-with-results