[Haskell-cafe] How do I get a long iteration to run in constant
space
Malcolm Wallace
Malcolm.Wallace at cs.york.ac.uk
Mon Oct 4 11:37:30 EDT 2004
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"
More information about the Haskell-Cafe
mailing list