three-way comparison

*Sven.Hartrumpf@xxxxxx*23 Oct 2006 08:36 UTCHello. Thanks Aubrey for drafting a sorting SRFI. Maybe this time (after the withdrawn SRFI-32) we will see such a beast :-) Three-valued comparison function are more efficient for some data types if many duplicates are present. I often sort lists of some million strings of average length 20 and many duplicates. I remember that some sort algorithms will test (< a b) and (< b a) in certain constellations for one setting of a and b. A three-valued comparison function also speeds up other algorithms, e.g. vector-binary-search. SRFI-67 provides a solid base of comparison functions: http://srfi.schemers.org/srfi-67/srfi-67.html A short quote: "Moreover, in case Scheme users and implementors find this mechanism useful and adopt it, the benefit of having a uniform interface to total orders to be used in data structures will manifest itself. Most concretely, a new sorting procedure in the spirit of this SRFI would have the interface (my-sort [ compare ] xs), using default-compare if the optional compare was not provided. Then my-sort could be defined using the entire infrastructure of this SRFI: Efficient 2- and 3-way branching, testing for chains and pairwise inequality, min/max, and general order statistics." See also: http://srfi.schemers.org/srfi-32/mail-archive/msg00023.html http://srfi.schemers.org/srfi-32/mail-archive/msg00024.html Greetings Sven