[Haskell-cafe] Lazy evaluation and tail-recursion

[Daniel Fischer]

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