[Haskell-cafe] Lazy evaluation and tail-recursion

[Tillmann Rendel]

Hi,

Daniel Fischer wrote:
>>    data EvaluatedList a
>>
>>       =  Cons a (List a)
>>
>>       |  Empty
>>
>>     type List a
>>
>>       = () ->  EvaluatedList a
>>
>>     map :: (a ->  b) ->  (List a ->  List b)
>>     map f xs
>>
>>       = \_ ->  case xs () of
>>
>>                 Cons x xs  ->   Cons (f x) (\_ ->  map f xs ())
>>                 Empty      ->   Empty
>>
>> Here, the call to map is more visibly in tail position.
>
> According to the definition of tail recursion that I know, that's not tail
> recursive.

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.

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.


So I think that in a non-strict language like Haskell, we need to  
define "tail position" semantically, not syntactically.

   Tillmann