[Haskell-cafe] Flattening tail recursion?
Benjamin.Rudiak-Gould at cl.cam.ac.uk
Fri Dec 10 10:47:00 EST 2004
>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.
More information about the Haskell-Cafe