FSet 1.2 Release Notes

There are no very major changes to FSet for 1.2. There are a fair number of detail improvements, and of course some bug fixes. Since 1.1 I have actually had the chance to use FSet in a couple of projects, and I love it! But I would, of course :)

Largely as a result of that experience, FSet 1.2 has improved support for extending FSet to handle user-defined types. See compare-slots and identity-ordering-mixin (both described in the spiffy new tutorial).

There were a couple of changes to existing interfaces:

fold is deprecated in favor of reduce, which shadows/genericizes cl:reduce and has a slightly different interface. (fold dates back to a time when I wasn't doing nearly so much shadowing, but now that there are lots of shadowed/genericized CL functions, it makes sense for reduce to be one of them.)

I decided I liked the name contains? better than member?, with the opposite argument order. Most FSet functions that take both a collection and a value or possible value of the collection or its domain take the collection as the first argument, like cl:aref and cl:elt and unlike cl:assoc and cl:gethash; the only exception among FSet's own interfaces was member? (the shadowed CL sequence functions find, count, etc. take the collection second, and so are not consistent with the FSet convention, but these need to remain compatible with their CL versions, so I can't change them). So, I now consider member? deprecated (a back-compatibility function remains), and encourage the use of contains? instead. Also, it used to be the case that member? on a map would tell you whether the value was a member of the map's domain; now there are separate operations domain-contains? and range-contains? which work on both maps and seqs. range-contains? performs a linear search.

FSet 1.2 includes experimental code for some new types:

• Infinite complements of finite sets. You can request the complement of any set and receive an object called a complement-set. You can't enumerate it, obviously, but it supports the familiar operations union, intersection, set-difference, subset?, and disjoint?, both with normal sets and other complement sets. This is only a notational convenience; but FSet is all about notational convenience :-)
• "Bounded" sets, which are subsets of a known set (the type is bounded-set). These also support complement, but in this case the complement is finite, and therefore enumerable. These are also a notational convenience, but can be handy.
• Binary relations (the type is 2-relation). These are logically sets of pairs; they differ from maps in that a single domain value can be paired with multiple range values. The implementation uses a map from each domain value to the set of its range values, and an inverse map from each range value to its set of domain values; but the inverse map is constructed only if needed (once constructed, it is maintained incrementally).
• Sets of intervals (the type is interval-set). Each interval can be open or closed at either end. These don't have to be numeric intervals, but can be bounded by any type with an FSet ordering; for example, they could be strings.

By the way, there are places where we assume that no collection has more than most-positive-fixnum elements. This is a pretty safe assumption in most implementations.