From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 98EB3BC6C for ; Tue, 25 Sep 2007 20:54:05 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAO31+EbAXQImk2dsb2JhbACOLAEBAQEHBAYHIA X-IronPort-AV: E=Sophos;i="4.20,296,1186351200"; d="scan'208";a="3242492" Received: from discorde.inria.fr ([192.93.2.38]) by mail3-smtp-sop.national.inria.fr with ESMTP; 25 Sep 2007 20:54:05 +0200 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l8PIrxnP007162 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Tue, 25 Sep 2007 20:54:05 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ao8CAO31+EaACH6C/2dsb2JhbAA X-IronPort-AV: E=Sophos;i="4.20,296,1186351200"; d="scan'208";a="1458241" Received: from lb-nat-3.cs.umd.edu (HELO dispatch.cs.umd.edu) ([128.8.126.130]) by mail1-smtp-roc.national.inria.fr with ESMTP; 25 Sep 2007 20:54:03 +0200 Received: from [192.168.0.2] (c-69-243-63-39.hsd1.md.comcast.net [69.243.63.39]) (authenticated bits=0) by dispatch.cs.umd.edu (8.13.1/8.12.5) with ESMTP id l8PIrjCx007363 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Tue, 25 Sep 2007 14:53:47 -0400 Message-ID: <46F95938.7030107@cs.umd.edu> Date: Tue, 25 Sep 2007 14:53:44 -0400 From: Mike Furr User-Agent: Mozilla-Thunderbird 2.0.0.4 (X11/20070828) MIME-Version: 1.0 To: caml-list Subject: [ANN] OCaml Reins 0.1 - Persistent Data Structure Library Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-CSD-MailScanner-Information: Please email staff@cs.umd.edu for more information X-CSD-MailScanner: Found to be clean X-CSD-MailScanner-SpamCheck: not spam, SpamAssassin (not cached, score=-4.392, required 5, autolearn=not spam, ALL_TRUSTED -1.80, AWL 0.01, BAYES_00 -2.60) X-CSD-MailScanner-From: furr@cs.umd.edu X-Miltered: at discorde with ID 46F95947.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 ocaml:01 catenable:01 big-endian:01 bool:01 functor:01 combinators:01 -unsafe:01 cheers:01 -mike:01 sourceforge:01 sourceforge:01 iterators:01 polymorphic:01 stack:01 I'm happy to announce the first source release of the OCaml Reins data structure library available at: http://ocaml-reins.sourceforge.net This project started as an "OCaml Summer Project" and is now continuing its development on sourceforge. The library already contains several implementations of persistent data structures and will continue to grow (possibly adding ephemeral data structures at some point if there's interest). Features of this release include: * List data types: o Single linked lists (compatible with the standard library type) o O(1) catenable lists o Acyclic double linked lists o Random access lists with O(1) hd/cons/tl and O(log n) lookup/update * Double ended queues * Sets/Maps with both polymorphic and monomorphic keys/values o AVL o Red/Black o Big-endian Patricia o Splay * Heaps: o Binomial o Skew Binomial * Zipper style cursor interfaces * Persistent, bi-directional, cursor based iterators (currently only for lists and sets) * All standard types hoisted into the module level (Int, Bool, etc...) * A collection of functor combinators to minimize boilerplate (e.g., constructing compare or to_string functions) * Quickcheck testing framework o Each structure provides a gen function that can generate a random instance of itself * Completely safe code. No -unsafe or references to Obj.* * Consistent function signatures. For instance, all fold functions take the accumulator in the same position. * All operations use no more than O(log n) stack space (except for a few operations on splay trees which currently have O(log n) expected time, but O(n) worst case) Cheers, -Mike