[Haskell-cafe] Re: How do I get a long iteration to run in constant space

W M caeshmer at yahoo.com
Wed Oct 6 10:34:51 EDT 2004


I take it that the extra case always fails but forces
the arguments to be evaluated?  Nice trick.

Thanks!
--wgm

--- oleg at pobox.com wrote:

> 
> I added two lines to your code:
> 
> iterate2 f x n | seq f $ seq x $ seq n $ False =
> undefined
> iterate2 f x n = --- as before
> 
> rk4Next f h (x, y) | seq f $ seq h $ seq x $ seq y $
> False = undefined
> rk4Next f h (x, y) = -- as before
> 
> I also increased ten times the number of steps for
> the last iteration,
> to make the example more illustrative.
>    putStr (show (rk4 stiff 0 1 (exp (-1)) 1000000))
> 
> The rest of the code is unchanged. The program now
> runs on GHCi
> 
> *Foo> main
> Begin
> (1.0000000000000007,-6.503275017254139)
> (0.9999999999999062,-6.497717470015538)
> (1.000000000007918,-6.497716616653335)
> 
> 
> on on hugs
> 
> Begin
> (1.0,-6.50327501725414)
> (0.999999999999906,-6.49771747001554)
> (1.00000000000792,-6.49771661665334)
> 
> with the default stack size for both interpreters.
> It seems the code
> does run in constant space now.
> 
> The added lines are meant to turn the relevant
> functions from lazy to
> strict. When you see something like '(n-1)' and 'y +
> a1/6', it is a
> red flag. These are exactly the kinds of expressions
> that lead to
> memory exhaustion. Perhaps it is because the size of
> an unevaluated
> thunk for (n-1) is so much bigger than the size of
> the evaluated
> thunk. It seems that arithmetic expressions are the
> best candidates
> for some opportunistic evaluation...
> 



		
__________________________________
Do you Yahoo!?
Yahoo! Mail - Helps protect you from nasty viruses.
http://promotions.yahoo.com/new_mail


More information about the Haskell-Cafe mailing list