[Haskell-cafe] Lazy evaluation and tail-recursion

[Yves Parès]

> 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 at 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110316/90b6f49c/attachment.htm>