Where a map is a set of key/value pairs where the keys are unique, a binary relation is any set of such pairs, possibly with dupicate keys. For a simple example, imagine you have a number of products, each of which comes in one or more colors. There are, in general, multiple colors per product, but also different products that come in the same color; so you couldn’t represent this as a map from product to color, or one from color to product. What you have is a binary relation. You could draw it as a boolean-valued matrix where the rows are products and the columns are colors.
You could represent your matrix as a map from each product to a set of colors; and that’s how FSet treats binary relations internally. The inverse mapping, from color to set of products, may also be of interest; FSet will build that for you on demand and cache it, updating it incrementally as you update the relation. The operations listed below that cause the inverse mapping to be built are marked as “constructs inverse”; the time complexities for these operations are given as amortized, under the assumption that the inverse mapping has usually already been built.
I used the name 2-relation for these, partly because it’s shorter than
binary-relation, and partly to show off Lisp’s unconventional lexical rules — most
languages wouldn’t let us start an identifier with a digit!
There are both CHAMP and WB implementations; the default is CHAMP.
The abstract class of FSet functional binary relations. Subclass of collection.
Returns true iff x is an FSet functional binary relation.
The abstract class of FSet functional binary relations. Subclass of transient-collection.
Returns true iff x is an FSet functional binary relation.
Constructor function. Returns an empty binary relation of the default implementation, currently
ch-2-relation, and the default organization.
Constructor macro. Constructs a 2-relation of the default implementation, currently
ch-2-relation, and the default organization according to the supplied argument subforms.
Each argument subform can be a list of the form (key-expr value-expr), denoting a
mapping from the value of key-expr to the value of value-expr; or a list of the form ($
expression), in which case the expression must evaluate to a 2-relation, all of whose mappings
will be included in the result. Also, each of key-expr and value-expr can be of the
form ($ expression), in which case the expression must evaluate to a set, and the elements of
the set are used individually to form pairs; for example:
> (2-relation (($ (set 1 2)) ($ (set 'a 'b))))
##{+ (1 B) (1 A) (2 B) (2 A) +}
Functional binary relations implemented using CHAMP trees. Subclass of 2-relation. These
print as:
##{+ (k0 v0) (k1 v1) ... +}[key-compare-fn;val-compare-fn]
Note the double #, which indicates CHAMP, and the plus signs just inside the braces. The
comparison functions are printed only if they are not compare.
Returns true iff x is an FSet functional CHAMP binary relation.
Constructor function. Returns an empty ch-2-relation. key-compare-fn-name and
val-compare-fn-name, if supplied, must be symbols naming the comparison functions to be used
for keys and values respectively (these default to compare). A hash function must have been
defined for each comparison function using define-hash-function.
Constructor macro. Constructs a ch-2-relation according to the supplied argument subforms. See
2-relation, above for the interpretation of subforms.
Constructor macro. Constructs a ch-2-relation with a custom organization, according to the supplied
argument subforms. key-compare-fn-name and val-compare-fn-name must be symbols naming
the comparison functions to be used for keys and values respectively (you can use nil as a
synonym of compare). See 2-relation, above for the
interpretation of subforms.
Functional binary relations implemented using WB-trees. Subclass of 2-relation. These print
as:
#{+ (k0 v0) (k1 v1) ... +}[key-compare-fn;val-compare-fn]
Note the single #, which indicates WB, and the plus signs just inside the braces. The
comparison functions are printed only if they are not compare.
Returns true iff x is an FSet functional WB-tree binary relation.
Constructor macro. Constructs a wb-2-relation according to the supplied argument subforms. See
2-relation, above for the interpretation of subforms.
Constructor macro. Constructs a wb-2-relation with a custom organization, according to the supplied
argument subforms. key-compare-fn-name and val-compare-fn-name must be symbols naming
the comparison functions to be used for keys and values respectively (you can use nil as a
synonym of compare). See 2-relation, above for the
interpretation of subforms.