[Haskell-cafe] Strange memory consumption problems in something that should be tail-recursive

Sven Panne sven.panne at aedion.de
Fri Feb 16 09:16:36 EST 2007


On Tuesday 13 February 2007 22:32, Bernie Pope wrote:
> Creighton Hogg wrote:
> [...]
> > So for example in the case of,
> > facTail 1 n' = n'
> > facTail n n' = facTail (n-1) (n*n')
>
> The problem with this example is that it will build up an expression of
> the form:
>
>    (n1 * n2 * n3 .....)
> [...]

This is not true if one takes strictness analysis into account: facTail is 
strict in both arguments, and any decent strictness analyser will detect 
this, e.g. GHC with -O. Strict arguments can be evaluated before the function 
call, so in the example above no stack space will be consumed and the above 
will basically be a good old loop.

For the brave: Use "ghc -v4 -O" on the example above to see what really 
happens. GHC is even clever enough to factor out (un-)boxing (at least for 
Int and friends), so there is a rather tight loop with unboxed Ints.

Cheers,
   S.


More information about the Haskell-Cafe mailing list