[Haskell-cafe] Flattening tail recursion?
jules at jellybean.co.uk
Fri Dec 10 10:35:18 EST 2004
On 10 Dec 2004, at 15:06, GoldPython wrote:
> I'm missing something, a functional idiom, whatever. I know there's
> "length" to count the elements in a list and it works fine, but the
> function below stack overflows on a large list.
> countLines  = 0
> countLines (_:ls) = 1 + countLines ls
> I would have thought that this was tail recursive and would be
> flattened into iteration by the compiler. Can anyone explain why? Is
> it because the call is embedded in an expression?
If you write it in prefix form:
countLines (_:ls) = (+)(1,countLines ls)
...you can see that it is not tail recursive. Tail recursive means that
the result of the function *is* the result of the recursive call. The
technique you have to use to make functions like this tail recursive is
to pass along an accumulating parameter.
The textbook answer to your problem is something like this:
countLines l = countLines' 0 l
where countLines' n  = n
countLines' n (_:ls) = countLines' (n+1) ls
More information about the Haskell-Cafe