Robert Dockins robdockins at fastmail.fm
Fri Dec 10 10:34:45 EST 2004

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

This function isn't tail recursive, because you do additional operations
to the result of the function call.  The following is tail recursive:

countlines = aux 0
where aux x []     = x
aux x (_:ls) = aux (x+1) ls

So it should get "flattened," but it still doesn't run in constant space
because the "x" parmeter isn't strict, so it will accumulate a bunch of
closures like (((((((0)+1)+1)+1)+1)+1).... To make it strict, do
something like this:

countlines = aux 0
where aux x [] = x
aux x (_:ls)
| x `seq` False = undefined
| otherwise     = aux (x+1) ls

The `seq` causes the x to be evaluated, so it should run in constant space.

As to predicting, I think that if the function is actually tail
recursive and any accumulating parameters are strict, the function will
run in constant space.