[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Relation to sorting, checks, typos
This page is part of the web mail archives of SRFI 67 from before July 7th, 2015. The new archives for SRFI 67 contain all messages, not just those from before July 7th, 2015.
We deliberately did not include anything
related to sorting in SRFI-67,
in order to separate "compare procedures"
and "data structures having
compare procedures as parameters".
(The variable arity procedures
pairwise-not=?, kth-largest, and min/max
are borderline cases.)
Personally, I would like to see a SRFI-68
on sorting and searching based
on SRFI-67 for comparison. A nice starting
point is indeed SRFI-32.
The API should be revised to use an
(optional?) compare procedure,
and to specify (inplace vs. copying)
x (list vs. vector) x (stable vs. unstable),
plus some options to specify the actual
algorithm. Sorting is a strange
thing: The closer you look, the more
difficult it gets. Most applications are
just fine with /some/ stable, inplace,
vector sorting that is not terrible on
frequent inputs (e.g. randomized).
As for the reference implementation,
Mike Sperber told me that a slightly
cleaned version of Olin Shivers' code
is included with Scheme 48 now.
That might be a good starting point
for a portable implementation.
Concerning your other remarks: Having
the checks (compare x x) made
syntactically more visible in the reference
implementation is a good idea;
I have just implemented it. Thanks also
for pointing out the typos and
inconsistencies in the text. You should
find it fixed in the next release.
Dr. Sebastian Egner
Senior Scientist Channel Coding & Modulation
Philips Research Laboratories
Prof. Holstlaan 4 (WDC 1-051, 1st floor, room 51)
5656 AA Eindhoven
tel: +31 40 27-43166 *** SINCE 10-Feb-2005
fax: +31 40 27-44004
(bcc: Sebastian Egner/EHV/RESEARCH/PHILIPS)
Relation to sorting
Some might have found the reference to the SRFI-32 archive, which contains
arguments in favor of 3-way comparisons. My question is: when we
have a better
basis for comparison by way of SRFI-67, would it become easier to revive
withdrawn SRFI-32 as SRFI-68 (Sorting with compare procedures?) or similar?
is the relationship between comparison and sorting so close that some version
SRFI-32 should become part of SRFI-67? I guess I know the answer
I will get :-)
Nevertheless I wanted to raise this issue.
I will not create any new threads today, I promise :-)