Changing one cdr can reshape every path that reaches it.
Perform destructive append, observe aliases into the appended tail, create a cycle, and count unique pairs without following the same object forever.
How do mutation and identity change the meaning of familiar list operations such as append and traversal?
- Find the final pair of a proper mutable list
- Implement append! by changing one existing cdr
- Observe that an alias into the right list remains shared by the result
- Create a finite cycle without attempting to print it as a proper list
- Count unique pairs with an explicit seen-object set
append! does not rebuild the left list. It finds the final pair and changes that pair’s cdr to point at right. The original left name now observes the combined chain, while right still names the shared tail beginning at c. The eq? result exposes that identity relationship directly.
The cycle example changes the final cdr to point back at the first pair. Ordinary recursive list traversal would never reach the empty list. count-unique-pairs therefore records every pair identity before descending and contributes zero when memq finds a pair already seen. The program reports the cycle through eq? instead of asking the printer to expand it indefinitely.
- Output
- —
- Value
- —
- Diagnostic
- —
The destructive append program returns ((a b c d) (c d) #t). The cycle program returns (3 #t).
Find the single set-cdr! that connects the b pair to right, then compare all three names that reach the shared tail. In the cycle run, locate the final link back to the first pair and each memq hit that prevents another descent.
Change the program and compare the result.
Build two lists that share only their final pair, then count unique pairs across a structure containing both lists. Compare that result with a naive recursive pair count.
Show hint
Record pair identities before traversing car and cdr. Equal printed contents do not imply one shared allocation.