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

Bernie Pope 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
>     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

> 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
> 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.

```