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

Tillmann Rendel rendel at cs.au.dk
Sat Mar 28 08:40:32 EDT 2009

```Brent Yorgey wrote:
>> What, strictly speaking, is the definition of ”tail recursive” as opposed to
>> just “recursive”?
>
> A recursive function is tail recursive if the final result of the
> recursive call is the final result of the function itself.  If the
> result of the recursive call must be further processed (say, by adding
> 1 to it, or consing another element onto the beginning of it), it is
> not tail recursive.
>
> With that said, tail recursion is not that useful of a concept in a

What, non-strictly speaking, is the definition of "tail call" in Haskell
as opposed to an eager language?

For example in the following ML code,

fun eager x = if p x then f x else g x

both (f x) and (g x) are clearly tail calls, even if they appear in the
syntactic context of the if-then-else expression. However, (p x) is
clearly not a tail call. We can understand this by taking the
operational behavior of the if-then-else expression into account: (p x)
is evaluated first, then either the result of evaluating (f x), or the
result of evaluating (g x) is returned without further processing.

Now consider the same example in Haskell:

lazy x = if p x then f x else g x

Haskell's if-then-else expression has the same operational behavior as
ML's, so again, (f x) and (g x) are tail calls.

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.

I think that a definition of tail calls in Haskell should take the
strictness properties of functions into account. Such Haskell tail calls
would have the same nice properties as tail calls in an eager language,
but they would reflect that fact that it is hard to analyse strictness