[Haskell-cafe] Flattening tail recursion?

[Ben Rudiak-Gould]

GoldPython wrote:

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

This is not tail recursive as written. SICP section 1.2.1 does a good
job of explaining how to tell the difference:

    http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1

The analysis in Haskell is a bit different in general because reductions
are applied in a different order, but in this case it's exactly the same.

Some compilers might indeed optimize your code into a tail-recursive
version, but there's a catch: the optimization depends on the
commutativity and associativity of (+), which doesn't hold for arbitrary
types in Num. Try giving countLines an explicit type signature like
([a] -> Int) and see if that helps.

-- Ben