O'Caml Reins

Welcome to the home page for the O'Caml Reins persistent data structure library. This project began as an OCaml Summer Project sponsored by Jane St. Capital and is now continuing on here at sourceforge. Since it is my goal to include as many data structures as possible in this library, I am always looking for contributions from others. Even if you don't have time to contribute code, but know of a data structure that you would like to see included, please let us know by sending a message to the mailing list. In addition to providing a large collection of data structures, the O'Caml Reins project also includes several features that I hope will make developing O'Caml applications easier such as a random testing framework and a collection of "standard" modules.

Current features

• List data types:
  • Single linked lists (compatible with the standard library type)
  • O(1) catenable lists
  • Acyclic double linked lists
  • Random access lists with O(1) hd/cons/tl and O(log i) lookup/update for i'th element
• Double ended queues
• Sets/Maps:
  • AVL
  • Red/Black
  • Big-endian Patricia
  • Splay
• Heaps:
  • Binomial
  • 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
  • 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)

Coming features

• Space and time asymptotic bounds on all functions
• Automatic benchmarking of all included data structures (based on Graeme Moss's PhD thesis)
  • Including a set of Oracle data structures which recommend a specific implementation based on observed executions
• Fill in missing functionality. For instance sets and maps need a {to,from}_list function and many list functions are still missing.
• More data structures:
  • weight balanced trees
  • persistent arrays
  • more heap implementations
• Iterators for maps and heaps
• 100% code coverage from the test suite
• Web based manual / tutorial for using some of the less intuitive features

More Information

Check out the sourceforce project page for access to svn, bug tracker, etc...
There is also a mailing list setup.
You can also browse the ocamldoc API pages available here

This page is hosted by: