[Haskell-cafe] Re: Definition of "tail recursive" wrt Folds

[Ben Franksen]

Mark Spezzano wrote:
> Just looking at the definitions for foldr and foldl I see that foldl is
> (apparently) tail recursive while foldr is not.
> 
> Why?
> 
> Is it because foldl defers calling itself until last whereas foldr
> evaluates itself as it runs?
> 
> What, strictly speaking, is the definition of ”tail recursive” as opposed
> to just “recursive”?

An application of some function f inside another function g is in 'tail
position' (or a 'tail call') if the result of applying f is the result of
g. Operationally speaking, calling f is the very last thing g does. Tail
calls can be optimized by a compiler (or interpreter) so that the call does
not use additional stack; that is, the call can be replaced by a jump.

A function is called ”tail recursive” (as opposed to just “recursive”) if
the recursive call to itself is in tail position. If the compiler performs
tail call optimization, tail recursive functions can work with constant
stack space, similar to a (imperative) loop.

Looking at a definition of foldl, e.g.

foldl f z0 xs0 = lgo z0 xs0 where
  lgo z []     =  z
  lgo z (x:xs) = lgo (f z x) xs

you see that lgo calls itself in tail position, thus is tail recursive. In
contrast, foldr can be defined as

foldr k z xs = go xs where
  go []     = z
  go (y:ys) = y `k` go ys

where you see that the result of go is not the recursive call to go.
Instead, the result is  y `k` go ys . Thus, foldr is not tail recursive.

So, if you are saying that "foldl defers calling itself until last whereas
foldr evaluates itself as it runs" then you got the right idea, I think.
The point is that foldr still needs to do something (namely to apply  (y
`k`)) to the result of applying itself. It needs to remember to do so, and
thus the stack grows linearly with the size of the list.

Cheers
Ben