[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.

Hello Sven,

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
The Netherlands
tel:       +31 40 27-43166   *** SINCE 10-Feb-2005 ***
fax:      +31 40 27-44004
email: sebastian.egner@xxxxxxxxxxx


07-04-2005 09:41

        To:        srfi-67@xxxxxxxxxxxxxxxxx
        cc:        (bcc: Sebastian Egner/EHV/RESEARCH/PHILIPS)
        Subject:        Relation to sorting



Some might have found the reference to the SRFI-32 archive, which contains some
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 the
withdrawn SRFI-32 as SRFI-68 (Sorting with compare procedures?) or similar?  Or
is the relationship between comparison and sorting so close that some version of
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 :-)