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

From: Bradd W. Szonye (bradd+plt at szonye.com)
Date: Wed May 26 18:25:30 EDT 2004

Bradd W. Szonye writes:
>> That won't minimize garbage; indeed, it'll /create/ garbage. This MAP
>> would need to create the results, compare them to the original list, and
>> then throw them away if they match.

Doug Orleans wrote:
> You're the third person to say this...  What am I missing?  My
> implementation (see previous post) creates no more cons cells than a
> naive implementation of `map', as far as I can tell.

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.

You haven't really eliminated any garbage; at best, you've just moved it
from the cons cells to the call frames (and in most cases, doubled the
amount of garbage by /also/ making a consed list).
Bradd W. Szonye

Posted on the users mailing list.