[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Relation to sorting, checks, typos




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.

Sebastian.

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








srfi-67-request@xxxxxxxxxxxxxxxxx

07-04-2005 09:41

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

        Classification:        




Hello.

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.

Greetings
Sven

P.S.
I will not create any new threads today, I promise :-)