FSet
FSet is a functional set-theoretic collections data structures 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, 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/CL, the Common Lisp implementation, 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))
"without foo"
* (lookup m1 (set 3 'foo 1 2))
"with foo"

For more information:

FSet page on Common-Lisp.net

The recommended way to obtain FSet is with Quicklisp.