[Haskell-cafe] Lazy evaluation and tail-recursion

[Daniel Fischer]

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 
consumed).

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.