[Haskell-cafe] Re: MonadFix

Joost Behrends webmaster at h-labahn.de
Thu Dec 20 19:37:49 EST 2007


Albert Y. C. Lai <trebla <at> vex.net> writes:

> Theoretically the recursions in
> 
>      oddFactors k n | otherwise = oddFactors (k+2) n
> 
> and
> 
> (*) divisions y |divisor y <= bound y = divisions (divstep y)
> 
> do not cost stack space. They are tail recursions too!
> 
> In general similar tail recursions do not cost stack space. Some 
> programs using them use a lot of stack space, but that is because of 
> non-strictness, not because of tail recursion itself. And such 
> non-strictness is absent here due to the way the parameters have to be 
> evaluated for all sorts of decisions before further recursive calls.


Thanks for all that benchwork (and especially your exponent 61). I must admit,
that i ran the (*) version in ghci only (not having compiled it 
to a standalone version). Maybe ghci is configured wrongly on my system. 
As i remember, i tried (*) twice, coming near to memory exhaustion 
and not awaiting the result. I would really like a non-monadic version. 

What is interesting also is how near your 19 minutes came to my 17 
(Windows XP, 2.2GHZ, 512MB). And the comparations to Daniels code 
seem to imply, that my named fields in DivIter are 
not very expensive, if at all.

Is there documentation of tail recursion anywhere ? I searched
(googling with site:www.haskell.org) and didn't find anything else 
than entries in mailing lists.

Cheers, Joost






More information about the Haskell-Cafe mailing list