[Haskell-cafe] Lazy evaluation and tail-recursion
daniel.is.fischer at googlemail.com
Wed Mar 16 22:35:09 CET 2011
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)
> if' c t e = if c then t else e
> countdown' n = if' (n == 0) 0 (foo (n - 1))
> 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.
More information about the Haskell-Cafe