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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
