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