Tutorial: FSet for Common Lisp
Introduction
FSet is a functional, set-theoretic collections library for Common Lisp. "Set-theoretic" just means that the types and operations FSet provides are inspired by set theory. "Functional" means that, unlike the types of most collections libraries (and Common Lisp arrays and hash tables), FSet collections are not mutable objects that are updated by side-effect; instead, the various FSet update operations return a new collection, leaving their operand(s) unchanged. Thus FSet brings the benefits of the functional programming style to collection-related code.
What those benefits are is the subject of a separate essay (and many other writings by other people). In this tutorial I will try to show some of them by example. We have just a few preliminaries before we get started. First, this tutorial is addressed to those who have acquired at least some familiarity with Common Lisp; it’s not the place to start for newcomers to the language. Second, you will want to have a copy of FSet running so you can follow along. Assuming you are already using Quicklisp, just do
> (ql:quickload "fset")
The Major FSet Types
FSet provides four major types: sets, maps, seqs, and bags. Sets are the most basic: a set is an
unordered collection of unique members. (FSet imposes an ordering, but this is a standard ordering
FSet uses for its own purposes, and can’t be changed for a particular set instance.) Maps are
perhaps the most useful: a map, like a hash table, associates each of a set of keys with a unique
value. Seqs are FSet’s sequences; I use a shortened form of the word "sequence" because sequence
is, of course, already a CL type name. And finally, bags (another term is "multisets") are somewhat
like sets except that a bag remembers the number of times each member has been added to
it.
The examples assume one is typing to a REPL. User input is shown in bold. To follow along, which I highly recommend, assuming you have installed and loaded FSet, first do this:
> (in-package fset-user)
Sets
The simplest way to create a set is with the function empty-set
:
> (defparameter es (empty-set)) ES > es #{ }
Now we can add an element to the set with with
:
> (defparameter s (with es 3)) S > s #{ 3 }
You can see that the with
function has returned a new set without modifying the original:
> es #{ }
The function empty?
tells you whether a set is empty. (FSet uses the trailing question mark rather
than the older -p
convention for the names of boolean-valued functions.)
> (empty? s) NIL > (empty? es) T
If the set is not empty, arb
will give you one of its members:
> (arb s) 3 T
Note that arb
is not guaranteed to give you any particular member, nor is its job to give you a
"randomly selected" member. Its only postcondition is to give you some member of the set. This
contract may seem a bit odd, but it gives the implementation flexibility to return a "convenient"
member. And it’s still usable in algorithms. For one thing, if the set is a singleton (has size
1), then arb
is guaranteed to return the only member. For another, some "workset" algorithms
don’t need a particular member; they just need to pull some member out of the set on each loop
iteration until it’s empty. (Example below.)
(The second value of T
indicates that the set was, in fact, nonempty; FSet’s philosophy is to use
multiple values to indicate special cases, when that makes sense, instead of signalling errors.)
Having obtained a member of the set, we can remove it with less
:
> (less s 3) #{ }
This may not seem too exciting yet, but it is already enough to write certain algorithms which have this general form:
(let ((workset (some-set))) (loop while (not (empty? workset)) (let ((x (arb workset))) (setq workset (less workset x)) (some-operation-on x) (dolist (y (successors-of-some-kind x)) (if (some-predicate y) (setq workset (with workset y)))))))
Another important function on sets is size
, which returns the number of members:
> (size s) 1
To test membership of a particular value, there’s contains?
:
> (contains? s 2) NIL > (contains? s 3) T
Constructing literal sets by repeated applications of with
gets tedious, so FSet provides a
constructor macro which is simply called set
. (We have shadowed cl:set
, which is archaic
anyway, in the fset-user
package.) For example:
> (set) #{ } > (defparameter s1 (set 1 2 3)) S1 > s1 #{ 1 2 3 } > (defparameter s2 (set 'c 1 "foo" 'a 'c)) S2 > s2 #{ 1 A C "foo" }
You can see that FSet handles many builtin Lisp types (we’ll get to the whole list later); that mixing types in a collection is no problem, of course, this being Lisp; that sets ignore duplication of members; and that FSet imposes its own ordering on sets.
The set
constructor macro has a syntax for including all the elements of another set (this is why
it’s a macro):
> (set ($ s1) 'x) #{ 1 2 3 X }
Okay, given a couple of sets we can start to do some more interesting things with them.
> (equal? s1 (set 3 2 1)) T > (union s1 s2) #{ 1 2 3 A C "foo" } > (intersection s1 s2) #{ 1 } > (set-difference s1 s2) #{ 2 3 } > (set-difference-2 s1 s2) #{ 2 3 } #{ A C "foo" }
(That last one is returning both differences as two values.)
FSet provides alternate versions of many CL functions, which are intended to be shadowing-imported
into your code package (and are, obviously, in fset-user
). Most of these are CLOS generic
functions, with compatibility methods so they will do the same thing as the CL builtins if invoked
on non-FSet types. However, you see we have a separate predicate equal?
rather than shadowing
cl:equal
.
There are also a couple of useful predicates on pairs of sets:
> (subset? (set 1 2) s1) T > (subset? s1 (set 1 2)) NIL > (disjoint? s1 (set 1 2)) NIL > (disjoint? s1 (set 4 5)) T
Maps
You can create an empty map with empty-map
; with
on a map takes two arguments:
> (empty-map) #{| |} > (defparameter m1 (with (empty-map) 'x 1)) M1 > m1 #{| (X 1) |}
Retrieving the value associated with a map key is done with lookup
or its synonym @
(which to
use is a stylistic choice I’ll discuss further below; herein I’ll mostly use @
):
> (lookup m1 'x) 1 T > (@ m1 'x) 1 T > (@ m1 'y) NIL NIL
As you see, these functions return a second value indicating whether the key was in the map. This is
in case you’re using nil
as a range element; since such usage is rare, most of the time you can
ignore the second value. Also as you see, the "default default" for the primary value, when the key
is not in the map, is nil
. The default can be changed, though, either by supplying an argument to
empty-map
when first creating the map, or later by using with-default
:
> (defparameter m2 (with (empty-map 0) 'x 1)) M2 > m2 #{| (X 1) |}/0 > (@ m2 'x) 1 T > (@ m2 'y) 0 NIL > (with-default m1 3) #{| (X 1) |}/3
(When the default is not nil
, it is printed after the map, separated by a slash.)
There is also a constructor macro for maps called map
— the obvious choice of name except that it
requires shadowing cl:map
, which is a little unfortunate (but see the discussion of GMap
below). The map
macro has a more complex syntax than set
since it accepts pairs:
> (defparameter m3 (map ('a 1) ('b 2))) M3 > m3 #{| (A 1) (B 2) |}
Note that the sublists immediately within the map
form are not forms, but pairs of forms
(e.g. ('a 1)
is not evaluated, but 'a
and 1
are evaluated separately). The macro also supports
the $
syntax for including the pairs of another map:
> (defparameter m4 (map ('b 3) ('c 4))) M4 > m4 #{| (B 3) (C 4) |} > (defparameter m5 (map ($ m3) ('D 42) ($ m4))) M5 > m5 #{| (A 1) (B 3) (C 4) (D 42) |}
As you see, when two of the maps included with $
have pairs with the same key, the one on the
right wins.
There are some interesting and powerful operations to combine maps. map-difference-2
returns, as
two values, the mappings in its first argument that are not in its second, and conversely:
> (map-difference-2 m3 m5) #{| (B 2) |} #{| (B 3) (C 4) (D 42) |}
The functions map-union
and map-intersection
return a map whose domain is respectively the union
or intersection of the domains of the arguments. To compute the range value for each key that
appears on both maps, they call a function supplied as their optional third argument; this function
defaults to one that just returns its second argument, so the second map shadows the first one:
> (map-union m3 m4) #{| (A 1) (B 3) (C 4) |} > (defparameter m6 (with-default (map ('a (set 1)) ('b (set 2))) (set))) M6 > m6 #{| (A #{ 1 }) (B #{ 2 }) |}/#{ } > (defparameter m7 (with-default (map ('b (set "x")) ('c (set "y"))) (set))) M7 > m7 #{| (B #{ "x "}) (C #{" y" }) |}/#{ } > (map-union m6 m7 #'union) #{| (A #{ 1 }) (B #{ 2 "x "}) (C #{ "y "}) |}/#{ }
Seqs
Seq indexing is 0-origin, like indexing of CL sequences (cl:elt
etc.).
Seq creation can be done with empty-seq
or the seq
constructor macro:
> (empty-seq) #[ ] > (defparameter q1 (seq 1 2 'a)) Q1 > q1 #[ 1 2 A ] > (defparameter q2 (seq "x" ($ q1) "y")) Q2 > q2 #["x" 1 2 A "y"]
Seqs have operations to access, add, and remove elements at the ends:
> (first q1) 1 T > (last q1) A T > (with-first q1 3) #[ 3 1 2 A ] > (with-last q1 7) #[ 1 2 A 7 ] > (less-first q2) #[ 1 2 A "y" ] > (less-last q2) #[ "x" 1 2 A ]
For indexing purposes, a seq is like a map whose keys are integers. Indexing is done with @
(or
lookup
):
> (@ q1 2) A T > (@ q1 17) NIL NIL
As you see, we again use a second value to indicate that the index was in bounds. Like maps, seqs allow you to specify the default to be returned for an out-of-bounds index:
> (setq q2 (with-default q2 0)) #[ "x" 1 2 A "y" ]/0 > (@ q2 47) 0 NIL
There are two different ways to get a new element into a seq: with
updates an element at a
specific index (it can also be used to append an element); insert
inserts an element at the given
index:
> (with q1 1 7) #[ 1 7 A ] > (insert q1 1 7) #[ 1 7 2 A ] > (with q1 3 42) #[ 1 2 A 42 ]
If with
is given an out-of-bounds index, it extends the sequence as needed by inserting copies of
the default:
> (with q2 8 "yow!") #[ "x" 1 2 A "y" 0 0 0 "yow!" ]/0
To delete the element at a given index, use less
:
> (less q1 1) #[ 1 A ]
Other interesting operations on seqs are subseq
and concat
:
> (defparameter q3 (concat q1 q2)) Q3 > q3 #[ 1 2 A "x" 1 2 A "y" ] > (subseq q3 1 5) #[ 2 A "x" 1 ]
Seqs also support the generic CL sequence operations find
, position
, etc. (Be sure to call the
versions of these functions whose names are in the fset:
package.)
Bags
A bag (sometimes called a multiset) is much like a set except that it associates with each member a natural number (nonnegative integer) called the multiplicity, which represents the number of occurrences of the member in the bag. So, for instance, if you start with an empty bag and add a member to it twice, the resulting bag will contain that member with multiplicity 2. Removing the same member once leaves it in the bag with multiplicity 1.
The basics should be familiar by now (once you get used to the print syntax, at least; the #%
inclusions are for members with multiplicity greater than 1):
> (empty-bag) #{% %} > (defparameter b1 (bag 1 2 1)) B1 > b1 #{% #%(1 2) 2 %} > (with b1 3) #{% #%(1 2) 2 3 %} > (less b1 1) #{% 1 2 %} > (bag ($ b1) 2 3) #{% #%(1 2) #%(2 2) 3 %} > (defparameter b2 (bag 2 2 3)) B2 > b2 #{% #%{2 2} 3 %} > (union b1 b2) #{% #%(1 2) #%(2 2) 3 %} > (intersection b1 b2) #{% 2 %} > (bag-sum b1 b2) #{% #%(1 2) #%(2 3) 3 %} > (bag-product b1 b2) #{% #%(2 2) %} > (size b1) 3 > (set-size b1) 2
union
and intersection
take the max
and min
of the multiplicities of each element,
respectively; bag-sum
and bag-product
take their sum and product. The standard operation size
returns the total multiplicity; to get the number of unique members, use set-size
.
Programming with FSet
This section introduces some idioms and convenience features that make programming with FSet easier, and the resulting code more elegant. It also explains how to extend FSet to handle your own types.
Nested collections
FSet fully supports nesting of collections. Sets of sets, maps keyed by sequences of bags, … all these combinations Just Work™ with no further effort on your part. Such types don’t necessarily arise frequently during ordinary application programming, but they do show up in compiler and static analysis work. The state table of an LALR parser generator, for instance, is basically a map keyed by sets of sequences (the LR(0) items); such a type can be manipulated quite directly and elegantly in FSet.
Assignment and updating
FSet provides several macros which are handy for updating variables that hold collections. (Their
names all end in "f", following setf
.) These might appear at first glance to be mutating
operators, but of course, they’re not:
> (defparameter s (set 1 2)) S > s #{ 1 2 } > (defparameter s1 s) S1 > s1 #{ 1 2 } > (includef s 3) #{ 1 2 3 } > s1 #{ 1 2 } > (excludef s1 1) #{ 2 } > s #{ 1 2 3 }
Some of these also work with maps, and there’s a setf
method for @
(or lookup
). The ability,
mentioned above, to specify a default for the map is very handy here:
> (defparameter m2 (empty-map 0)) M2 > m2 #{| |}/0 > (incf (@ m2 'x)) 1 > m2 #{| (x 1) |}/0 > (defparameter m3 (empty-map (empty-set))) M3 > m3 #{| |}/#{} > (includef (@ m3 'foo) "bar") #{ "bar" } > m3 #{| (FOO #{ "bar" }) |}/#{}
This works to multiple levels too, e.g., a map from something to maps from something else to sets.
Conversions
FSet has its own CLOS generic function, convert
, to handle conversions; this GF has a plethora of
methods already, and more can certainly be added. Its argument order is the reverse of cl:coerce
:
it takes the target type (a symbol) as its first argument, and uses eql
-dispatch on it (see the
code).
A few methods take additional keyword parameters to specify some aspect of the conversion. For
example, there are two ways to represent a bag as a list: either as a flat list possibly with
repeated elements, or as an alist where the cdr of each pair gives the multiplicity. When converting
from an FSet bag, you can specify the target type as either list
or alist
to select the desired
representation; but alist
is of course not a CL type, and can’t be dispatched on, so to convert
from an alist to a bag, you would say :from-type 'alist
.
A brief summary of the important conversions:
-
set, map, seq, or bag to/from list or vector
-
set to/from bag
-
set to/from seq
Iteration
The first thing to be said about iteration in FSet is that if the purpose of iterating over a
collection is to compute a value (which could be a new collection), there is probably no need to
iterate explictly at all. The functions image
, filter
, and reduce
provide very elegant and
clear ways to do implicit iteration to compute a value.
On a set or sequence, image
applies a function to each member and returns respectively a set or
sequence of the results (it’s similar to good old cl:mapcar
):
> (image (lambda (x) (if (oddp x) (1+ x) x)) (set 1 2 3 4)) #{ 2 4 } > (image #'1+ (seq 1 2 3 4)) #[ 2 3 4 5 ]
filter
applies a predicate to each member of a set or sequence and returns a set or sequence of
those members for which the predicate returned true (like cl:remove-if-not
):
> (filter #'oddp (set 1 2 3 4)) #{ 1 3 } > (filter #'oddp (seq 4 3 2 1)) #[ 3 1 ]
And reduce
is a generic version of cl:reduce
:
> (reduce #'union (set (set 1 2) (set 2 3) (set 3 4))) #{ 1 2 3 4 } > (reduce #'concat (seq (seq 1 2) (seq 2 3) (seq 3 4))) #[ 1 2 2 3 3 4 ]
If you’re not used to using these operators, I highly recommend practicing at every opportunity — as I say, any time you’re iterating over a collection to compute a value. They’re an important part of the FSet style.
Iteration macros (do-set
etc.)
The simplest and most commonly used imperative iteration constructs provided by FSet are the
iteration macros do-set
, do-seq
, do-map
, do-bag
, and do-bag-pairs
(all analogous to
dolist
). These are all pretty straightforward. do-map
takes two variables, which are bound to
the key and value of each pair:
(do-map (x y my-map) (format t "~A --> A%" x y))
For each member of the bag, do-bag
executes its body as many times as the multiplicity of that
member. If you want the body executed only once per member, use do-bag-pairs
, which gives you the
multiplicity in a second variable, like do-map
.
GMap
GMap is an iteration macro I first developed as an undergraduate in 1980. I forgot about it for
some years, but when I dusted it off a few years ago it still seemed usable to me. You can think of
it as a generalization of cl:map
(which it predated), which is in turn a generalization of good
old mapcar
. It also bears some relation to Waters' Series package; it’s not as powerful (the
implementation is far simpler) and yet it handles a lot of common cases. It’s somewhat redundant
with image
/filter
/reduce
, but can do some things they can’t, like parallel iteration of two or
more collections.
The basic idea is simple: we start with something resembling mapcar
, and then add just enough
syntax to allow us to specify different ways to generate each argument of the function being mapped,
and different ways to collect the results. Some examples:
> (gmap (:result sum) #'* (:arg index 0 3) (:arg list '(7 3 5))) 13 > (gmap (:result set) #'list (:arg index 0 3) (:arg vector #(q r s))) #{ (0 Q) (1 R) (2 S) } > (gmap (:result map) #'values (:arg index 0 3) (:arg seq (seq 'b 'k 'n))) #{| (0 B) (1 K) (2 N) |}
For complete documentation and more examples see
Misc-Extensions. FSet defines new
argument- and result-types set
, map
, seq
, bag
, and bag-pairs
, and result-types union
,
intersection
, map-union
, map-intersection
, and concat
.
Another macro in Misc-Extensions, also dating back to 1980, is used heavily in the FSet
implementation, and you may find you want to use it also. This is my generalization of let
. It
makes working with multiple values much more convenient; it also generalizes let
and let*
into a
construct that can do both parallel and serial binding in any combination. Check it out, in
new-let.lisp
. This macro is upward-compatible with cl:let
; it is exported as both let
and
nlet
, so you don’t have to shadow cl:let
if you don’t want to.
Iterators
Yet another way you can iterate over collections in FSet is by using the provided iterators. The
generic function iterator
returns a closure of one argument: if passed :more?
it returns true
iff more values are available; if passed :done?
it returns true iff more values are not
available; if passed :get
and more values are available it returns the next value (or, on a map,
the next pair as two values) and an additional true value; if passed :get
when no more values are
available, returns two or three nil
values.
Note that the iterator is a stateful object, unlike most everything else in FSet. If you want an
iterator that behaves functionally rather than statefully, your best bet is to convert
the
collection to a list.
Indexing and rank access
Still another way you can iterate in FSet is by indexing on a seq. Sets, maps, and bags support
an analogous operation called at-rank
which takes an integer and returns the member or pair at
that rank within the collection’s ordering. You can use rank
to find the rank of a member, or for
non-members, the rank it would have if it were in the collection. This is currently the only way to
iterate over a subinterval of a collection.
Equality and comparison
Although supporting several different kinds of equality is something of a Lisp tradition, FSet
relies on a single, global equality predicate, equal?
. On the built-in Lisp types supported by
FSet it behaves mostly like equal
, but unlike the latter, equal?
is extensible for new types.
We’ll see how that works in a moment. For now I just want to make the point that FSet is not like
the CL sequence interface, where you can specify the equivalence relation to use on each operation.
In principle it would be possible for FSet to let you specify the equivalence relation used by a
particular collection, but currently it doesn’t support this (it might someday). So, if you want to
control how the members of a set are distinguished (and also how they’re ordered), you need to
define your own type.
The equality predicate and the ordering relation are connected in this way. The ordering relation is
a CLOS generic function compare
, which takes two arguments and returns one of the symbols :less
,
:greater
, :equal
, or :unequal
. So equal?
just calls compare
and returns true if the result
is :equal
.
The compare
results :less
and :greater
are straightforward — they indicate that FSet should
order its first argument before or after the second, respectively. In rare cases it is necessary to
use the fourth possible value, :unequal
, to indicate that while the two values are not equal, the
relevant compare
method is unable to assign an ordering to them. (We will see some examples
shortly.) FSet goes to some trouble to handle this case correctly, and does so with only a small
loss of performance as long as the sets of mutually :unequal
values remain small.
Member types FSet knows about
FSet already has compare
methods for the following CL types:
-
null
: the type of one object,nil
-
real
: the type of rationals (integers and ratios) and the various float types; these are ordered by<
, of course, but distinguished byeql
, meaning that comparing a rational and a float of equal value returns:unequal
, as does comparing two floats of equal value but different representations -
character
-
symbol
: uninterned symbols of the same name compare:unequal
, as do symbols of the same name of:unequal
packages (see below; this is a very rare case) -
string
: compared by length first, then lexicographically (this possibly surprising choice is made for performance reasons; see below) -
vector
: also compared by length first, then lexicographically -
list
: compared lexicographically; dotted lists are supported -
package
-
pathname
There is a potential problem in that some of these types are mutable in CL: strings, vectors, and lists. It is very important not to modify these while they’re in FSet collections! Doing so will break the ordering invariant that FSet relies on.
If you mix types within a set, as I have in some of the examples in section 1, you will also see the effects of the cross-type comparison methods, which control the ordering of values of different types. FSet defines these for the built-in types it supports; the ordering is the same as that of the above list. For user-defined types, it falls back to comparing the type names. We will see in a moment how to make cross-type comparisons more efficient for new types.
One more point about these built-in compare
methods. While those for simple types like numbers
supply orderings that will likely be generally useful in application code, that’s not their purpose.
In particular, note that a shorter string will always be ordered before a longer one, independent of
their contents; only if the lengths are equal do we look at the contents. That’s not an ordering
that’s likely to be useful to application code, but doing it this way makes sets of strings or
symbols, or maps keyed by strings or symbols, much more efficient in the common case that they are
of varied lengths. In general, I would discourage you from counting on FSet’s built-in orderings;
if you want a set of strings, say, in a particular order, wrap the strings in a struct or class type
and specify the ordering for that type yourself, as we will now see how to do.
Adding new member types
Here we discuss how to extend FSet so you can use your own struct and class types in FSet collections.
The first question to ask of such a type is whether it models an immutable value or a mutable object. If it’s a value, you will want to index it by content; if it’s an object, you should almost certainly index it by identity. The danger of indexing a mutable object by content is that that content could change while the object is in an FSet collection, invalidating the latter’s ordering invariant.
In general, to tell FSet about your type you need to define a method on compare
. In most cases,
this method should return either :equal
, :less
, or :greater
, but there might be rare cases
when it’s necessary to return :unequal
. Suppose, for instance, you are determining the order in
which two values should go by hashing their representations and then comparing the hash values. If
(as is likely) it’s possible for distinct contents to hash to the same hash value, your compare
method should return :unequal
in that case.
FSet provides several convenience facilities to assist you in interfacing your own types to it. For
value types, take a look at compare-slots
: it takes the two values to be compared and (as a rest
argument) a list of accessors; it applies the first accessor to each value and compares the results;
if that comparison returns :less
or :greater
it returns that result, else it moves on to the
second accessor, etc. Here’s an example:
(defclass point () ((x :accessor point-x) (y :accessor point-y))) (defmethod compare ((p1 point) (p2 point)) (compare-slots p1 p2 'x 'y)) ;;; or, if you prefer: (defmethod compare ((p1 point) (p2 point)) (compare-slots p1 p2 #'point-x #'point-y))
Here the points will be ordered first by X coordinate, then by Y coordinate. For each slot, you can specify it either as a quoted slot name or as a function-quoted accessor name; or, you can supply an arbitrary function on your type.
The second convenience facility is for (mutable) object classes: all you have to do, if your class
is a standard (CLOS) class, is to supply identity-ordering-mixin
as one of its superclasses.
That’s it!
The third convenience facility is a macro for defining cross-type comparison methods; simply add,
after your type definition, a form like (define-cross-type-compare-methods point)
While FSet has a fallback mechanism that orders otherwise unordered types by name, it is more efficient, if you are actually going to be mixing types within a collection, to define the cross-type methods explicitly. For types that will not be in mixed collections, this doesn’t matter.
The fourth convenience facility is for cases where, for the purposes of your application, you
specifically want lexicographic comparison of strings or other sequences. The generic function
compare-lexicographically
takes two strings, CL sequences, or seqs, and returns the result of a
lexicographic comparison. To use it, define a new class that holds the string or other sequence in
question, and in the compare
method for that type, call compare-lexicographically
.
Performance considerations
Let me get one thing out of the way. No functional collection implementation can be as fast as well-implemented imperative collections, for the simple reason that the functional implementation has to do more allocation and therefore puts a greater load on the garbage collector. The goal of FSet isn’t to be the fastest collection implementation period; it’s to be fast enough to make functional collections a reasonable choice for ordinary application programming. I’ll say more about this below.
Because FSet is implemented with balanced binary trees, it achieves good time complexity across a wide variety of operations. Of particular note:
-
Lookup (including seq indexing) and point updates take logarithmic time.
-
The operations that combine two collections (
union
etc.) all run in linear time (or better — see below). -
Seq operations
insert
,less
,subseq
, andconcat
take logarithmic time; you can use them freely without worrying about the copying cost you would pay with CL sequences.
FSet also uses a heterogeneous tree design that has much less space overhead than the more common homogeneous trees.
Time complexities of common operations:
These operations run in constant time or amortized constant time: empty?
, size
, set-size
,
arb
, all operations on an iterator
These operations run in time logarithmic in the size of the collection: contains?
, lookup
(aka
@
), with
, less
, subseq
, concat
These operations run in time linear in the size of the collection or the total sizes of the two
collections: equal?
, union
, intersection
, set-difference
, set-difference-2
, map-union
,
map-intersection
, map-difference
These operations run in "quasilinear" (O(n log n) time: sort
, stable-sort
There is an important optimization that applies to the collection-combining algorithms. While they
run in linear time in the normal case, they can run faster than that in the common special case that
the collections being combined are historically related, in the sense that one has been computed
from the other or both have been computed from a common ancestor. In the extreme case, if their
arguments are eq
, they run in constant time. If one argument has been computed by applying a
small number of with
, less
, or update operations to the other (or both have been computed this
way from a common ancestor), they run in logarithmic time. This means, for example, you can take a
large map, hand it to someone, have them make a point modification and hand it back to you, and then
map-difference
will tell you what they did to it in log time! And even if they make many changes
to it, or construct a completely new map and hand it back to you, the worst that can happen is that
the algorithm will fall back to linear time.
Now, about that load on the garbage collector. FSet-heavy programs will, admittedly, tend to generate a fair amount of short-lived garbage. However, most modern Common Lisp implementations use generational garbage collectors, that efficiently collect short-lived garbage. Unless you are working on something extremely performance-sensitive, I think you are very unlikely to even notice the GC running more frequently as a result of using FSet.
Tuples
FSet provides an additional type, tuple
. This type is somewhat experimental; its usefulness is
not clearly established. Tuples are logically similar to maps, but intended for use in situations
where the keys are all compile-time constants (and thus there is a bounded set of them). See the
comments in tuples.lisp
for more information.
FSet Philosophy and Style
You will have noticed already a major difference in design philosophy between CL’s collections and
FSet’s. Besides being functional, the FSet collections are semantically loaded: each collection
knows what kind it is (set, seq, map, bag) and, as previously discussed, knows what equivalence
relation it uses (since there is a single global equivalence relation). In contrast, CL collections
are just bare data structures; you have to remember the intended semantics — for instance, is a
given list a sequence, a set, an alist, etc. — and if you’re using an equivalence relation other
than eql
, you have to remember that too, and supply it explicitly to each operation. This semantic
loading makes FSet collections easier and more elegant to use. It does require, however, that you
decide in advance what kind of collection you’re creating; a decision CL allows you to defer to some
extent.
When and why to use FSet?
Again, FSet’s goal is not to be the fastest collection library; it can’t compete with imperative collections. Rather, it is designed to be a good default choice for ordinary application programming: the thing you use when you don’t have a specific reason to do something different.
A good analogy is generic arithmetic. In CL, most of the time that you write an arithmetic operation (in ordinary application code, at least), you use generic arithmetic. Users of other languages look at that and think that the overhead must make Lisp slow; but we know that, first, there’s an awful lot of code in the world that isn’t particularly performance-sensitive, and second, that for those few places where it matters, Lisp provides ways to reduce or eliminate the overhead, such as type declarations and specialized arrays.
So I would encourage you to think about FSet the same way you think of generic arithmetic. Yes, there’s some overhead, but there are benefits in convenience, elegance, and generality that usually outweigh the overhead. And when that’s not the case, Lisp provides alternatives that are less general, harder to use, but higher in performance.
By the way, I wouldn’t suggest that the FSet types supplant all uses of lists. Lists are very convenient for certain situations. I certainly still find uses for them even in FSet-heavy code; but they are one tool in the toolbox rather than the primary tool.
One place where functional collections are particularly useful is at interfaces. The problem with passing mutable collections across interfaces is the possibility of inadvertent modification of a shared structure. If I pass you a mutable set that I am also using internally, I have to trust that you will not modify it; if you overlook this requirement (or I fail to document it), and treat the set as your own datum that you can modify for your own purposes, you’re likely to break my code. The only easy way to prevent this, with mutable collections, is to copy the set before I hand it to you; but that’s an unpalatable linear-time operation. If, on the other hand, I’m using functional collections, there’s no problem: I can hand you the same set I’m using internally, knowing you can’t inadvertently modify my copy.
This issue probably arises less in Lisp than it would in, say, Java, because (as I commented above) it’s quite common in Lisp to treat lists as functional collections; while it’s certainly possible for you to modify a list I’ve passed to you, you’re more likely to be aware that that could be a bad idea. Still, the issue could come up when using a vector or hash table.
Some style considerations
I expect there will be two primary ways that FSet gets used; I’ll call them "FSet-light" and "FSet-heavy". In the "light" mode of use, FSet types and operations will be sprinkled into code — perhaps, code that was originally written without FSet — but the code will mostly use Lisp collections. In the "heavy" mode, on the other hand, code uses FSet for most or all of its collections.
There are some choices to be made based on this difference. The major one is whether to import the
external FSet symbols into your package. This is clearly desirable for FSet-heavy code (see the
defpackage :fset-user
form in fset.lisp
for an example of how to do this, including a list of
symbols you will need to shadowing-import
from either fset
or cl
). For FSet-light code, on
the other hand, it may be better not to do this, but to refer to FSet symbols with an explicit
fset:
package prefix; this is particularly true when FSet is being added to existing code (and
maybe doubly true on a large project with multiple developers).
A small choice is whether to use lookup
or @
. In FSet-light code you should probably use
lookup
as the name will be easier to recognize, but in FSet-heavy code I think you may as well use
@
(I do).