Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell Time Limit on Evaluation

Tags:

time

haskell

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.

like image 845
PyRulez Avatar asked Dec 23 '13 22:12

PyRulez


2 Answers

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 ->.

like image 65
leftaroundabout Avatar answered Oct 20 '22 16:10

leftaroundabout


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.

like image 39
J. Abrahamson Avatar answered Oct 20 '22 17:10

J. Abrahamson