[Haskell-cafe] Flattening tail recursion?

Ben Rudiak-Gould Benjamin.Rudiak-Gould at cl.cam.ac.uk
Fri Dec 10 10:47:00 EST 2004

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:


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

More information about the Haskell-Cafe mailing list