Haskell评估时间限制

Question

有没有人知道一个函数可以限制另一个函数的执行时间，函数类型签名大致如下。

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

我不知道如何实现，也找不到相关信息。我询问的原因是我要列出所有可能的Brainfuck程序，并过滤掉运行时间太长的。

- PyRulez

Answer 1

有一个来自System.Timeout的专用函数：timeout。

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

要按照你写的方式进行操作，只需使用以下代码：

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

记住，Haskell的惰性意味着任何值都是其他语言可能称为“零参数的记忆函数”，因此您实际上不需要 (a->b) -> a ->。

- leftaroundabout

---

我完全不知道那个存在。 - J. Abrahamson

limited t f x = timeout t (return $! f x) 可以翻译为：limited t f x = 在t时间内限制函数f x的执行，如果超时则返回空值，否则返回f x的执行结果。 - J. Abrahamson

更好的选择是：timeout t $ evaluate (f x)（其中evaluate在Control.Exception中定义）。 - Roman Cheplyaka

Answer 2

使用 async 包，我们可以进行线程的 race。

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运行两个独立的线程中的IO计算，并返回先完成的结果。因此，我们只需要将我们的线程与threadDelay进行比赛。

注意我们使用($!)来对结果f a执行seq。如果我们不这样做，那么Left线程总是胜出，并且在查看时实际上是在主线程中进行计算。

- J. Abrahamson