[Caml-list] Do we have a B-tree implementation in ocaml?

[Caml-list] Do we have a B-tree implementation in ocaml?

[Francois Berenger]

Hello,

I am looking for even a simple implementation with at
least the following operations:

insert/add, remove, mem/contains and at_rank.

The at_rank is especially important since it is inefficient
to implement it using fold in a set like the ones from the stdlib.

Thanks a lot,
F.

Re: [Caml-list] Do we have a B-tree implementation in ocaml?

[Frédéric Bour]

[-- Attachment #1: Type: text/plain, Size: 1460 bytes --]

If I understand well, you want an efficient rank function on a 
sequence, you are not particularly interested in B-trees.

I have an implementation of balanced trees you might be interested into:

  https://github.com/def-lkb/grenier/blob/master/baltree/bt1.mli

It is a binary tree with a smart constructor to ensure only balanced 
trees are built.
Beside that, no other constraints are applied. In particular these are 
not search trees although those can easily be implemented on top.

O(1) access to the size (number of items) is provided, and as such an 
O(log n) rank function.

Performance is also quite competitive: although I did not push the code 
yet, I implemented Map and Set from the standard library using these 
trees. On a small set of benchmarks I ran, these were at worst 10% 
slower than the standard ones.


On Wed, Nov 4, 2015 at 6:39 PM, Francois Berenger 
<francois.berenger@inria.fr> wrote:
> Hello,
> 
> I am looking for even a simple implementation with at
> least the following operations:
> 
> insert/add, remove, mem/contains and at_rank.
> 
> The at_rank is especially important since it is inefficient
> to implement it using fold in a set like the ones from the stdlib.
> 
> Thanks a lot,
> F.
> 
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

[-- Attachment #2: Type: text/html, Size: 1961 bytes --]

Re: [Caml-list] Do we have a B-tree implementation in ocaml?

[Tom Ridge]

[-- Attachment #1: Type: text/plain, Size: 1808 bytes --]

I am working on a B+ tree. We are focusing on the verification in Isabelle,
but it would not be too difficult maybe to get some working OCaml code
together. As Frederic says, maybe you just want a binary tree?

On 5 November 2015 at 10:34, Frédéric Bour <frederic.bour@lakaban.net>
wrote:

> If I understand well, you want an efficient rank function on a sequence,
> you are not particularly interested in B-trees.
>
> I have an implementation of balanced trees you might be interested into:
>
>   https://github.com/def-lkb/grenier/blob/master/baltree/bt1.mli
>
> It is a binary tree with a smart constructor to ensure only balanced trees
> are built.
> Beside that, no other constraints are applied. In particular these are not
> search trees although those can easily be implemented on top.
>
> O(1) access to the size (number of items) is provided, and as such an
> O(log n) rank function.
>
> Performance is also quite competitive: although I did not push the code
> yet, I implemented Map and Set from the standard library using these trees.
> On a small set of benchmarks I ran, these were at worst 10% slower than the
> standard ones.
>
>
> On Wed, Nov 4, 2015 at 6:39 PM, Francois Berenger <
> francois.berenger@inria.fr> wrote:
>
> Hello, I am looking for even a simple implementation with at least the
> following operations: insert/add, remove, mem/contains and at_rank. The
> at_rank is especially important since it is inefficient to implement it
> using fold in a set like the ones from the stdlib. Thanks a lot, F.
> --
> Caml-list mailing list. Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners Bug reports:
> http://caml.inria.fr/bin/caml-bugs
>
>

[-- Attachment #2: Type: text/html, Size: 2709 bytes --]

Re: [Caml-list] Do we have a B-tree implementation in ocaml?

[Simon Cruanes]

[-- Attachment #1: Type: text/plain, Size: 796 bytes --]

I also have a weight-balanced tree implementation (quite experimental,
but there are tests), in containers.data: `CCWBTree`
(http://cedeela.fr/~simon/software/containers/CCWBTree.S.html).
It should provide all the operations you ask for in O(log(n)), and takes
a total order as a parameter.

Cheers,

Le Wed, 04 Nov 2015, Francois Berenger a écrit :
> I am looking for even a simple implementation with at
> least the following operations:
> 
> insert/add, remove, mem/contains and at_rank.
> 
> The at_rank is especially important since it is inefficient
> to implement it using fold in a set like the ones from the stdlib.
> 
> Thanks a lot,
> F.


-- 
Simon Cruanes

http://weusepgp.info/
key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [Caml-list] Do we have a B-tree implementation in ocaml?

[Hendrik Boom]

On Tue, Nov 10, 2015 at 03:37:14PM +0100, Simon Cruanes wrote:
> I also have a weight-balanced tree implementation (quite experimental,
> but there are tests), in containers.data: `CCWBTree`
> (http://cedeela.fr/~simon/software/containers/CCWBTree.S.html).
> It should provide all the operations you ask for in O(log(n)), and takes
> a total order as a parameter.

Just wondering -- are these trees in evanescent RAM or on persistent 
disk storage?  If the latter, do they do sufficient locking?

-- hendrik

> 
> Cheers,
> 
> Le Wed, 04 Nov 2015, Francois Berenger a écrit :
> > I am looking for even a simple implementation with at
> > least the following operations:
> > 
> > insert/add, remove, mem/contains and at_rank.
> > 
> > The at_rank is especially important since it is inefficient
> > to implement it using fold in a set like the ones from the stdlib.
> > 
> > Thanks a lot,
> > F.
> 
> 
> -- 
> Simon Cruanes
> 
> http://weusepgp.info/
> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6