&gt; And that&#39;s what, to my knowledge, is impossible with tail recursion. A tail<br>
&gt; recursive map/fmap would have to traverse the entire list before it could return anything.<br><br>Now that you say it, yes, you are right. Tail recursion imposes strictness, since only the very last call can return something.<br>

<br>Can a type signature give you a hint about whether a function evaluates some/all of its arguments (i.e. is strict/partially strict/lazy), or do you have to look at the implementation to know?<br><br><br><div class="gmail_quote">

2011/3/16 Daniel Fischer <span dir="ltr">&lt;<a href="mailto:daniel.is.fischer@googlemail.com">daniel.is.fischer@googlemail.com</a>&gt;</span><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 16 March 2011 20:02:54, Yves Parès wrote:<br>
&gt; &gt; Yes, and a tail-recursive map couldn&#39;t run in constant space<br>
&gt;<br>
&gt; Yes, I meant &quot;if you are consuming it just once immediately&quot;.<br>
&gt;<br>
<br>
</div>And that&#39;s what, to my knowledge, is impossible with tail recursion. A tail<br>
recursive map/fmap would have to traverse the entire list before it could<br>
return anything.<br>
<div class="im"><br>
&gt; &gt; the above pattern [...] is better, have the recursive call as a<br>
&gt; &gt; non-strict<br>
&gt;<br>
&gt; field of a constructor.<br>
&gt;<br>
&gt; Which pattern? Mine or Tillman&#39;s? Or both?<br>
<br>
</div>Yours/the Prelude&#39;s. I hadn&#39;t seen Tillmann&#39;s reply yet when I wrote mine.<br>
In<br>
<br>
map f (x:xs) = (:) (f x) (map f xs)<br>
<br>
the outermost call is a call to a constructor [that is not important, it<br>
could be a call to any sufficiently lazy function, so that you have a<br>
partial result without traversing the entire list] which is lazy in both<br>
fields, so a partial result is returned immediately. If the element (f x)<br>
or the tail is not needed, it won&#39;t be evaluated at all.<br>
If there are no other references, the (f x) can be garbage collected<br>
immediately after being consumed/ignored.<br>
<br>
<br>
Tillmann:<br>
<div class="im"><br>
&gt;   data EvaluatedList a<br>
&gt;<br>
&gt;      =  Cons a (List a)<br>
&gt;<br>
&gt;      |  Empty<br>
&gt;<br>
&gt;    type List a<br>
&gt;<br>
&gt;      = () -&gt; EvaluatedList a<br>
&gt;<br>
&gt;    map :: (a -&gt; b) -&gt; (List a -&gt; List b)<br>
&gt;    map f xs<br>
&gt;<br>
&gt;      = \_ -&gt; case xs () of<br>
&gt;<br>
&gt;                Cons x xs  -&gt;  Cons (f x) (\_ -&gt; map f xs ())<br>
&gt;                Empty      -&gt;  Empty<br>
&gt;<br>
&gt; Here, the call to map is more visibly in tail position.<br>
<br>
</div>According to the definition of tail recursion that I know, that&#39;s not tail<br>
recursive.<br>
By that, a function is tail-recursive if the recursive call (if there is<br>
one) is the last thing the function does, which in Haskell would translate<br>
to it being the outermost call.<br>
<br>
Thus a tail recursive map would be<br>
<br>
map some args (x:xs) = map other args&#39; xs<br>
<br>
, with a worker:<br>
<br>
map f  = go []<br>
  where<br>
    go ys [] = reverse ys<br>
    go ys (x:xs) = go (f x:ys) xs<br>
</blockquote></div><br>