Evaluación en Haskell con tiempo acotado
A veces es interesante evaluar expresiones en Haskell durante un tiempo limitado. Se puede conseguir usando la función timeout de la librería System.Timeout y la evaluate de la Control.Exception.
Vamos a mostrar su uso el siguiente ejemplo. En primer lugar, importamos las funciones
|
1 2 |
import System.Timeout (timeout) import Control.Exception (evaluate) |
A continuación, definimos la función de Fibonacci
|
1 2 3 4 |
fib :: Int -> Int fib 0 = 1 fib 1 = 1 fib n = fib (n-1) + fib (n-2) |
y la función acotada tal que (acotada t f x) calcula (f x) durante t microsegundos (1/10^6 segundos) y devuelve (Just (f x)) si encuentra su valor o Nothing en caso contrario.
|
1 2 |
acotada :: Int -> (a -> b) -> a -> IO (Maybe b) acotada t f x = timeout t (return $! f x) |
Con acotada podemos realizar evaluaciones con tiempo limitado. Por ejemplo,
|
1 2 3 4 5 6 |
ghci> acotada 100 fib 5 Just 8 ghci> acotada 100 fib 20 Nothing ghci> acotada (10^5) fib 20 Just 10946 |
También se puede acotar con evaluate. Por ejemplo,
|
1 2 3 4 5 6 |
ghci> timeout 100 $ evaluate (fib 5) Just 8 ghci> timeout 100 $ evaluate (fib 20) Nothing ghci> timeout (10^5) $ evaluate (fib 20) Just 10946 |
Esta entrada se basa en la consulta Haskell time limit on evaluation de StackOverflow.