There has been a decent amount of activity around the Array library within NoRedInk. Noah got into it because of the equality issues, which led to some interesting ideas and findings.
First, the current implementation is a community contribution written almost entirely in JS and the code is kind of crazy to read. What if we moved as much as possible into Elm?
We started exploring this in
the array branch. Noah, Tessa, Aaron, and I have all paired on it in various configurations to get at least a baseline of things working.
Second, today we got to a point where we realized that no one really knows how
the original paper on Relaxed Radix Balanced Trees
really works.
In section 2.4, they say it is based on the idea of 3-4 trees, but modified to actually be 31-32 trees. I know about 2-3-4 trees now, but not 3-4 trees. They almost certainly are different things, but I have not found any good resources on this.
From there, I looked at the existing JS implementation to see if I could learn more, and I don't think it is doing balancing as described in the paper. I'm not sure though.
Finally, I'm not sure how much farther we will get within NRI pairing on this without finding good resources on 3-4 trees or 31-32 trees. So I just wanted to share this progress with the community to see if (1) anyone had any helpful info or (2) if anyone wants to take a swing at making progress on
Array.elm and
Array.js directly.