Sets (Modern Common Lisp with FSet)

Next: Maps, Previous: Notes on Time Complexity, Up: FSet API Reference [Contents][Index]

6.2 Sets ¶

A set is an unordered collection of values without duplicates, called its elements or members, with efficient operations to add or remove a value and to test whether the set contains a value. Adding a value to a set that already contains it, or removing one from a set that does not contain it, results in the same set.

Although sets are conceptually unordered, FSet imposes an order for its own purposes. The WB implementation allows you to control this ordering.

The default implementation of sets is currently CHAMP (ch-set). The WB implementation (wb-set) is also available.

Data type: set ¶: The abstract class for FSet functional sets. Subclass of collection.

Function: set? x ¶: Returns true iff x is an FSet functional set.

Data type: transient-set ¶: The abstract class for FSet transient sets. Subclass of transient-collection.

Function: transient-set? x ¶: Returns true iff x is an FSet transient set.

Function: empty-set ¶: Constructor function. Returns an empty set of the default implementation, currently ch-set, and the default organization.

Macro: set &rest subforms ¶: Constructor macro. Constructs a set of the default implementation, currently ch-set, and the default organization, according to the supplied argument subforms. Each argument subform can be an expression, whose value will be an element of the result set; or a list of the form ($ expression), in which case the expression must evaluate to a set, all of whose elements become elements of the result set.

Data type: ch-set ¶

Functional sets implemented using CHAMP trees. Subclass of set. These print as:

##{ e0 e1 ... }[compare-fn]

Note the double #, which indicates CHAMP. The comparison function is printed only if it is not compare.

Function: ch-set? x ¶: Returns true iff x is an FSet functional CHAMP set.

Function: empty-ch-set &key compare-fn-name ¶: Constructor function. Returns an empty ch-set. By default, it will be ordered by compare. To use a custom ordering, supply the comparison function name (a symbol) as compare-fn-name; a hash function must have been defined for it using define-hash-function.

Macro: ch-set &rest subforms ¶: Constructor macro. Constructs a ch-set according to the supplied argument subforms. See set, above for the interpretation of subforms.

Macro: ch-custom-set compare-fn-name &rest subforms ¶: Constructor macro. Constructs a ch-set with a custom organization, according to the supplied argument subforms. compare-fn-name must be a symbol naming the desired comparison function; a hash function must have been defined for it using define-hash-function. See set, above for the interpretation of subforms.

Data type: wb-set ¶

Functional sets implemented using WB-trees. Subclass of set. These print as:

#{ e0 e1 ... }[compare-fn]

Note the single #, which indicates WB. The comparison function is printed only if it is not compare.

Function: wb-set? x ¶: Returns true iff x is an FSet functional WB-tree set.

Function: empty-wb-set &key compare-fn-name ¶: Constructor function. Returns an empty wb-set. By default, it will be ordered by compare. To use a custom ordering, supply the comparison function name (a symbol) as compare-fn-name.

Macro: wb-set &rest subforms ¶: Constructor macro. Constructs a wb-set according to the supplied argument subforms. See set, above for the interpretation of subforms.

Macro: wb-custom-set compare-fn-name &rest subforms ¶: Constructor macro. Constructs a wb-set with a custom organization, according to the supplied argument subforms. compare-fn-name must be a symbol naming the desired comparison function. See set, above for the interpretation of subforms.