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