Hi,
I am also looking for this kind of information in general, however I have done some investigations that answer some of you questions. I posted a question on this kind of optimisation recently [1], but it kept unanswered.
On Tue, 28 Sep 2004 18:10:11 +0000 (UTC), John Goerzen
Hello,
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? ghc does it with one of -O -O1 -O2 switches. hugs doesn't seam to do it since [2] says that foldl (\n _ -> n + 1) 0 [1..100000] causes a stack overflow.
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? Not really, on the stacksize you give the RTS, however you are limited by the memory anyway. See ghc +RTS --help
3. Does it make a difference for optimization purposes whether a particular recursive function is tail-recursive? As far as I know it is crucial for loop optimisation since without tail recursion there is theoretically no way of transforming the code to an iteration. (without a stack of any kind).
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 isn't.) To my knowledge it is missing. foldl is tail recursive and foldr isn't.
5. Are there any examples/patterns anywhere that illustrate standard tail-recursion practice in Haskell? See [3].
[1] http://www.haskell.org//pipermail/haskell/2004-September/014533.html [2] http://cvs.haskell.org/Hugs/pages/bugsandfeatures.htm [3] http://haskell.org/hawiki/TailRecursive?action=highlight&value=tail+recursion Georg