[goldfishgold]

Scala has a similar data structure https://www.scala-lang.org/api/2.13.6/scala/collection/immut.... Something was in the air in 2013.

[swannodette]

Clarifying Clojure had them in 2007. Scala implementations were inspired by Clojure’s. Both Odersky and Bagwell have given credit to Hickey.

[bjoli]

And Hickey himself said he adapted ideas from Bagwell's HAMTs. And tries are 60 years old.

I have always thought Hickeys main contribution was making it default in a coherent way, and proved it could be done. Before clojure most peoplle still thought immutable data structures were too I practical.

[swannodette]

That's a big contribution, also the original HAMTs are not a functional data structure. See Section 3.4.1 in https://docdrop.org/download_annotation_doc/3386321-trk2f.pd...

[bjoli]

No, but persistent bit partitioned tries were pretty well known in the late 90s (I first met them in standard ML in 2005)

[panick21_]

I think the Clojure version does have some actual improvements over the Bagwell version, and some implementation tricks improvements as well. But I don't remember all the details.

[bjoli]

Well, sure. But it is not like Hickey invented the 5bit partitioned trie (there is work in sml and Haskell before that), nor did he invent functional tries.

He took what was a research topic and made it standard. There were no other 5bit partitioned tries in (wide) use. I think he did that in a way that signals a fantastic sense of taste, and if you are implementing a programming language you need taste.

[pjmlp]

Real World Haskell was published in 2008, followed by Real World OCaml in 2013.

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.

[bjoli]

Those are not really the same. Those are N=32 finger trees which have extra benefits (quick slices, for example, quicker insertions).

[stingraycharles]

It’s not a secret that they came from the same zeitgeist but took wildly different approaches, but inspired each other.

I still don’t understand why they’re referred to as persistent vectors rather than immutable vectors, but I digress.

[lemming]

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.

[whateveracct]

structural sharing = log n updates

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)

[panick21_]

Can you please share these data-structures you are talking about? What papers?

[mrkeen]

Because standard libraries in mainstream languages are name-squatting on 'immutable' pretty hard.

You wanted 2+1 to yield 3, but instead you get a runtime exception telling you that 2 can't be changed.

[whateveracct]

okasaki came first

haskell too had them (IntMap honestly works fine in that use case)

[Sesse__]

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).