FSet
FSet is a functional set-theoretic collections data structure library by Scott L. Burson.

Functional means that update operations return a new collection rather than modifying the existing one in place. Set-theoretic means that collection instances aren't solely data structures holding elements; they are also pure mathematical values, like numbers. This means, among other things, that like sets etc. in mathematics, these collections can be arbitrarily nested. Compound types like maps keyed by sets of sequences just work with no additional programmer effort.

FSet is implemented using heterogeneous weight-balanced binary trees. FSet uses a single, global, extensible ordering relation (implemented as a CLOS generic function), so that FSet collections can contain any combination of types.

Some examples to give the flavor:

* (setq s1 (set 1 2 3))        ; shadowed version of `set', not `cl:set'
#{ 1 2 3 }
* (setq s2 (with s1 'foo))
#{ 1 2 3 FOO }
* s1
#{ 1 2 3 }
* (setq m1 (map (s1 "without foo") (s2 "with foo")))          ; `map' also shadowed
#{| (#{ 1 2 3 } "without foo") (#{ 1 2 3 FOO } "with foo") |}
* (lookup m1 (set 2 3 1))     ; note that ordering doesn't matter for sets
"without foo"
* (lookup m1 (set 3 'foo 1 2))
"with foo"

For more information:

FSet page on Common-Lisp.net

A tutorial

The recommended way to obtain FSet is with Quicklisp.