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

Jens Axel Søgaard writes:
 > The function map have can't determine whether the given function
 > behaves like the identity on all elements of the list without
 > first building a list with the mapped elements and then compare
 > this list to the original.
 > [...]
 > In other words, I interpret the "where possible" not to mean
 > "theoretically possible" but to mean "possible without speed
 > or memory sacrifices".

I'm not sure what the big sacrifice is:

  (define (map f l)
    (if (null? l)
	null
	(let ((h (car l)) (t (cdr l)))
	  (let ((fh (f h)) (ft (map f t)))
	    (if (and (eq? h fh) (eq? t ft))
		l
		(cons fh ft))))))

> (define l '(0 1 2 3))
> (define fl (map (lambda (x) (if (zero? x) 10 x)) l))
> (eq? l fl)
#f
> (eq? (cdr l) (cdr fl))
#t


OK, it's not tail-recursive, but I'll leave that as an exercise for
the reader...

--dougo at place.org