[Haskell-cafe] What's the best way to give up?

[Derek Elkins]

On Sat, 2008-09-06 at 12:17 -0400, David F. Place wrote:
> On Sat, 2008-09-06 at 11:10 -0400, Brandon S. Allbery KF8NH wrote:
> > On 2008 Sep 6, at 7:30, David F. Place wrote:
> > > Say I have a function solve which is a constraint solver.  It  
> > > reconfigures its input to be a solution.  If there is no solution,  
> > > it returns the input.
> > >
> > > solve :: a -> Either a a
> > > solve input output = maybe (Left input) Right $ solve' input
> > >
> > > If there is a solution, it finds it in a few seconds.  If there is  
> > > no solution, it goes away for days proving that.  So, I'd like to  
> > > give up on it if it doesn't return in a few seconds.
> > 
> > http://www.haskell.org/haskellwiki/Timing_out_computations
> > 
> 
> Thanks, Arnar, Christopher and Brandon.  I looked into all your
> suggestions.
> 
> I came up with this:
> 
> import Control.Exception
> import System.Timeout
> 
> apt :: Int -> (a -> a) -> a -> IO (Either a a)
> apt time f x =
>     do { ans <- timeout time $ evaluate (f x)
>        ; return $ maybe (Left x) Right ans
>        }
> 
> test x = sum [1..x]
> test2 x = length $ repeat x
> 
> Which seems to do what I want for test:
> 
> *Main> apt 100 test 100
> Right 5050
> *Main> apt 100 test 1000
> Right 500500
> *Main> apt 100 test 10000
> Right 50005000
> *Main> apt 100 test 100000
> Left 100000
> *Main> apt 100 test 1000000
> Left 1000000
> *Main> apt 100 test 10000000
> Left 10000000
> 
> 
> But, the following sets the cpu spinning and can't be interrupted.
> *Main> apt 100 test2 100

length (repeat x) doesn't require allocating any memory.  GHC only
performs a context switch at heap checks.  If there are no allocations,
there are no heap checks and therefore no context switches.