Haskell - 有没有办法限制给定函数的执行时间？

Question

假设我在 Haskell 中有一个可能不会总是终止的函数。如果计算时间过长，有没有办法让程序自行停止？

例子:

import qualified Data.Map as Map

walkmap :: Int -> Map.Map Int Int -> Int
walkmap x m = case Map.lookup x m of
  Nothing -> x
  Just y -> walkmap y m

main :: IO ()
main = do
  let ma = Map.fromList [(0,1), (1,2)]
  let mb = Map.fromList [(0,1), (1,0)]
  print $ walkmap 0 ma
  print $ walkmap 0 mb

walkmap ma 0 应该立即返回 2，但 walkmap mb 0 将永远循环。我知道无法确定函数是否会停止，我想知道是否有办法为该计算设置时间限制(例如 10 秒)。

Answer 1

问题的答案如下所示:

timeout (10*1000000) (evaluate (walkmap 0 mb)) >>= print

但背后的“避免查找循环”问题的答案是布伦特非凡的 tortoise and hare algorithm . (请注意!我只在您的两个测试用例上测试了此代码。其中可能潜伏着错误。您应该阅读链接背后的算法并自己进行代码审查(或重新实现)。)

walkmap :: Ord a => a -> Map.Map a a -> Maybe a
walkmap a m = case Map.lookup a m of
    Nothing -> Just a
    Just a' -> go a a' (iterate (2*) 1)
    where
    -- p for pause
    go a a' ps | a == a' = Nothing
    go a a' (p:ps) = case Map.lookup a' m of
        Nothing -> Just a'
        Just a''
            | p == 0 -> go a' a'' ps
            | otherwise -> go a a'' (p-1:ps)