Hello everyone! I’m new to Ocaml and I was wondering if it has any data structure similar to Scala’s immutable vector: http://www.scala-lang.org/api/2.12.0/scala/collection/immutable/Vector.html (idea behind it here: https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf ). It’s basically a more…

I don’t know whether this exists, but I’d bet that there is something similar. If you haven’t already done so, you should look in Containers , Batteries Included , and Core or Core_kernel . There might also be other, smaller libraries in opam that provide the kind of data structure you want.

There’s nothing like that in containers. I feel like it’s missing, but I could probably adapt the weird-ish hash trie to work exclusively with consecutive integer keys. I’ll think about it…

Hi, it looks like the Batteries Included library indeed has a vector implementation: http://ocaml-batteries-team.github.io/batteries-included/hdoc2/BatVect.html There is also a mutable, array-backed vector available at https://github.com/gsg/ocaml-vector

Thanks a lot for your replies. It seems like the BatVec is so far the closest one to what I was looking for.

Does Scala currently use RRB trees, or just the radix balanced trees from the background of that paper? The description of the standard library immutable vectors here doesn’t mention faster concatenations, and the implementation here makes it sound like this isn’t the current stdlib vector implement…

The immutable-re library has a vector, but it only works with OCaml < 4.05. [image] Immutable-re Immutable-re: Immutable collections for Reaso

So I started writing something based on trees with up to 32 values and 32 children. It should be called Fun_vec and should provide roughly the same interface as a mutable vector (fast append on the right, fast lookup). first benchmark (comparing it to RAL which is based on Okasaki’s “purely functio…

Hi Simon, how does your thing compares to the batteries’ stuff? Thanks, Francois.

And there is my implementation of RRB-trees in OCaml.

The algorithm is different from BatVec’s underlying rope. I wrote a kind of HAMT-like structure where all nodes contain an array of up to 32 values, and up to 32 subnodes, and filled in increasing index order. Benchmarks with BatVect . I expect it to be quite fast in practice for batch operations by…

Scala Vector-like structure in OCaml

Learning

c-cube February 21, 2018, 1:42am 12

Seems that Daniel Bünzli is on it with pvec. That should be a high quality library!

Topic		Replies	Views
Standardized mutable data structures Ecosystem	34	2837	October 29, 2022
Bit sequences in OCaml Learning	11	3957	May 17, 2019
Adding Dynamic Arrays / Vectors to StdLib Ecosystem	52	7888	October 31, 2023
Announcing Sek, an efficient implementation of sequences Ecosystem	4	1686	April 5, 2020
[ANN] First release of baby Community announce	18	1665	April 4, 2025

Scala Vector-like structure in OCaml

Related topics