[Haskell-cafe] Flattening tail recursion?

[Robert Dockins]

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