Hi, Yves Parès wrote:
A question recently popped into my mind: does lazy evaluation reduce the need to "proper" tail-recursion? I mean, for instance :
fmap f [] = [] fmap f (x:xs) = f x : fmap f xs
Here fmap is not tail-recursive, but thanks to the fact that operator (:) is lazy, I think that it may still run in constant space/time, am I right?
In a sense, that definition of fmap is tail-recursive. To see that, consider how a non-strict list could be encoded in a strict language: 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. So I would say that in Haskell, tail-call optimization is just as important as, for example, in Scheme. But tail positions are not defined syntactically, but semantically, depending on the strictness properties of the program. Tillmann