[Haskell-cafe] Optmiization of recursion
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