[r6rs-discuss] Re: [Formal] Add (sort) and (vector-sort!) procedures

From: Jason Orendorff <jason.orendorff>
Date: Thu Oct 19 15:55:15 2006

> On Fri, Oct 13, 2006 at 01:24:30AM +0200, Marcin 'Qrczak' Kowalczyk wrote:
> > Aubrey Jaffer <ajaffer_at_clearmethods.com> writes:
> >
> > > | The key should be extracted exactly once for each element.
> > >
> > > Because there are potentially more than O(N) comparisons, keys are
> > > potentially accessed more than once. So the sort routines would need
> > > to allocate O(N) storage to hold the keys to meet this requirement.
> >
> > If an implementation extracts keys once, I have a choice: for a fast
> > key extraction function I can pass a comparator which extracts keys
> > on each comparison to save some memory, and for a slow key extraction
> > I can rely on the variant with a key extractor doing the appropriate
> > thing.
>
> And if the key-extract function is impure, this can affect the results
> and not just the run time -- e.g., sorting a list of files by time of
> last modification, where the get-key calls Unix stat(2) or equivalent,
> would yield Bad Stuff if a file were modified during the sort.

I think the right thing is to require behavior "as though" the key
function were called exactly once per element. That way, if a
compiler sees (sort mylist < cadr), it is allowed to optimize away the
map-sort-map dance. But users can still rely upon the desired
behavior in the sort of cases you describe.

-j
Received on Thu Oct 19 2006 - 15:48:04 UTC