16 Mar
2011
16 Mar
'11
2:26 p.m.
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.