[Haskell-cafe] Lazy evaluation and tail-recursion
rendel at informatik.uni-marburg.de
Wed Mar 16 21:44:36 CET 2011
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
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.
More information about the Haskell-Cafe