[Haskell-cafe] Flattening tail recursion?

[Jules Bean]

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.

See: http://www.haskell.org/hawiki/TailRecursive

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

Jules