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

[Lennart Augustsson]

You are absolutely right.  The concept of tail call is not quite as
easy to define in Haskell as some people seem to think.
It is, after all, an operational concept.

In your example
>  if' a b c = if a then b else c
>  variant x = if' (p x) (f x) (g x)
the variant function tail calls if', and if' tail calls b or c.
So in a transitive sense variant tail calls (f x) or (g x).

  -- Lennart

On Sat, Mar 28, 2009 at 12:40 PM, Tillmann Rendel <rendel at cs.au.dk> wrote:
> 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
>> lazy language like Haskell.
>
> 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 in
> Haskell.
>
> 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".
>
>    Tillmann
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>