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

[Jefferson Heard]

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
> 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')
> Cheers,
> Bernie.
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe