RRB Trees: Efficient Immutable Vectors

I propose to add an implementation of Bagwell and Rompf's RRB-Tree Vectors (Relaxed Radix-Balanced Trees) to FSharpx.Collections. They are similar to PersistentVector, but allow for efficient slicing and concatenation. Slicing an RRB vector is effectively constant-time since it takes O(log32 N) time. Concatenating two RRB Vectors together is also O(log32 N) but with a large constant multiplier, as much as 1024 in the worst case, so it should really be considered O(log N) for all practical purposes.

Clojure implementation of RRB vectors: https://github.com/clojure/core.rrb-vector
Scala implementation: https://github.com/nicolasstucki/scala-rrb-vector

Papers about RRB vectors:

• Bagwell and Rompf's original paper
• Further paper by Stucki, Rompf, and Ureche, (and Bagwell, posthumously credited)
• Master's thesis by Jean Niklas L'orange on RRB Vector performance improvements through the use of transient vectors (PDF at http://hypirion.com/thesis.pdf)
• Master's thesis by Nicolas Stucki on the Scala implementation of RRB Vectors (alternate printable version available, as well as slides from Stucki's thesis presentation)

Start by locating FSharpx.Collections' existing PersistentVector implementation and compare it with the linked Clojure and Scala RRB-vector implementations and papers. Define the RRB vector's public operations and representation before working on the implementation. Done means FSharpx.Collections includes an immutable RRB vector supporting efficient slicing and concatenation.