4 ms·
Scala has a similar data structure https://www.scala-lang.org/api/2.13.6/scala/collection/immutable/Vector.html https://www.scala-lang.org/api/2.13.6/scala/coll
by goldfishgold 6mo ago
Scala has a similar data structure https://www.scala-lang.org/api/2.13.6/scala/collection/immutable/Vector.html https://www.scala-lang.org/api/2.13.6/scala/collection/immut.... Something was in the air in 2013.
- stingraycharles 6mo agoIt’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 6mo agoI 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 6mo agostructural 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_ 6mo agoCan you please share these data-structures you are talking about? What papers?
- mrkeen 6mo agoBecause 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.
- swannodette 6mo agoClarifying Clojure had them in 2007. Scala implementations were inspired by Clojure’s. Both Odersky and Bagwell have given credit to Hickey.
- bjoli 6mo agoAnd 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.
- panick21_ 6mo agoI 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 6mo agoWell, 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.
- swannodette 6mo agoThat'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.pdf https://docdrop.org/download_annotation_doc/3386321-trk2f.pd...
- bjoli 6mo agoNo, but persistent bit partitioned tries were pretty well known in the late 90s (I first met them in standard ML in 2005)
- whateveracct 6mo agookasaki came first haskell too had them (IntMap honestly works fine in that use case)
- Sesse__ 6mo agoYeah, “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).
- pjmlp 6mo agoReal 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 6mo agoThose are not really the same. Those are N=32 finger trees which have extra benefits (quick slices, for example, quicker insertions).