> 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 <[email protected]> > 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. >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
