IMHO, this is one of the coolest aspects of Clojure: the data structures were designed to be immutable as efficiently as possible. This allows for some of the most critical aspects of the language to function. If you're whole program passes around values that are immutable, you don't ever have to worry about which part of the code owns what. Rust is such a different language but the borrow-checker is solving a nearly identical problem: who owns this memory and who is allowed to change it? In Rust, one owner ever gets to write to a piece of memory and you can move that around. It catches lots of bugs and is extremely efficient, but it is definitely a difficult aspect of the language to master. Clojure just says everyone gets to read and share everything, because every mutation is a copy. One piece of your codebase can never stomp on or free some memory that another part is using. Big tradeoffs with garbage collection but geeze does it make reasoning about Clojure programs SO much easier. And the cornerstone of that idea is fast, immutable data structures by default. Maps are implemented similarly in that they are fast to make mutated copies with structural sharing to save memory.
It is faster than clojures vectors (running on the JVM, so apples and cucumbers) in all cases, and mostly beats scala's vectors except for splitting which is crazy fast in scala's vectors).
I know people using ref counting to support using allocation arenas for immutable structures. For some workloads that gives a pretty crazy performance boost.
Just pre-allocating leaf nodes can reduce iteration overhead by 40%.
Yeah, “Purely Functional Data Structures” came out in 1996! I read most of it recently, when I needed a C++ copy-on-write hash map. It was still fairly relevant (although the “obvious” solution of a HAMT was also the one we decided on).
I semi-ported it to c# here: https://github.com/bjoli/RrbList/tree/main/src/Collections
It is faster than clojures vectors (running on the JVM, so apples and cucumbers) in all cases, and mostly beats scala's vectors except for splitting which is crazy fast in scala's vectors).
Just pre-allocating leaf nodes can reduce iteration overhead by 40%.
Scala got introduced in 2004, with the first Programming in Scala book, in 2008.
HN had plenty of PureScript and Elm.
FP finally was going to get their spotlight, and then mainstream languages got enough FP features to keep being the go to tooling.
I still don’t understand why they’re referred to as persistent vectors rather than immutable vectors, but I digress.
I believe that immutable just means, well, immutable, but persistent means that updates are achieved via structural sharing, so they’re efficient.
if you think immutable updates are O(n) in 2026, you're so far behind the curve it's laughable
it's crazy how many ppl i interview just stop thinking and insist you can't do better than O(n)
You wanted 2+1 to yield 3, but instead you get a runtime exception telling you that 2 can't be changed.
haskell too had them (IntMap honestly works fine in that use case)