Thanks for your clear explanation. I understand the role of laziness now. <br><br><div class="gmail_quote">On Wed, Nov 10, 2010 at 7:53 PM, Daniel Fischer <span dir="ltr">&lt;<a href="mailto:daniel.is.fischer@web.de">daniel.is.fischer@web.de</a>&gt;</span> wrote:<br>

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