A collection type considered abstractly can have multiple concrete implementations. This is true even in bare Common Lisp: a sequence can be implemented as either a list or a vector. FSet adds a third sequence type, plus two implementations each of sets, maps, bags, and others. The question then arises: how does equality testing of collections deal with this? Can two sequences, for example, of different implementations be equal?
Some languages, including notably Java, followed by the JVM languages Scala and Clojure, take an
abstract view of equality: two sequences are equal if they contain the same elements in the same
order, independent of what subtype of List each one is implemented as. Similarly, two sets
are equal if they are of the same size and each element of one is also an element of the other. And
so on.
The alternative is a concrete view of equality: for two objects to be equal, they must first be of
the same class. This is how CL’s equal works: a list and a vector are automatically unequal;
their contents are not considered.
The attractiveness of the abstract definition is obvious. For FSet, however, it would run into a snag. One of FSet’s design desiderata is that collections must be nestable without additional work. Since some of FSet’s collections — the WB-tree sets, maps, etc. — are implemented as ordered binary trees, that means that there must exist a consistent ordering over all FSet types. Consider two sets with the same internal ordering relation: FSet can order the sets first by size and then lexicographically, as if they were sequences.
But FSet also has hash-based implementations, which necessarily keep their elements in a different order (and even within an implementation, you can customize the ordering). What would happen, for instance, if we had a WB-tree set, whose elements included both WB-tree sets and hash-based sets? Using abstract equality, we would have to consider two sets equal if they have the same elements. But for our ordering relation to be transitive, it would have to order sets with different internal orders identically. The only way to do that would be to convert them to a canonical internal order before comparing them, which would be very expensive — too expensive to consider.
So FSet must use concrete equality, like cl:equal. This means that a list and a vector, or a
list and an FSet seq, or a seq and a vector, are never equal according to equal?, even if
they have the same elements in the same order. Similarly, two FSet collections of the same abstract
type but different implementations, such as ch-set and wb-set, are never considered
equal, even if they have the same contents. In fact, even two wb-sets with different
ordering relations, or two ch-sets with different hash functions, cannot be equal.
Either choice, arguably, carries a potential for confusion. Consider: what should happen if you try
to make a set that contains both the list (a b c) and the vector #(a b c)? If FSet
used abstract equality, the set would wind up containing only one of those (the first one added,
presumably, though it might not always be clear which one that is). I can certainly imagine that
behavior being surprising to someone intentionally using lists and vectors to represent different
kinds of things. With concrete equality, the set would contain both of them; but this behavior
would also be surprising to someone thinking of these as abstract sequences that just happen to be
represented differently.
I don’t think there’s a perfect solution here. Concrete equality was the path of least resistance for FSet, so that’s the way I’ve gone.