[Haskell-cafe] Re: Debunking tail recursion

[Jon Fairbairn]

Ilya Tsindlekht <eilya497 at 013.net> writes:

> On Sat, May 19, 2007 at 09:16:46PM +0100, Jon Fairbairn wrote:
> > Ilya Tsindlekht <eilya497 at 013.net> writes:
> > > By definition, tail recursive function is recursive function in which
> > > the value returned from a recursive call is immediately returned without
> > > modification as value of the top-level invocation, which is true for
> > > foldl defined as above.
> > 
> > Sure. Did I say otherwise?
> Sorry, I thought you were saying foldl is not tail-recursive. I must
> have not read your message carefully enough, mea culpa.

No worries.  I was, in fact, saying that in a lazy language
more things are tail recursive than you might expect, owing
to the possibility of defining choice functions other than
if and case.  One might even argue that the question of
whether something is tail recursive (in effect) depends on
the context:

> down 0 = []
> down n = n:down (n-1)

is clearly not tail recursive: the tail call is to (:), but
if the context only ever applies either head or tail, (:) is
effectively a choice...

> silly [] = []
> silly (x:xs) = silly xs

clearly is, now silly (down n) only ever applies tail to the
conses, so no state builds up, so the combined effect of the
two functions is as if they were tail recursive.


-- 
Jón Fairbairn                                 Jon.Fairbairn at cl.cam.ac.uk