[Haskell-cafe] Strange memory consumption problems in something
that should be tail-recursive
bjpop at csse.unimelb.edu.au
Tue Feb 13 16:32:38 EST 2007
Creighton Hogg wrote:
> On 2/13/07, *Duncan Coutts* <duncan.coutts at worc.ox.ac.uk
> <mailto:duncan.coutts at worc.ox.ac.uk>> wrote:
> On Tue, 2007-02-13 at 15:27 -0500, Jefferson Heard wrote:
> > Hi, I am running the following code against a 210 MB file in an
> attempt to
> > determine whether I should use alex or whether, since my needs
> are very
> > performance oriented, I should write a lexer of my own. I
> thought that
> > everything I'd written here was tail-recursive
> Isn't that exactly the problem - that it's tail recursive? You do not
> want it to be tail recursive since then it must consume the whole
> before producing any output. You want it to be as lazy as possible so
> that it can start producing tokens as soon as possible without
> having to
> consume everything.
> 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
(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')
More information about the Haskell-Cafe