[Haskell-beginners] IO loops with tail call

[edgar klerks]

Thanks for your clear explanation. I understand the role of laziness now.

On Wed, Nov 10, 2010 at 7:53 PM, Daniel Fischer <daniel.is.fischer at web.de>wrote:

> On Wednesday 10 November 2010 18:25:37, edgar klerks wrote:
> > Hi Yasuyuki,
> >
> > I must admit, It is not clear to me. But I think a reference to the head
> > of the list is somehow used as an argument to the recursive function,
> > which adds the next value to the list. So that it is tail-recursive
> > again. Or something like that.
>
> One point is that a tail-recursive function can't deliver anything until it
> has reached the end of the recursion, but laziness allows to deliver
> partial results before that (not always, however; sum :: [Int] -> Int needs
> to traverse the entire list, so there's a point where tail-recursion [with
> a strict accumulator] is the way to go).
>
> Consider
>
> map :: (a -> b) -> [a] -> [b]
> map f [] = []
> map f (x:xs) = f x : map f xs
>
> Not being tail-recursive, it can deliver its result (almost) immediately.
> The result is a constructor, (:), applied to two thunks. If the caller
> consumes the result appropriately, the computation can run in constant
> space.
> The important thing is that the recursive call is in a lazy argument
> position of the overall result, so the recursion may end prematurely if the
> caller doesn't need the full result.
>
> If you define map with a tail-recursive worker, the entire result list has
> to be constructed before the caller can inspect any of it, so it would
> require at least O(length list) space - particularly wasteful if the caller
> is "take k" for sufficiently small k and doesn't work at all on infinite
> lists.
>
> Tail-recursion has its uses in Haskell, but since Haskell's evaluation
> model is different from e.g. Lisp's, it's not so important. As a catch-
> phrase: "(non-tail-)recursion doesn't eat stack frames in Haskell".
>
> >
> > But I may also be completely off.
> >
> > Greets,
> >
> > Edgar
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20101110/b123dc5c/attachment.html