[Haskell-cafe] Optmiization of recursion

[Iavor S. Diatchki]

hello,

John Goerzen 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?
>  
>
yes they do.  most functional language compilers do this sort of thing.


>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?
>  
>
if they answer was no, perhaps that would be the case, but with lazyness 
things get weird.
may experience is that it is somehow a lot easier for me to run out of 
space when writing
ML programs (this could be because i probably think in Haskell).  the 
reason is that
in ML sometimes things get evaluated, when in haskell you would simply 
acllocate a closure on the heap.
OTOH there are a few classical cases in haskell where you run out of 
space even if you have a tail
recursive function: e.g.
sum n [] = n
sum n (y:ys) = sum (n + y) ys
the reason for this that the n+y expression never gets evaluated until 
the very end,
so you create many suspensions in memory. 

>3. Does it make a difference for optimization purposes whether a
>particular recursive function is tail-recursive?
>  
>
yes, in a tail recursive call you can reuse your stack frame, so the 
call becomes simply
a jump (i.e. you get a loop).

>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.)
>  
>
i am not sure if there is such a thing, but one can often guess.
for the record, foldl is the tail recursive one (it captures the pattern 
of traversing a list with an acumulator)
while foldr is not.

>5. Are there any examples/patterns anywhere that illustrate standard
>tail-recursion practice in Haskell?
>  
>
i'd imagine these would be much the same as in o'caml. 
a common functional programming pattern when you get tail recursion is
to rewrite a function using an accumulator (i.e. a bit of local state).

hope this helps
-iavpr