[Hugs-users] Avoiding use of the stack

[eoin.mcdonnell at lineone.net]

Hi Scott,

Thanks for your insight on this one. My test routines now work, and I now
have a better understanding of this aspect of Haskell.

Best regards,
        Eoin

-----Original Message-----
From: Scott Turner [mailto:p.turner at computer.org]
Sent: 18 November 2004 16:32
To: hugs-users at haskell.org
Cc: eoin.mcdonnell at lineone.net
Subject: Re: [Hugs-users] Avoiding use of the stack


On 2004 November 18 Thursday 06:15, eoin.mcdonnell at lineone.net wrote:
> how to write recursive functions
> so that they don't eat up stack space, and instead behave more like while
> loops (I think you had to convert them to tail-recursive forms?).

> testR2 :: Integer -> Integer
> testR2 n = testR2' 0 n
> testR2' :: Integer -> Integer -> Integer
> testR2' a 0 = a
> testR2' a n = testR2' (a+n) (n-1)

You're on the right track.  This is properly tail recursive. The remaining

problem is that the argument (a+n) does not get evaluated during the 
processing of testR2'.  So each successive call to testR2' is passed a larger

expression such as
    testR2' (((((0+10)+9)+8)+7)+6) (6-1)
Pattern matching causes the second argument to be evaluated.
To ensure that the first argument is processed, you can use the $! operator.
    testR2' a n = (testR2' $! (a+n)) (n-1)
which evaluates (a+n) before passing it to testR2'.

Where you see stack overflow, it's actually a stack of + opeations rather
than 
a stack of testR2' calls.


__________________________________________________________________

INTRODUCTORY OFFER! Tiscali Business Broadband for £15.99!

http://www.tiscali-business.co.uk/broadband/?code=ZZ-MS-12KC