From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr 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 833547EF21 for ; Sun, 15 Jun 2014 06:51:45 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of lukstafi@gmail.com) identity=pra; client-ip=209.85.160.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="lukstafi@gmail.com"; x-sender="lukstafi@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of lukstafi@gmail.com designates 209.85.160.174 as permitted sender) identity=mailfrom; client-ip=209.85.160.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="lukstafi@gmail.com"; x-sender="lukstafi@gmail.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-yk0-f174.google.com) identity=helo; client-ip=209.85.160.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="lukstafi@gmail.com"; x-sender="postmaster@mail-yk0-f174.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApABAI8lnVPRVaCulGdsb2JhbABag19agmynAAEGgleNPokPAXsIFg8BAQEBBwsLCRIqhAMBAQEDARIRHQEbEgwDAQsGBQQHGh0CAiEBAREBBQEKEgYBEhIQiAsBAwkIDaROaosngXKDD5JcChknAwplhRkRAQUMhVeGcIIfC4J3gUwEhGMFhVeOC4F5gUOMFYQPGCmFEB0v X-IPAS-Result: ApABAI8lnVPRVaCulGdsb2JhbABag19agmynAAEGgleNPokPAXsIFg8BAQEBBwsLCRIqhAMBAQEDARIRHQEbEgwDAQsGBQQHGh0CAiEBAREBBQEKEgYBEhIQiAsBAwkIDaROaosngXKDD5JcChknAwplhRkRAQUMhVeGcIIfC4J3gUwEhGMFhVeOC4F5gUOMFYQPGCmFEB0v X-IronPort-AV: E=Sophos;i="5.01,479,1400018400"; d="scan'208";a="80112159" Received: from mail-yk0-f174.google.com ([209.85.160.174]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 15 Jun 2014 06:51:44 +0200 Received: by mail-yk0-f174.google.com with SMTP id 19so3219830ykq.33 for ; Sat, 14 Jun 2014 21:51:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=RsuXhtp8KEdXIxz8h3pE6kzljk87/ziXnHXiGfDsto4=; b=OzrC0K2wi5eNYbxpyNcxbk3Zhn8CWOCn62pY4Cqz/xzJcdDArMwLuXDXCQ6hZGnB/+ uC32EZVT4n5MzdL0HWRiCwsbIbghrCM5yOjFn8eLAnOl75j1QonsH7hcuAhI4dW9hHM8 2/Tgf4QkSkl/dFBUIdZbj3890Ocvs3OMShQh0EaKQzTiQcyJm3JPknJT7ghgBqcGAsdl Z2zQTLM32xsCz0eu4ukWNJ7OEocd2anZhpm/fZuBrBMxeg0vOQuFh8PtMoK0MhuJo4Il Q+y9ho4Ko1ji4ORWO7EGjgKZwP8J/SAxjUlBkoxkpPQXOcNp+Yl6Z5/Gewzw0sK692Mp QdYA== X-Received: by 10.236.171.194 with SMTP id r42mr21078781yhl.112.1402807903516; Sat, 14 Jun 2014 21:51:43 -0700 (PDT) MIME-Version: 1.0 Received: by 10.170.131.202 with HTTP; Sat, 14 Jun 2014 21:51:23 -0700 (PDT) In-Reply-To: References: <538CAD12.2040104@inria.fr> From: Lukasz Stafiniak Date: Sat, 14 Jun 2014 21:51:23 -0700 Message-ID: To: Caml , jonikelee@gmail.com Content-Type: multipart/alternative; boundary=20cf3040ec58c6fbe704fbd8aa74 Subject: Re: [Caml-list] Why AVL-tree? --20cf3040ec58c6fbe704fbd8aa74 Content-Type: text/plain; charset=UTF-8 Here is a 2-imbalance AVL trees example from InvarGenT: https://github.com/lukstafi/invargent/blob/master/examples/avl_tree.gadt and the (inferred) types: https://github.com/lukstafi/invargent/blob/master/examples/avl_tree.gadti.target Regards, Lukasz On Tue, Jun 10, 2014 at 11:19 AM, wrote: > I am coming here from the Coq mailing list, because of a link posted there > about this e-mail thread. I have been working on Coq-verified and fully > proof-erased versions of AVL and red-black trees, as well as a variant I > didn't know existed before, until I read about "2-imbalance AVL trees" in > this > thread. > > The github address for my development is: > > https://github.com/jonleivent/mindless-coding > > and the "gaptree" development there may be the same as your "2-imbalance" > AVL > trees, though I can't be sure without more of an explanation (or maybe > just a > pointer to the source code) for the 2-imbalance AVL trees. > > Any further information or source pointers you can give me would be greatly > appreciated. > > Thanks > --Jonathan > > -- > 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 > --20cf3040ec58c6fbe704fbd8aa74 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Here is a 2-imbalance AVL trees example from InvarGenT:https://github.com/lukstafi/invargent/blob/master/examples/avl_= tree.gadt
and the (inferred) types:
https://github.c= om/lukstafi/invargent/blob/master/examples/avl_tree.gadti.target

Regards,
Lukasz

On Tue, Jun 10, 2014 at 11:19 A= M, <jonikelee@gmail.com> wrote:
I am coming here from the Coq mailing list, because of a l= ink posted there
about this e-mail thread. =C2=A0I have been working on Coq-verified and ful= ly
proof-erased versions of AVL and red-black trees, as well as a variant I
didn't know existed before, until I read about "2-imbalance AVL tr= ees" in this
thread.

The github address for my development is:

https://github.com/jonleivent/mindless-coding

and the "gaptree" development there may be the same as your "= ;2-imbalance" AVL
trees, though I can't be sure without more of an explanation (or maybe = just a
pointer to the source code) for the 2-imbalance AVL trees.

Any further information or source pointers you can give me would be greatly=
appreciated.

Thanks
--Jonathan

--
Caml-list mailing list. =C2=A0Subscription 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

--20cf3040ec58c6fbe704fbd8aa74--