On Wednesday 16 March 2011 21:44:36, Tillmann Rendel wrote:
My point is that the call to map is in tail position, because it is the last thing the function (\_ -> map f xs ()) does. So it is not a tail-recursive call, but it is a tail call.
Mmmm, okay, minor terminology mismatch, then. Makes sense, but is not what I'm used to. I'd say it is a tail-call of Cons's second argument, and the tail call of map would be Cons, so tail-call is not transitive.
Of course, (\_ -> map f xs ()) does not occur literally in the Haskell implementation of map, but the runtime behavior of the Haskell implementation of map is similar to the runtime behavior of the code above in a strict language.
Let's look at the following code:
countdown n = if n == 0 then 0 else foo (n - 1)
s/foo/countdown/ presumably
if' c t e = if c then t else e countdown' n = if' (n == 0) 0 (foo (n - 1))
s/foo/countdown'/
countdown is clearly tail-recursive. Because of Haskell's non-strict semantics, countdown and countdown' have the same runtime behavior. I therefore submit that countdown' is tail-recursive, too.
Formally, not according to the previously mentioned definition, but in terms of generated code/runtime behaviour, of course, so
So I think that in a non-strict language like Haskell, we need to define "tail position" semantically, not syntactically.
I think you're right.
Tillmann
Cheers, Daniel