[Haskell-cafe] Lazy evaluation and tail-recursion

Tillmann Rendel rendel at informatik.uni-marburg.de
Wed Mar 16 19:19:48 CET 2011


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 

   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.


More information about the Haskell-Cafe mailing list