Haskell评估时限

Question

有没有人知道一个只允许一定时间执行函数的函数.像这样的类型签名的东西.

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

我想不出如何实现,我找不到它.我问的原因是我要列出所有可能的Brainfuck程序,我想过滤那些花费太长时间的程序.

Answer 1

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

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

raceIO在单独的线程中运行两个计算并返回"赢"中的任何一个,所以我们只是针对a来竞争我们的线程threadDelay.

注意,我们使用($!)到seq的结果f a.如果我们不这样做,那么Left线程总是会赢,并且当你看它时计算实际上发生在主线程中.