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

[Malcolm Wallace]

W M <caeshmer at yahoo.com> writes:

>                               I suppose in my ODE
> example it's building up expressions somewhere for
> lazy evaluation,

Exactly right.  The trick is spotting which expressions.  Until you
have some experience of likely causes, rather than guessing I can
recommend studying some heap profiles to learn what kind of values
are building up - e.g. are they closures for 'integrate' or for '+'?

Here are a couple of simple changes that seem to fix your space leak.

> iterate2 f x n = 
>     if n == 0 then
>       x 
>     else
>       iterate2 f (f x) (n - 1)

Try
        x `seq` iterate2 f (f x) (n - 1)
to ensure that the accumulator is holding simple values rather than
closures.

Also, currently you are building pairs lazily.  Making a strict pair
type helps:

        data Pair a = P !a !a

> integrate step f xInit xFinal yInit nSteps =
>     let
>       h = (xFinal - xInit) / fromIntegral nSteps
>       next = step f h
>     in
>       iterate2 next (xInit, yInit) nSteps

        iterate2 next (P xInit yInit) nSteps


> rk4Next f h (x, y) =
>     let
>       a1 = h * f x y
>       a2 = h * f (x + h/2) (y + a1/2)
>       a3 = h * f (x + h/2) (y + a2/2)
>       a4 = h * f (x + h) (y + a3)
>     in
>       (x + h, y + a1/6 + a2/3 + a3/3 + a4/6)

        P (x + h) (y + a1/6 + a2/3 + a3/3 + a4/6)


> rk4 = integrate rk4Next
> 
> stiff x y = -( ((exp (x - 1)) + (x - 1) * y)
> 	       / (1 - x - 0.0001 * y) )
> 
> main =
>     do
>       putStr "Begin\n"
>       putStr (show (rk4 stiff 0 1 (exp (-1)) 1000))
>       putStr "\n"
>       putStr (show (rk4 stiff 0 1 (exp (-1)) 10000))
>       putStr "\n"
>       putStr (show (rk4 stiff 0 1 (exp (-1)) 100000))
>       putStr "\n"