From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 5CB407FD26 for ; Fri, 6 Nov 2015 22:05:18 +0100 (CET) IronPort-PHdr: 9a23:gOD/hxOtNt4rTwGiG8Ul6mtUPXoX/o7sNwtQ0KIMzox0KfX7rarrMEGX3/hxlliBBdydsKIZzbGG+P2/EUU7or+/81k6OKRWUBEEjchE1ycBO+WiTXPBEfjxciYhF95DXlI2t1uyMExSBdqsLwaK+i760zceF13FOBZvIaytQ8iJ35nxjLD5psKbSj4LrQT+SIs6FA+xowTVu5teqqpZAYF19CH0pGBVcf9d32JiKAHbtR/94sCt4MwrqHwI6LoJvvRNWqTifqk+UacQTHF/azh0t/vQqALbQACTynwZW2QQ2loUUkmWpC39C7nrMyd7rOt2kAOdINe+Gb4uVDiv9aZgDhXvlT0vMzc6+WvejIp2gb4N5FqGjBV6x8bwYZqJfK51d6bZONcbXnZpX8BLViUHDJnqK8MhFeMHNuFZtMHXqkEDqxSzH0H4CvnmzDRPh2Sw16Ag3uIuHBvu3Qo6HttIvm6C//vvM6JHbeewhJPJwTrOJ6dK3jK76s7ScxwurLKIXKlsWcXWzkYrGgbMj1HWoovgaWDGnt8RunSWurIzHdmkjHQq/kQs+zU= Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=tom.j.ridge@googlemail.com; spf=Pass smtp.mailfrom=tom.j.ridge@googlemail.com; spf=None smtp.helo=postmaster@mail-qg0-f46.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of tom.j.ridge@googlemail.com) identity=pra; client-ip=209.85.192.46; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="tom.j.ridge@googlemail.com"; x-sender="tom.j.ridge@googlemail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of tom.j.ridge@googlemail.com designates 209.85.192.46 as permitted sender) identity=mailfrom; client-ip=209.85.192.46; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="tom.j.ridge@googlemail.com"; x-sender="tom.j.ridge@googlemail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-qg0-f46.google.com) identity=helo; client-ip=209.85.192.46; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="tom.j.ridge@googlemail.com"; x-sender="postmaster@mail-qg0-f46.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0AzAQCbFT1WlC7AVdFehA5vBoJgq3eRW4VvgTYHPBABAQEBAQEBARABAQEBBwsLCR8wgi6CBwEBAQMBDAYRHQEBIwkMBAsBCAIEBw0NHQICIhIBBQEKEgYBEhIQh3YBAwoIDZMMj02BMT4xildxhGMBBYZYChknAwqEWAaLUoUIgm2BRIYQDJAxhR2ICIIkmFMSJIEXESdlgUoNHYFWPjSFFAEBAQ X-IPAS-Result: A0AzAQCbFT1WlC7AVdFehA5vBoJgq3eRW4VvgTYHPBABAQEBAQEBARABAQEBBwsLCR8wgi6CBwEBAQMBDAYRHQEBIwkMBAsBCAIEBw0NHQICIhIBBQEKEgYBEhIQh3YBAwoIDZMMj02BMT4xildxhGMBBYZYChknAwqEWAaLUoUIgm2BRIYQDJAxhR2ICIIkmFMSJIEXESdlgUoNHYFWPjSFFAEBAQ X-IronPort-AV: E=Sophos;i="5.20,253,1444687200"; d="scan'208";a="186468149" Received: from mail-qg0-f46.google.com ([209.85.192.46]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 06 Nov 2015 22:04:42 +0100 Received: by qgad10 with SMTP id d10so101261176qga.3; Fri, 06 Nov 2015 13:04:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:content-type; bh=CIJi4iis/U6P7hjr1YGGvAs5I7+68BY5rMrkm1F66rc=; b=O3ycPtPuzFihXd3zAUwRY0VjPTHCxlKJfw1YjYi25LVUBancZa+otQq93lzFC2ZiIs WN1XNRknRBcCcn/rmH9gvWYc49VAXbH9I9ZlEWLWQzpgDh5aMqfdpHgwUiFKsHYgHu55 /AnJiD2CeemTxvLfmVmlpg8SxG4iC/nfiW9iFbkd+17D9zCdH9fwMYH1ilrCR5HniKAF /TvxfuY+Npqfa/BuFFUnrF9ED1SaAtDM9l2hZkpvZy9bEgYfylwdqSHWahbZsa0ZRBd4 OC5AtW00sJd8Fqr9Uh+NRLOTWbZGXzttOoc4cYvfm6VKzbl1kWzG2NfP0ECO0Yzv+j7b hVDQ== X-Received: by 10.140.229.80 with SMTP id z77mr15782780qhb.104.1446843881405; Fri, 06 Nov 2015 13:04:41 -0800 (PST) MIME-Version: 1.0 Sender: tom.j.ridge@googlemail.com Received: by 10.140.20.13 with HTTP; Fri, 6 Nov 2015 13:04:22 -0800 (PST) In-Reply-To: <1446719674.22101.0@mail.lakaban.net> References: <563A42E9.7010008@inria.fr> <1446719674.22101.0@mail.lakaban.net> From: Tom Ridge Date: Fri, 6 Nov 2015 21:04:22 +0000 X-Google-Sender-Auth: eFX90HgwiQuAerzSZQUryMHW2ic Message-ID: To: =?UTF-8?B?RnLDqWTDqXJpYyBCb3Vy?= , OCaml List , Francois Berenger Content-Type: multipart/alternative; boundary=001a113784f298c4a30523e59747 Subject: Re: [Caml-list] Do we have a B-tree implementation in ocaml? --001a113784f298c4a30523e59747 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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=C3=A9d=C3=A9ric Bour 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 tree= s. > On a small set of benchmarks I ran, these were at worst 10% slower than t= he > 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 > > --001a113784f298c4a30523e59747 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I am working on a B+ tree. We are focusing on the verifica= tion in Isabelle, but it would not be too difficult maybe to get some worki= ng OCaml code together. As Frederic says, maybe you just want a binary tree= ?

On 5 Novem= ber 2015 at 10:34, Fr=C3=A9d=C3=A9ric Bour <frederic.bour@lakaban.= net> wrote:
If I understand well, you want an efficient rank function on a sequenc= e, you are not particularly interested in B-trees.

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


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

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

Perform= ance is also quite competitive: although I did not push the code yet, I imp= lemented Map and Set from the standard library using these trees. On a smal= l set of benchmarks I ran, these were at worst 10% slower than the standard= ones.


On W= ed, Nov 4, 2015 at 6:39 PM, Francois Berenger <francois.berenger@inria.fr> w= rote:
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.
--=20
Caml-list mailing list. Subscription management and archives: ht= tps://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

--001a113784f298c4a30523e59747--