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

[Bernie Pope]

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.