> And that'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 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"><<a href="mailto:daniel.is.fischer@googlemail.com">daniel.is.fischer@googlemail.com</a>></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>
> > Yes, and a tail-recursive map couldn't run in constant space<br>
><br>
> Yes, I meant "if you are consuming it just once immediately".<br>
><br>
<br>
</div>And that'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>
> > the above pattern [...] is better, have the recursive call as a<br>
> > non-strict<br>
><br>
> field of a constructor.<br>
><br>
> Which pattern? Mine or Tillman's? Or both?<br>
<br>
</div>Yours/the Prelude's. I hadn't seen Tillmann'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'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>
> data EvaluatedList a<br>
><br>
> = Cons a (List a)<br>
><br>
> | Empty<br>
><br>
> type List a<br>
><br>
> = () -> EvaluatedList a<br>
><br>
> map :: (a -> b) -> (List a -> List b)<br>
> map f xs<br>
><br>
> = \_ -> case xs () of<br>
><br>
> Cons x xs -> Cons (f x) (\_ -> map f xs ())<br>
> Empty -> Empty<br>
><br>
> 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'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' 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>