Understanding Clojure's Persistent Vectors, pt. 1 (2013)
5 days ago
- #Clojure
- #Persistence
- #Data Structures
- Persistent vectors in Clojure offer nearly constant-time operations for appends, updates, lookups, and subvec.
- They utilize path copying in balanced trees to achieve persistence without full array duplication.
- Updates involve copying nodes on the path to the target leaf and replacing the value.
- Appends handle three cases: space in the leaf, need for new nodes, or root overflow.
- Popping removes the last element, with cases for leaf removal, empty node cleanup, and root reduction.
- Shallow trees with a high branching factor (32 in Clojure) make operations effectively O(1).