Having persistent vectors would be very cool indeed — but I wonder how this would work with the “shared nothing” memory of the BEAM?

Since this is all immutable data, you could have all of it in shared memory, and just send references to processes. But if you have to copy the entire tree every time you send it, it will quickly become very slow.

Interestingly enough, according to this, the Erlang Map implementation is based on Rich Hickey’s work. So you could probably just use the maps to simulate a persistent vector without going to Rust at all.

An implementation of vectors/arrays built on top of maps is already available in the arrays package that is available on Hex.

I haven’t benchmarked them yet, but I’d expect them to usually be faster than Erlang’s :array implementation (which above library also has a wrapper for), because that one was built before maps were a thing.

As for tree copying: Copying a whole tree only adds log(n) elements to be copied to a process that would take n elements in the case of a sequential container structure like a list, so this is not ‘quickly becoming slow’ because the copying still happens in O(n) time complexity.

But we could benchmark this stuff at some point, I guess

I haven’t followed your links. But when I read the last time about clojures vectors they where described as a linked list of chunks. And as of such had a read of about O(n/chucnk size) (which is theory equal to O(n) but feels faster).

But you say balanced tree, and then :array comes to my mind. Its not binary, but finger/rose tree, but still kind of balanced.