[Haskell-cafe] Definition of "tail recursive" wrt Folds
Isaac Dupree
ml at isaac.cedarswampstudios.org
Sat Mar 28 09:44:05 EDT 2009
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
More information about the Haskell-Cafe
mailing list