haskell - Haskell 中具有部分结果的时间限制函数

Question

给出了初始值(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

我希望第二次调用返回部分计算结果。有简单的方法吗？

更实际的例子可以是牛顿-拉夫森方法或梯度下降。

Answer 1

我认为最简单的方法是将此类任务委托(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 。