Haskell - Is there a way to limit the execution time for a given function?

user_9781480 0
Viewed 229

Suppose I have a function in Haskell which may not always terminate. Is there a way to make the program halt itself if it's taking too long to compute?

Example:

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 should return 2 right away, but walkmap mb 0 would loop forever. I know it's impossible to know for sure if the function would halt or not, what I'd like to know is if there's a way to set a time limit (say, 10 seconds) for that computation.

haskell
1 Answers

The answer to the question as asked looks like this:

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

But the answer to the "avoid cycles in a lookup" question that's behind it is Brent's remarkable tortoise and hare algorithm. (Beware! I have only tested this code on your exact two test cases. There could be bugs lurking in it. You should read about the algorithm behind the link and code review (or re-implement) it yourself.)

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)
user_7916040
Related