FSet 1.5.0 gets custom orderings!

The ordering of the "setlike" collections — sets, maps, and bags — in FSet has always been determined by the generic function fset:compare.  This approach is often very convenient, as it allows you to define the ordering of a new type simply by adding a method on compare; there is no need to supply the ordering explicitly every time you create a new collection.

However, as people have complained from time to time, it is also a bit limiting.  Say you want to make something like a telephone directory (anyone remember telephone directories?) which maps string keys to values, and you would like it maintained in lexicographic order of the keys.  To do this with FSet, you have heretofore had to define a wrapper class, and then a compare method on that class, something like:

(defstruct lexi-string

  value)

(defmethod compare ((a lexi-string) (b lexi-string))

  (compare-lexicographically (lexi-string-value a) (lexi-string-value b)))

Then you would have to wrap your keys in lexi-strings before adding them to your map.  That seems a little wasteful of both time and space.

A second problem with always using fset:compare is that you have to pay the cost of the generic function dispatch several times every time the collection gets searched for an element, as in contains? on a set or lookup on a map.  (The number of such calls is roughly the base-2 logarithm of the size of the collection.)  One micro-benchmark I ran showed this cost to be around 20% of the access time, which is not insignificant.

So, in response to popular demand, I have added custom orderings to FSet: you can supply your own comparison functions when creating collections, and FSet will call those instead of compare.  Use of this feature is completely optional; existing code is not affected.  But if you want to do it, now you can!

I refer you to the PR description for the details.

There is one aspect of this change that might surprise you.  When given objects of different classes, fset:compare doesn't compare the contents of the objects; it just compares their class names and returns :less or :greater accordingly.  So, for instance, a list cannot be equal? to a vector or seq, even if they have the same elements in the same order.  This rule now also covers cases where the objects are collections of the same kind (sets, bags, or maps) but with different orderings.  So just as a wb-set and a ch-set can never be :equal, so two wb-sets with different orderings can never be :equal; compare will just look at the comparison function names to impose an artificial ordering.

I'm not suggesting this is an ideal situation, but I don't see a way around it.  Since comparing two wb-sets of the same ordering relies on that ordering, a combined relation on wb-sets of different orderings would in general fail to be transitive; you would get situations where a < b and b < c, but c < a.