FSet has a default ordering relation, computed by the generic function compare. It comes
with methods to compare most of the builtin CL types (null, real, complex,
character, symbol, string, vector, list, package,
pathname, and array) along with FSet’s own types. The comparisons are used to build
and search FSet’s internal data structures, so they must obey certain
mathematical rules.
The semantics of equal?, which are a consequence of the behavior of compare, are, on
the built-in CL types, almost identical to those of cl:equal. The only difference is that
for vectors that are not bit-vectors, cl:equal compares them by identity (eq), while
equal? compares them by content. (Both functions compare bit-vectors by content.)
FSet collections are always compared by content, and it is intended that objects that are actually subject to mutation should be compared by identity.
For more in-depth discussion on comparison by identity vs. comparison by content, have a look at Henry Baker’s paper Equal Rights for Functional Objects. This blog post may also be of interest: Equality and Comparison in FSet.
There is a big catch here, however. Lisp lists, strings, and vectors are technically mutable, and
not infrequently actually mutated. However, defining compare to distinguish them by identity
would run into two problems. First, it would produce very surprising results semantically; given a
map keyed by strings, for example, one would have to pass the correct instance of each key string to
lookup in order to retrieve the value. These types would function simply as opaque identities.
This would not be useful behavior. Second, the implementation would have very poor performance
characteristics, as there would be no way to order instances of these types; compare would have to
fall back to returning :unequal on any pair of them, forcing the implementation to store them in
alists and compare them by eql. Time complexity of lookup would balloon from logarithmic to
linear.
So FSet makes an assumption that is not unreasonable in practice, but that you must keep in mind: once a list, string, or vector is placed in an FSet collection, FSet assumes it will not thereafter be mutated. This assumption licenses FSet to compare these by content instead of by identity, giving natural semantics and decent performance. (There is an exception, discussed later.)
FSet does not attempt to define compare on Lisp hash tables or function objects. I do not
recommend placing these types in FSet collections.