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 2 days ago | parent | next [-]

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

▲

bjoli 2 days ago | parent [-]

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 2 days ago | parent | next [-]

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 2 days ago \| parent [-]
		No, but persistent bit partitioned tries were pretty well known in the late 90s (I first met them in standard ML in 2005)

▲

panick21_ 2 days ago | parent | prev [-]

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 2 days ago \| parent [-]
		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 2 days ago | parent | prev | next [-]

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 2 days ago | parent | prev | next [-]

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

▲

stingraycharles 2 days ago | parent | prev | next [-]

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 2 days ago | parent | next [-]

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 2 days ago | parent [-]

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_ 2 days ago \| parent [-]
		Can you please share these data-structures you are talking about? What papers?

▲

mrkeen 2 days ago | parent | prev [-]

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 2 days ago | parent | prev [-]

okasaki came first

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

	▲	Sesse__ 2 days ago \| parent [-]
		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).