representing sets

SICP §2.3.3 gives one interface – element-of-set?, adjoin-set, intersection-set, union-set – and three implementations: an unordered list, an ordered list, and a binary tree. Every comparison between two elements below is a recorded step. Enter two sets, pick a representation and an operation, and step through exactly what the procedure does; the same input runs through all three representations so their comparison costs can be compared side by side.

The invariant on display: representation independence. The three representations always agree on the answer – the set of elements returned by each operation is the same regardless of how it's stored – and differ only in how many comparisons each operation costs. The insertion-order control makes this concrete for the binary tree: a tree built from elements that arrive already sorted degenerates into a linked list (ex. 2.63's own warning), and the rebalance option – flatten with tree->list, rebuild a balanced tree with list->tree; ex. 2.63-2.64 – fixes it. The growth chart at the bottom makes the degenerate case precise: the sorted-input tree curve and the unordered-list curve coincide exactly, both n(n-1)/2 comparisons to build a set of n elements.

The pure operations and the trace/replay model live in wal-sh.tools.representing-sets.core (host-neutral .cljc, tested on the JVM with test.check: all three representations agree on every operation's result, tree->list is always sorted, list->tree round-trips through tree->list (ex. 2.64), rebalancing preserves a tree's elements, and the sorted-input-tree/unordered-list comparison-count equivalence). The browser adapter is wal-sh.tools.representing-sets.browser. Build: gmake tools-cljs; debug in isolation: gmake dev-tool TOOL=representing-sets.