compare ¶FSet provides a default ordering using the generic function compare. Having a default
ordering, implemented as a generic function, is a great convenience: it makes code more elegant by
removing the need to specify, whenever you create a collection, what ordering to use for it.
Instead, the ordering is associated with the type of the objects in the collection. While FSet now
has a facility for specifying custom comparison (and hash) functions for specific collections —
more on which below — I don’t think you will need to use it very often.
FSet predefines compare methods on the most commonly used built-in Common Lisp types:
null, real, complex, character, symbol, string,
list, vector, array, sequence, class, pathname, and
package.
FSet also defines “cross-type” methods that order values of different types, so that either all
values of one type will compare less than those of another, or all greater. (The type ordering is
arbitrary.) So FSet itself places no restrictions on what combinations of types can appear in a set
or bag, or as the keys of a map. In particular, the value nil is allowed.
Important note: compare compares lists, strings, vectors, and arrays by
content even though they are mutable. (I discussed why in Comparison and Equality.)
This means that once you use such an object in an FSet collection in such a way that it’s subject to
comparison or hashing, you must not mutate it. You have been warned!
In most cases, comparison of collections — strings, vectors, arrays, and other sequence types your implementation may support; and FSet collections themselves — starts by comparing the sizes of the two collections, and if they’re different, considering the smaller collection as less than the larger one, independent of their contents. Thus, all two-character strings compare less than all three-character strings, etc. This approach improves performance over the more familiar lexicographic (dictionary-style) comparison, in which length comes into play only when the shorter string is an initial substring (prefix) of the longer one. However, it does make the ordering less natural for human perusal. (Lists are compared lexicographically, though, because finding the length of a list takes O(n) time.)
compare of course follows the FSet comparison function protocol, mentioned above. There are
two predefined compare methods that can return :unequal on non-collection values:
This method returns :unequal when the arguments are of equal value, but are not equal
according to eql. This happens when one is a rational (including integers) and the other is
a float, or they are both floats but of different precisions — they are numerically equal, but not
indistinguishable.
Normally, symbols are compared by first comparing the names of their symbol-packages, and then if
those are equal, comparing their symbol-names. However, not all symbols have a symbol-package; it’s
possible to have distinct (non-eq) symbols with no symbol-package and with the same
symbol-name. (Yes, I’ve seen this in macro expansions.) In such a case, this method returns
:unequal.
There’s an even gnarlier case, caused by the existence of the rename-package function in CL:
you can rename a package, perhaps to get it out of the way after it gets screwed up somehow. If
FSet always used the current name of the package for comparison purposes, renaming it would
be very dangerous, as it could change the orderings of symbols in existing collections, breaking a
key invariant and rendering the collections unusable. To protect itself against this, FSet
squirrels away the original name of each package, and uses that for comparison purposes. But this
could result in two distinct packages having the same original name. In such a case, the packages
compare :unequal, and two symbols in those packages that have the same name also compare
:unequal.
Once generated, :unequal can be propagated by collection comparisons: if two collections
would be equal except that an element of one compares :unequal to the corresponding element
of the other, then the collections compare :unequal also. More on this below.
equal? is the FSet generalization of cl:equal. All it does is to call compare
on its argumens, and return true if the result is :equal. equal? behaves identically
to cl:equal on the built-in CL types, with one exception: on vectors other than bit-vectors,
cl:equal compares them by identity (eq), but equal? compares the contents. (On
bit-vectors, both compare the contents.)
compare makes no effort to detect circularities in the structures it is comparing. Putting
cyclic structures in FSet collections is not supported.