[Haskell-cafe] Optimization of recursion
alastair at reid-consulting-uk.ltd.uk
Tue Sep 28 18:34:48 EDT 2004
> > 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  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
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.)
More information about the Haskell-Cafe