Haskell Time Limit on Evaluation

Question

Does anyone know of a function that will allow only a certain amount of time to execute a function. Something with a type signature like this.

limited::Int->(a->b)->a->IO (Maybe b)

I can't think of how to implement, and I couldn't find it. The reason why I ask is I am going to make a list of all possible Brainfuck programs, and I want to filter out the ones that take too long.

Moitoso

Answer 1

There's a dedicated function from System.Timeout:

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

To have it the way you wrote, just use

limited t f x = timeout t $ do
     let y = f x
     y `seq` return y

Remember that Haskell's laziness means any value is what other languages might call "memoised function of zero arguments", so you don't really need the (a->b) -> a ->.

Guillory

I had no idea that existed. – Bose

limited t f x = timeout t (return $! f x) – Bose

Better yet: timeout t $ evaluate (f x) (evaluate is defined in Control.Exception) – Protagonist

Answer 2

Using the async package we can race threads.

import Control.Applicative
import Control.Concurrent
import Control.Concurrent.Async

limited :: Int -> (a -> b) -> a -> IO (Maybe a)
limited n f a = isLeft <$> race (return $! f a) (threadDelay n)
  where isLeft (Left a) = Just a
        isLeft _        = Nothing

race runs two IO computations in separate threads and returns whichever one "wins", so we just race our thread against a threadDelay.

Note that we use ($!) to seq the result f a. If we don't then the Left thread always wins and the computation actually occurs in the main thread when you look at it.

Bose