Creighton Hogg wrote:
On 2/13/07, *Duncan Coutts* <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> 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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
