Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[ANN] OCaml Reins 0.1 - Persistent Data Structure Library
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-09-25 (18:54)
From: Mike Furr <furr@c...>
Subject: [ANN] OCaml Reins 0.1 - Persistent Data Structure Library

I'm happy to announce the first source release of the OCaml Reins data 
structure library available at:

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 

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)
   * 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)