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 abilityif they answer was no, perhaps that would be the case, but with lazyness things get weird.
to handle very large lists in recursive functions is limited by the
maximum stack size on my system?
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 ayes, in a tail recursive call you can reuse your stack frame, so the call becomes simply
particular recursive function is tail-recursive?
a jump (i.e. you get a loop).
4. Is a reference available documenting which Prelude/standard functionsi am not sure if there is such a thing, but one can often guess.
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.)
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 standardi'd imagine these would be much the same as in o'caml. a common functional programming pattern when you get tail recursion is
tail-recursion practice in Haskell?
to rewrite a function using an accumulator (i.e. a bit of local state).
hope this helps -iavpr
_______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
