Re: [Haskell-cafe] Definition of "tail recursive" wrt Folds
On Wed, Mar 25, 2009 at 05:54:17PM +1030, Mark Spezzano 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. The important concept to know in Haskell is 'guarded recursion', where any recursive calls occur within a data constructor (such as foldr, where the recursive call to foldr occurs as an argument to (:)). This allows the result of the function to be consumed lazily, since it can be evaluated up to the data constructor and the recursive call delayed until needed. -Brent
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
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
if' a b c = if a then b else c variant x = if' (p x) (f x) (g x)
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
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
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (4)
-
Brent Yorgey -
Isaac Dupree -
Lennart Augustsson -
Tillmann Rendel