[Haskell-cafe] Optimization of recursion

[Alastair Reid]

> > 1. Do Haskell interpreters/compilers perform [tail call optimization]?

Georg Martius wrote:
> 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.

All Haskell compilers (including Hugs) perform tail call optimizations.
That is, tail calls are compiled as jumps (or equivalent).

This is absolutely necessary (and, incidentally, easy) because the only way to 
write a loop in Haskell is to write a recursive function.  If recursive 
functions consumed more and more stack space with each iteration, it wouldn't 
be possible to write programs that ran for any length of time or did anything 
interesting.

The problem Georg describes is _not_ due to how tail calls are implemented.  
It is a property of lazy evaluation that you have to learn about just as 
someone used to Haskell has to learn not to write the equivalent of [0..] in 
OCaml.  (For those who don't know Haskell, "[0..]" denotes the infinite list 
of natural numbers and would quickly exhaust your memory if you tried to use 
it in a strict language.)

--
Alastair Reid