Haskell函数超时问题

Question

import Math.NumberTheory.Primes (factorise)
import System.Timeout (timeout)
import Control.Monad (liftM)

type RetType = [(Integer, Int)] -- factorise's return type

-- proposed function
timedFact :: Integer -> Integer -> Either RetType Integer
timedFact u n = ?

尝试理解如何编写一个包装函数来对因数分解进行计时，如果成功，则返回RetType，否则返回Integer（传入的内容）。我对Haskell有点陌生。我知道超时需要在IO Monad中工作，但我无法将适当的结果带回。（注意：我不是非用Either不可，Maybe RetType也可以）。感谢任何帮助。

- user3424410

---

你可能也会感兴趣：http://hackage.haskell.org/package/speculation - jberryman

参见 Haskell 对计算时间的限制。 - Will Ness

Answer 1

看到类型 timeout :: Int -> IO a -> IO (Maybe a)，它可以被用作

import Math.NumberTheory.Primes (factorise)
import System.Timeout (timeout)
import Control.Exception (evaluate)
import Control.DeepSeq (force)

timedFact :: Int -> Integer -> IO (Maybe [(Integer, Int)])
timedFact u = 
      timeout u . evaluate . force . factorise 

测试：

 #> timedFact 3000000 1231231231223234234273434343469494949494499437141
Nothing
(3.04 secs, 2639142736 bytes)

 #> timedFact 4000000 1231231231223234234273434343469494949494499437141
Just [(1009,1),(47729236307,1),(125199345589541,1),(204202903382078984027,1)]
(3.07 secs, 2662489296 bytes)

更新：根据user2407038在评论中的说法（感谢！），

timedFact u n = timeout u (return $!! factorise n)

同样有效。 ($!!) 也来自于 Control.DeepSeq。引用文档中的话说，在表达式 f $!! x 中，x 在函数 f 应用之前被完全求值。

- Will Ness

---

@user2407038 参见 https://mail.haskell.org/pipermail/beginners/2010-April/004023.html - Will Ness

@user2407038，虽然evaluate x看起来很像return $! x，但事实证明它们之间存在重要但微妙的差别。这些差别足够微妙，以至于一些主要的GHC实现者都感到困惑；而这些差别又足够重要，以至于需要专门的seq# primop来正确定义evaluate。 - dfeuer

@WillNess @dfeuer return $!! factorise v 可以工作。然而，\u v -> timeout u $ return $ let r = factorise v in r \deepseq` r无法工作，等同于force (return r)。但是，\u v -> timeout u $ let r = factorise v in r `deepseq` return r可以工作且等同于return $!! r。evaluate` 真的是不必要的，但由于在调用 evaluate 时值已经被评估，我怀疑它是否有任何开销，因此它可能并不重要。 - user2407038

1. 你知道你可以删除评论吗？
2. 我强烈反对使用 unsafePerformIO。它之所以有“不安全”（unsafe）这个词，原因是有很大的风险。每当你使用它时，都应该提供证明，表明它不会引起问题。如果你无法做到这一点，那么你应该避免使用它，因为你很容易搞砸事情。只需像其他任何IO操作一样使用 timedFact 即可。

- Bakuriu

@user3424410 这里使用unsafePerformIO是不好的，因为没有理由相信运行纯计算两次会花费相同的时间（因此有可能第一次超时，第二次不超时或者反过来）。这里涉及到大量变量，包括：到目前为止强制执行了哪些thunks；哪些读取在缓存中命中，哪些没有命中；你的计算/看门狗线程如何与操作系统的调度器交互；以及许多其他变量。 - Daniel Wagner