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