tail recursion (was Re: Need some help please)

Elke Kasimir elke@espresto.com
Thu, 28 Aug 2003 12:11:01 +0200 (CEST)


On 27-Aug-2003 Nick Name wrote:
> -- First of all, a simple auxiliary function, so everything is 
> -- tail recursive
> 
> safetailaux :: [b] -> ([b] -> Int) -> [b]

Apropos "tailrecursive": I have the following question in mind
for some time: Rabhi/Lapalmes book about functional-styled
algorithms mention a version of tail-recursion-optimization which
relies on the availability of tail recursion elimination in
Haskell compilers and interpreters. Does the notion "tail recursion
elimination" mean something at all in the context of Haskell? For
example:

copyList (x:xs) = x : copyList xs

is surely not tail-recursive in the traditional sense, but I think
that most Haskell programmers  take it for granted that it runs in
constant stack space.

Behind this there is a more general question concerning stack space
complexity: Assuming primitive graph-reduction, the stack size (which
holds pointers to strict functions whose arguments are under evaluation,
if I remember things right) is bounded by the heap size. Does this
estimation carry over to all current Haskell implementations, or is there
need to pay special attention to stack size?
 
Best,
Elke.

Software Development                                  EsPresto AG 
----------------------------------------------------------------- 
kasimir@espresto.com                            Breite Str. 30-31
Tel/Fax: +49-30-90 226-750/-760              10178 Berlin/Germany