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:
- 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
There are several features that were not quite ready for this release
but are in the works:
- 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: