Haskell——强制使用奇怪的递归类型进行严格评估

Question

我previously问了一个关于如何强制严格评估以创建超时的问题。大多数时候使用 seq/$! 就足够了，deepseq 适用于任何属于 NFData 的成员>，但是如果我们使用奇怪的递归类型呢？假设我们有以下内容:

import Control.DeepSeq
import Control.Monad.Random
import Data.Maybe
import System.Timeout

newtype A = A { runA :: A -> Int -> Rand StdGen Bool }

-- a call to runA with this as the first input will always terminate
example1 :: A
example1 = A (\_ i -> (if i > 0 then getRandomR (True, False) else return False))

-- a call to runA with this as the first input will never terminate
example2 :: A
example2 = A (\_ _ -> runA example2 example2 0)

-- here it depends on the other input 
-- will terminate with example1, not with example2 or 3
example3 :: A
example3 = A (\a _ -> runA a a 0)

我们能否编写一个超时函数来确定 A 类型的某些值 x 是否会在我们调用 runA x x 0< 时在给定的时间内终止？我们可以像这样尝试使用 seq:

testTimeout :: A -> IO (Maybe Bool)
testTimeout x = timeout 1000 . evalRandIO $! runA x x 0

但是，这对 example2 和 example3 不起作用，因为对 runA 的调用被评估为 WHNF，但随后挂起，因为计算永远不会完成。用 deepseq(即 $!!)尝试同样的事情甚至不会编译，因为我们需要 Rand 的 NFData 实例StdGen Bool。那么，我们如何实现这个实例，以便严格评估/超时按预期工作？还是有其他方法可以做到这一点？

Answer 1

timeout 似乎只是在一定时间内执行操作，而不评估结果。它不评估生成的内部。没关系。如果我们使用

(>>= (return $!)) :: Monad m => m a -> m a

如您所知，return 会创建一个 m a 类型的值。通过执行 return $!，我们表示我们不会生成 m a，因此在计算结果之前完成操作。这是一个更详细的函数。

evalM m = do
    result <- m
    result `seq` return result

您也可以使用 NFData 执行此操作(这对于 Bool 不是必需的，但如果您使用 [a] 代替)，您可以执行以下操作:

(>>= (return $!!)) :: (Monad m, NFData a) => m a -> m a

更详细地说:

forceM m = do
    result <- m
    result `deepseq` return result