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

[Isaac Dupree]

Tillmann Rendel wrote:
> Now consider a variant:
>
>    if' a b c = if a then b else c
>    variant x = if' (p x) (f x) (g x)
>
> I would say that if' has the same operational behavior as an
> if-then-else expressions, and therefore, (f x) and (g x) are still tail
> cails, even if they now appear in the context of another function call.

yes, and the if' is also a tail-call.  I guess I would say that (f x) and (g 
x) are tail-calls out of if' and if' is a tail-call out of variant.

> I think that a definition of tail calls in Haskell should take the
> strictness properties of functions into account.

sometimes the optimizer does this, and makes more functions behave like tail-
call than you'd expect! But sometimes it doesn't.

> And I think that this makes for a much more friendly migration path.
> Instead of telling people: "No, forget about tail calls, in Haskell, you
> need something else", you could tell them: "Yes, tail calls are the way
> to go, but in Haskell, they look different".

Sometimes you do need something different though... if you're *producing* a 
lazy data structure.

foldr f z (x:xs) = x `f` (foldr f z xs)
If "f" is ":" then this is an efficient non-tail-call
(later someone will demand the later parts of the list)
whereas
foldl f z (x:xs) = foldl f (z `f` x) xs
is tail-recursion, which means that it needs to traverse the whole input-list 
before producing *any* output

-Isaac