Help reimplementing Array in Elm?

[Evan Czaplicki]

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.

[Gary Lockyer]

I'd take this answer with a grain of salt. But the paper appears to be refering to scala's vectors, which are a trie with a branching factor of 32.  And from a quick read of the paper that appears to be what they mean when they refer to a 31-32 tree.

--
You received this message because you are subscribed to the Google Groups "elm-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-dev+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elm-dev/CAF7GuPE9hVt4e21e_nkm9m_bDZ15oUo2dUsnuHJqxeiC0-MOBQ%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Gary Lockyer]

With a bit more reading the 3-4 31-32 is specifying the range of node sizes, i.e. they are not fixed to 4 or 32. So an n-m tree appears to be trie with node sizes in the range n to m.