Are there any accessible explanations of RRB trees? I tried implementing them a while ago but all I could find was a something-hundred pages thesis and a paper with some Scala code that I didn't fully grasp ;)
The simple explanation is "take the bit partitioned immutable vectors and relax the leftwise dense requirement" and then sprinkle some magic implementation dust in between that and the finished implementation.
On a more serious note: the only complex piece of code to write is the merge and split operations, but since the structure of the tree is given it isn't theoretically hard. It is just a pain in the ass.
There are two high quality implementations. One for c++ (immer) and the one in scala.
On a more serious note: the only complex piece of code to write is the merge and split operations, but since the structure of the tree is given it isn't theoretically hard. It is just a pain in the ass.
There are two high quality implementations. One for c++ (immer) and the one in scala.
Bagwell did a talk about it on YouTube as well.