给出了初始值(x)、函数(f)、谓词(p)和时间界限(t)。我想在 x 上重复应用“f”,直到它满足“p”。但同时要确保它不超过时间限制。如果时间超过“t”,它应该返回部分结果,即一对数字“n”和对“x”应用“f”n次的值,对于实际执行计算的最大n。
如果放宽部分结果条件,则可以轻松编程为 -
import System.Timeout
iter :: a -> (a -> a) -> (a -> Bool) -> Int -> IO (Maybe (Int, a))
iter x f p t = do
let fs = x:(map f fs)
timeout t $ return $! head $ filter (\x -> p $ snd x) $ zip [1..] fs
我希望它的签名类似于 -
iter :: a -> (a -> a) -> (a -> Bool) -> Int -> IO (Either (Int, a) (Int, a))
左为部分结果,右为完整结果。
使用上述函数的一个愚蠢而琐碎的示例是 -
*Main> iter 1 (+2) (> 1000000) 1000000
Just (500001,1000001)
*Main> iter 1 (+2) (> 1000000) 100000
Nothing
我希望第二次调用返回部分计算结果。有简单的方法吗?
更实际的例子可以是牛顿-拉夫森方法或梯度下降。
最佳答案
我认为最简单的方法是将此类任务委托(delegate)给比 base
提供的抽象能力更好的库,例如async
:
{-# LANGUAGE BangPatterns #-}
import Control.Concurrent.Async
import Control.Concurrent
iter :: a -> (a -> a) -> (a -> Bool) -> Int -> IO (Either (Int, a) (Int, a))
iter z f p maxt = do
o <- newMVar (0, z)
let loop old@(!i,x) = do
modifyMVar_ o (const $ return old)
if p x then return old else loop (i+1, f x)
race (threadDelay maxt >> readMVar o) (loop (0, z))
race
执行两个 IO
操作并返回先完成的操作,并杀死另一个操作。仅当最长时间已过且该线程能够读取 MVar 时,左侧操作才会完成。由于另一个线程会在短时间内(在写入结果时)保存 MVar
,因此工作线程在写入结果时永远不会被中断。
另请注意,强制应用程序链 f $ f $ f..
的唯一因素是谓词 p
- 如果您传递惰性函数(例如 const False
) 那么这将无法按您想要的方式工作。在实践中,很少有情况会使用这样的函数(尤其是数值计算),因此它可能不会引起太多关注。但在这种情况下,loop
没有执行任何实际工作,并且构建了数量惊人的应用程序:
>iter 2 (\x -> x * x) (const False) (10^6)
Left (472190,Interrupted.
我的计算机将永远无法打印此结果,因为它有 6.8×10^142142 digits 。但是:
>iter 2 (\x -> x * x) (<0) (10^6)
Left (24,Interrupted
这是一个很小的数字,大约只有 5,000,000 digits 。
关于haskell - Haskell 中具有部分结果的时间限制函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36431318/