4 ms·
Thanks for the info, I didn't realize the connection between hash array mapped tries and persistent collections. Are you aware of any open source (ie. linkable)
by sanderjd 11y ago
Thanks for the info, I didn't realize the connection between hash array mapped tries and persistent collections. Are you aware of any open source (ie. linkable) implementations that work that way?
- tomp 11y agoClojure [1] - the crucial implementation is really in classes BitmapIndexedNode and ArrayNode. Scala [2] - Scala's source is an incredibly convoluted spaghetti of abstract classes and traits, but it looks like the main bits of implementation is in methods get0 and updated0 of HashTrieMap. There's also a C# implementation somewhere, but it's not a part of a language library, so it's likely less optimized (except for some boxing/reified generics, which make it theoretically more efficient). But all these implementations use the same basic algorithm, so it's irrelevant which one you study. [1] https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju... [2] https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/immutable/HashMap.scala https://github.com/scala/scala/blob/2.11.x/src/library/scala...
- sanderjd 11y agoWow, thanks for doing the leg work for me. This is the type of thing that reminds me why the internet is so wonderful :)
- kqr 11y agoSure, the [unordered-containers](https://github.com/tibbe/unordered-containers https://github.com/tibbe/unordered-containers) library is based on that IIRC, as is the [hash map in Clojure](https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju...).