[Haskell-cafe] Lazy evaluation and tail-recursion

Daniel Fischer daniel.is.fischer at googlemail.com
Wed Mar 16 19:26:14 CET 2011

On Wednesday 16 March 2011 18:31:00, Yves Parès wrote:
> Hello,
> 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?

Yes, and a tail-recursive map couldn't run in constant space, as far as I 
can see (time is O(length) for both of course, if the result is compeltely 

Tail recursion is good for strict stuff, otherwise the above pattern - I 
think it's called guarded recursion - is better, have the recursive call as 
a non-strict field of a constructor.

More information about the Haskell-Cafe mailing list