FSet brings persistent functional data structures to Common Lisp, delivering O(log n) operations for sets, maps, bags, and sequences. Developers get immutable collections that share structure on updates, avoiding the mutation pitfalls of CL’s lists, vectors, and hash tables. This matters because Common Lisp’s mutable defaults hinder concurrency and state reasoning in multicore applications—FSet fixes that without forcing a language switch.
Released around 2010 by Nathan Froyd, FSet targets “modern” Lisp use cases like graph algorithms and simulations. Its collections use two backends: weight-balanced (WB) binary trees for strict O(log n) worst-case performance, and CHAMP (cache-hash array-mapped persistent) trees for amortized speed akin to Clojure’s. WB-trees balance by subtree size, ensuring no path exceeds 2*log(n) nodes. CHAMP hashes into arrays of 32-1024 buckets, cascading for persistence. Both support millions of elements before slowdowns, per benchmarks in the docs.
Core Structures and Operations
Sets store unique elements; insert/delete yield new sets sharing 90-99% structure with predecessors. Maps act as functional hash tables—(lookup map key) runs in O(log n), (insert map key val) creates a versioned copy. Bags handle multisets for histograms: add elements, count frequencies without resizing arrays. Seqs mimic vectors with efficient concatenation and slicing.
Start with Quicklisp:
(ql:quickload :fset) Import via (use-package :fset.rail) for clean syntax. Build a set:
(defvar s (singleton 42))
(insert s 1 2 3) Update immutably: (defvar s2 (insert s 4))—s stays unchanged. Nested structures like set-of-maps work seamlessly: (set (map #\a 1)).
Nesting shines in graphs: represent adjacency lists as maps-of-sets. Walk with do-map or gmap for generic iteration. The histogram example counts word frequencies in O(n log n) time, beating naive hash tables under high contention.
Tradeoffs and Real-World Fit
FSet allocates on every update—expect 10-100x more cons cells than mutable ops in tight loops. But path-copying shares nodes, so a chain of 1M inserts uses under 20M nodes total, not 1M! Compare to CL hash tables: O(1) average but resizing pauses and races. FSet’s determinism aids testing; no Heisenbugs from shared mutation.
Skeptical note: CL’s object system (CLOS) integrates loosely—FSet types aren’t standard sequences, so mapcar fails. Use convert for interop: (convert 'list my-seq). Iteration via do-seq, collecting, or iterate library. Custom classes need compare and hash-value methods; strict weak ordering required to avoid cycles.
In practice, FSet powers CL-Cont (continuation library) for efficient state machines and the CLIM GUI toolkit’s event handling. For crypto/security apps—think key sets or transaction graphs—immutability prevents side-channels from shared state. Graph walking example traverses 100K nodes in seconds, scaling linearly.
Why this matters now: Multicore servers run 64+ threads; mutable CL code serializes on locks. FSet enables fork-join parallelism—pass collection versions to workers, merge immutably. No GC pauses like JVM langs; SBCL optimizes tail calls. Downsides? Steeper curve than Python dicts, and printing large structures bloats output (use print-pretty).
Bottom line: FSet modernizes CL for functional paradigms without hype. Pair with Alexandria for utils; test on 10M-element sets to feel the log n. If you’re building concurrent systems or tire of debugging mutable state, load it today—it’s battle-tested over a decade.
