Clojure, Scala and JavaScript have excellent implementations of Hickey/Bagwell Hash array mapped tries and Vector tries. This allows Clojure to have built-in persistent array and persistent map types which minimize the need to copy or cache data. Effectively they allow (close to) O(1) lookups, appends and inserts without any copying of data and with all old versions of the data still available, via extensive sharing. (Yes this sounds impossible but it is actually true.)
The best candidate Swift library for my purposes that I have found so far is Forest, a Swift generic implementation of various persistent/immutable trees, but it is not exactly what I am looking for (it has O(log n) complexity because it is a binary tree, not a wide hash tree). It would probably get me off the ground but is not a long term solution.
So my question is quite specific and objective:
- Has someone implemented/port these data structures (hash map and vector) to Swift, and if so, what is the name/GitHub repo link?
- If not, will I have to port this myself? (If I do I will leave an answer below that points to this on GitHub.)
- Is this even feasible on Swift, because of the difference between Automatic Reference Counting and Garbage Collection?
For those who will ask what I need this for over other Swift data structures, the answer is that I am building a purely functional language that is entirely designed around providing these structures as built-in data types. I am trying to decide between JavaScript + ImmutableJS or Swift + Xyz where Xyz is an implementation of these data structures.
NOTE: Again, I am not interested in the built-in Swift immutable array and dictionary types. I understand that they are immutable and persistent. However they have poor time complexity for updates and would not scale. I am looking for ports of the Scala and Clojure or ImmutableJS structures, or if I will have to do that work myself.