[Haskell-cafe] Optimization of recursion

[Georg Martius]

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 <jgoerzen at complete.org> wrote:

> 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