[plt-scheme] should `map' reuse cons cells?

Bradd W. Szonye writes:
 > Given (map identity l), most maps will create a duplicate list (built
 > backwards and then reversed). Your implementation instead creates a
 > duplicate "list," but using call frames instead of cons cells. Given an
 > arbitrary mapping function, most maps still only create a duplicate
 > list. Yours creates two duplicates, one explicitly with cons cells and
 > one implicitly with call frames.

OK smarty pantses, you guys win.  I see now that a tail-recursive
version of my program would still have to make an intermediate list:

(define (map f l)
  (let loop ((in l) (out null) (same-tail l))
    (if (null? in)
	(append-reverse! (drop out (length same-tail)) same-tail)
	(let ((x (car in)) (in (cdr in)))
	  (let ((fx (f x)))
	    (loop in (cons fx out) (if (eq? x fx) same-tail in)))))))

> (define l (iota 7 -3))
> l
(-3 -2 -1 0 1 2 3)
> (define fl (map abs l))
> fl
(3 2 1 0 1 2 3)
> (eq? (cdddr l) (cdddr fl))
#t

So it doesn't create any less garbage, but it's still a win for me
because I can avoid a lot of `equal?' traversal later.  But maybe this
is a rare enough case that the `eq?' overhead isn't worth changing the
standard implementation.

I'll note that the SRFI-1 implementation of `map' is not tail
recursive, by the way, so it's also creating two duplicates, by
Bradd's argument.

--dougo at place.org