Re: Relation to sorting, checks, typos bear 07 Apr 2005 22:31 UTC


Just a quick word, but I've found it useful in several applications to
have a comparison procedure that imposes a total ordering on data of
many differnt types.  This is useful mainly for making 'ordered
collections' such as trees and ordered arrays that can use any atom as
a key.  I call it "gcmp", but there's probably a better name.

The result is that in the ordering imposed by gcmp, the empty list is
"less than" all booleans, false is "less than" true, all booleans are
"less than" all characters, all characters are "less than" all
symbols, all symbols are "less than" all strings, all strings are
"less than" all numbers, all numbers with a negative imaginary part
are "less than" all numbers with the same real part and no imaginary
part, and all numbers without an imaginary part are "less than" the
complex numbers with the same real part and postive imaginary part.
pairs and vectors are not comparable by gcmp.

Because the implementation allows querying an object for its type and
mapping of types to positive integers, this is efficiently
implementable in a nonportable way.  To implement it in R5RS scheme,
you have to dispatch on the result of type predicates.

The important thing is that the comparison is transitive: If (gcmp a
b) -> #t and (gcmp b c) -> #t, then (gcmp a c) -> #t.  The particular
order defined isn't terribly important.  If adopted, I think it ought
to be okay for gcmp to have implementation-defined intertype ordering
and complex-numeric ordering, but intratype ordering should be defined
as for the ordering predicates within each type; the uses to which
gcmp can be put are more related to computational requirements to
compare and order objects for purposes of key comparison than they are
to any inherent "real" or "mathematical" order for anything.

				Bear