时间限制函数,在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

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

更实际的例子可以是Newton-Raphson方法或梯度下降.

Answer 1

我认为将这些任务委托给具有比提供的更好的抽象能力的库是最简单的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位数字.然而:

>iter 2 (\x -> x * x) (<0) (10^6)
Left (24,Interrupted

这是一个只有大约5,000,000个数字的小数字.