[Haskell-cafe] Optimization of recursion
mai99dgf at studserv.uni-leipzig.de
Tue Sep 28 15:17:57 EDT 2004
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 , but it kept unanswered.
On Tue, 28 Sep 2004 18:10:11 +0000 (UTC), 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
> 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  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
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?
More information about the Haskell-Cafe