[Haskell-cafe] Optmiization of recursion

John Goerzen jgoerzen at complete.org
Tue Sep 28 14:10:11 EDT 2004


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

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?

2. If the answer to 1 is No, then am I correct in saying that my ability
to handle very large lists in recursive functions is limited by the
maximum stack size on my system?

3. Does it make a difference for optimization purposes whether a
particular recursive function is tail-recursive?

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?  (OCaml system docs generally specify when a function is
not tail-recursive... for instance, one of foldr/foldl is and the other

5. Are there any examples/patterns anywhere that illustrate standard
tail-recursion practice in Haskell?


More information about the Haskell-Cafe mailing list