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

[Creighton Hogg]

On 2/13/07, Bernie Pope <bjpop at csse.unimelb.edu.au> wrote:
>
> Creighton Hogg wrote:
> > This may be silly of me, but I feel like this is an important point:
> > so you're saying that tail recursion, without strictness, doesn't run
> > in constant space?
>
> It is an important point, and a classic space bug (see foldl in the
> Prelude).
>
> It it not the fault of tail recursion per se, in fact tail recursion is
> often important in Haskell too.
>
> > 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 .....)
>
> in the second argument. It's size will be proportional to the number of
> recursive calls made (n).
> > You'll just be building a bunch of unevaluated thunks until you hit
> > the termination condition?
> >
>
> To fix it you will want the function to evaluate its second argument
> eagerly:
>
> facTail n n' = facTail (n-1) $! (n*n')


Awesome.
For a long time now I've been interested in Haskell, and studied it from the
math side, but haven't actually really written anything.  This mailing list,
the wiki, and #haskell are proving to be a great resource.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070213/d0103f92/attachment.htm