Add a public Vector module built on top of RRB trees

RRB trees can be used to implement highly efficient random access vectors supporting splitAt, concat, insertAt and removeAt functions. I had a primitive implementation but decided not to include it as it did not implement some of the known optimizations, specifically focus nodes.

immutable-re already has a vector module internally, and this implementation would replace that implementation, make it public, and in the process improve Deque.update performance as well. Also we would likely replace internal uses of TreeList with the Vector implementation.

Note the key differences between Deque and Vector:

Deque supports an O(1) reverse operation. Vector cannot support reverse as it would break the ability to perform efficient concatenation.
Vector supports concat, splitAt, insertAt, removeAt.

Proposed API:

let module Vector: {
  type t 'a;

  let add: 'a => (t 'a) => (t 'a);
  let addFirst: 'a => (t 'a) => (t 'a);
  let addLast: 'a => (t 'a) => (t 'a);
  let concat: (list (t 'a)) => (t 'a);
  let count: (t 'a) => int;
  let get: int => (t 'a) => 'a;
  let empty: (t 'a);
  let first: (t 'a) => 'a;
  let insertAt: int => 'a => (t 'a) => (t 'a);
  let isEmpty: t 'a => bool;
  let isNotEmpty: t 'a => bool;
  let last: (t 'a) => 'a;
  let reduce: ('acc => 'a => 'acc) => 'acc => (t 'a) => 'acc;
  let reduceRight: ('acc => 'a => 'acc) => 'acc => (t 'a) => 'acc;
  let removeAt: int => (t 'a) => (t 'a);
  let removeAll: (t 'a) => (t 'a);
  let removeFirst: (t 'a) => (t 'a);
  let removeLast: (t 'a) => (t 'a);
  let splitAt: int => (t 'a) => ((t 'a), (t 'a));
  let toIndexed: (t 'a) => (Indexed.t 'a);
  let toSeq: (t 'a) => (Seq.t 'a);
  let toSeqReversed: (t 'a) => (Seq.t 'a);
  let tryFirst: (t 'a) => option 'a;
  let tryGet: int => (t 'a) => (option 'a);
  let tryLast: (t 'a) => option 'a;
  let update: int => 'a => (t 'a) => (t 'a);
};

References:

facebookarchive / immutable-re

Add a public Vector module built on top of RRB trees #1