Ordering changes what a set operation can skip.
A set stored as an increasing list can stop membership search after passing the target and can merge two unions without rescanning either prefix.
Which work becomes unnecessary when a set representation promises increasing order?
- Treat increasing order as a representation invariant
- Stop membership search after the first larger element
- Advance one or both set tails after comparing their heads
- Keep union ordered while removing duplicates
element-of-ordered-set? compares the target with each current head. Equality succeeds, a smaller target fails immediately, and only a larger target justifies visiting the tail. Searching for 4 therefore checks 1, 3, and 5 but never visits 7 or 9.
union-ordered-set compares the two heads. It keeps the smaller one and advances that list; equal heads produce one element and advance both. Every recursive step consumes at least one current head, preserving sorted order without restarting a search from the beginning.
- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (#f 3). The second returns (1 2 3 5 6 8 9).
Find the comparison with 5 that ends membership search before 7 and 9. In union, watch each head comparison consume left, right, or both while the result remains increasing. These traces rely on the shipped inputs already being ordered sets.
Change the program and compare the result.
Write intersection-ordered-set with the same two-head comparison. Predict the intersection of the two shipped union inputs.
Show hint
Keep a value only when both heads are equal. Otherwise discard the smaller head.