[Haskell-cafe] Strange memory consumption problems in something
that should be tail-recursive
wchogg at gmail.com
Tue Feb 13 16:45:17 EST 2007
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
> 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
> facTail n n' = facTail (n-1) $! (n*n')
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...
More information about the Haskell-Cafe