# [Haskell-beginners] IO loops with tail call

Daniel Fischer daniel.is.fischer at web.de
Wed Nov 10 13:53:18 EST 2010

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.