> Yes, and a tail-recursive map couldn't run in constant space

Yes, I meant "if you are consuming it just once immediately".

> the above pattern [...] is better, have the recursive call as a non-strict field of a constructor.

Which pattern? Mine or Tillman's? Or both?

2011/3/16 Daniel Fischer <daniel.is.fischer@googlemail.com>
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.