[Haskell-cafe] Optmiization of recursion

[Fergus Henderson]

On 28-Sep-2004, John Goerzen <jgoerzen at complete.org> wrote:
> As I'm investigating Haskell, it's occured to me that most of the
> Haskell tutorials out there have omitted something that was quite
> prominent in the OCaml material I had read: making functions properly
> tail-recursive.
> 
> The OCaml compiler was able to optimize tail-recursive functions such
> that they could be compiled using a loop.  This would achieve two main
> benefits: performance due to not needing to allocate/deallocate stack
> frames, and the ability to work on very large lists since each recursive
> call did not consume extra stack space.
> 
> So I have several questions about Haskell:
> 
> 1. Do Haskell interpreters/compilers perform similar optimizations?

Yes.  However, laziness has a major effect on space usage and on
the applicability and importance of tail call optimization.

> 4. Is a reference available documenting which Prelude/standard functions
> are properly tail-recursive (and thus suitable for very large lists) and
> which are not?

No.  But the source code is available...

If analyzing the performance and space usage of your programs is important,
then Haskell may not be the best choice of language.

-- 
Fergus J. Henderson                 |  "I have always known that the pursuit
Galois Connections, Inc.            |  of excellence is a lethal habit"
Phone: +1 503 626 6616              |     -- the last words of T. S. Garp.