[Haskell-cafe] Lazy evaluation and tail-recursion

[Tillmann Rendel]

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