[Haskell-cafe] Re: Debunking tail recursion

[Jon Fairbairn]

"David House" <dmhouse at gmail.com> writes:

> On 18/05/07, Albert Y. C. Lai <trebla at vex.net> wrote:
> > Lazy evaluation says, to evaluate x, call f first, then x is the last
> > call.
> 
> x may be the last to be evaluated, but you still have to pass through
> f's call context 'on the way out'.

Not exactly, or, only if it has some...

> Let's have one more example to explain what I mean by 'call stack'.
> The classic tail recursive function is foldl, contrasting with the
> non-tail recursive function foldr. Equations from both these functions
> are shown below, with their right-hand sides transformed into a tree
> (ASCII art: don't use a proportional font):
> 
> foldl f z (x:xs) = foldl f (f z x) xs
> 
> foldl-+--+-----+
>       |  |     |
>       f  f--+  xs
>          |  |
>          z  x
> 
> foldr f z (x:xs) = f x (foldr f z xs)
> 
> f-+--+
>   |  |
>   x  foldr-+--+--+
>            |  |  |
>            f  z  xs
> 
> Tail recursion, then, expresses the idea that a function appears at
> the top of its call stack, or at the top of the tree of its right-hand
> side. It's got nothing to do with evaluation order.

Well, I'd rather have it a different way.  The simplest tail
recursion is the head function in the expression (the
recursion is a/the tail call) -- so in

> foldl f z (x:xs) = foldl f (f z x) xs

it's easy to see that foldl is a tail call and therefore
tail recursion, because it's the leftmost outermost
function. Whether or not (f z x) is evaluated strictly, the
body of foldl doesn't have to do anything after the call to
foldl. In strict evaluation you would evaluate (f z x)
before calling foldl, and in lazy evaluation you just make a
representation of (f z x), but in either case you pass this
as an argument to the tail function and just go. Some of the
confusion here is that the left hand side of the definition
actually does some work, so the notation handily obscures
the fact that foldl isn't such a straightforward tail
call. It's actually something like:

> foldl f z l = case l of
                (x:xs) -> foldl f (f z x) xs
                [] -> z

which reveals that foldl in the RHS isn't really the
leftmost outermost function, but case is -- the tail call is
to case. It happens that case is a kind of function that
makes a choice -- it returns one of its arguments but
doesn't do anything more to it. In a strict language only
some predefined operators like case and if have this
property, but lazy languages allow the definition of new
ones, which is why we need more care when thinking about
tail calls.

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