[Haskell-cafe] Strange memory consumption problems in something
that should be tail-recursive
jeff at renci.org
Tue Feb 13 16:49:22 EST 2007
Ha! You're right! I didn't think about the laziness aspect of it. Anyway,
the non tail-recursive version fixed the problem. Thanks!
On Tuesday 13 February 2007 16:32, Bernie Pope wrote:
> 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
> > input
> > 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
> 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')
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe