What is containers?
- A usable, reasonably well-designed library that extends OCaml's standard
core/, packaged under
containersin ocamlfind. Modules are totally independent and are prefixed with
CC(for "containers-core" or "companion-cube" because I'm megalomaniac). This part should be usable and should work. For instance,
CCListcontains functions and lists including safe versions of
append. It also provides a drop-in replacement to the standard library, in the module
Containers(intended to be opened, replaces some stdlib modules with extended ones)
- Several small additional libraries that complement it:
containers.datawith additional data structures that don't have an equivalent in the standard library;
containers.iowith utils to handle files and I/O streams;
containers.iterwith list-like and tree-like iterators;
string) with a few packed modules that deal with strings (Levenshtein distance, KMP search algorithm, and a few naive utils). Again, modules are independent and sometimes parametric on the string and char types (so they should be able to deal with your favorite unicode library).
- A sub-library with complicated abstractions,
containers.advanced(with a LINQ-like query module, batch operations using GADTs, and others).
- A library using Lwt,
containers.lwt. Currently only contains experimental, unstable stuff.
- Random stuff, with NO GUARANTEE of even being barely usable or tested,
in other dirs (mostly
threads). It's where I tend to write code when I want to test some idea, so half the modules (at least) are unfinished or don't really work.
Some of the modules have been moved to their own repository (e.g.
qcheck) and are on opam for great fun and profit.
See this file.
- the github wiki
- on IRC, ask
You can either build and install the library (see
Build), or just copy
files to your own project. The last solution has the benefits that you
don't have additional dependencies nor build complications (and it may enable
more inlining). Since modules have a friendly license and are mostly
independent, both options are easy.
If you have comments, requests, or bugfixes, please share them! :-)
This code is free, under the BSD license.
The logo (
The design is mostly centered around polymorphism rather than functors. Such
structures comprise (some modules in
misc/, some other in
Core Modules (extension of the standard library)
the core library,
containers, now depends on
CCHeap, a purely functional heap structure
CCVector, a growable array (pure OCaml, no C) with mutability annotations
CCList, functions on lists, including tail-recursive implementations of
appendand many other things
CCArray, utilities on arrays and slices
CCMapextensions of the standard modules
CCString(basic string operations)
CCOpt(options, very useful)
CCOrd(combinators for total orderings)
CCRandom(combinators for random generators)
CCError(monadic error handling, very useful)
CCCache, memoization caches, LRU, etc.
CCFlatHashtbl, a flat (open-addressing) hashtable functorial implementation
CCTrie, a prefix tree
CCMultiset, functors defining persistent structures
CCFQueue, a purely functional double-ended queue structure
CCBV, mutable bitvectors
CCPersistentHashtbl, a semi-persistent hashtable (similar to persistent arrays)
CCMixset, containers of universal types (heterogenous containers)
CCIO, basic utilities for IO
CCUnix, utils for
A small S-expression library.
CCSexp, a small S-expression library
CCKList, a persistent iterator structure (akin to a lazy list, without memoization)
CCKTree, an abstract lazy tree structure
In the module
Levenshtein: edition distance between two strings
KMP: Knuth-Morris-Pratt substring algorithm
In the module
CCLinq, high-level query language over collections
CCCat, a few categorical structures
CCBatch, to combine operations on collections into one traversal
See doc. This list is not necessarily up-to-date.
AbsSet, an abstract Set data structure, a bit like
CSM, state machine abstractions
Bij, a GADT-based bijection language used to serialize/deserialize your data structures
Hashset, a polymorphic imperative set on top of
LazyGraph, a lazy graph structure on arbitrary (hashable+eq) types, with basic graph functions that work even on infinite graphs, and printing to DOT.
PHashtbl, a polymorphic hashtable (with open addressing)
RAL, a random-access list structure, with
O(ln(n))access to elements by their index.
RoseTree, a tree with an arbitrary number of children and its associated zipper
SmallSet, a sorted list implementation behaving like a set.
UnionFind, a functorial imperative Union-Find structure
Univ, a universal type encoding with affectation
Future, a set of tools for preemptive threading, including a thread pool, monadic futures, and MVars (concurrent boxes)
containers.lwtcontains Lwt-related modules (experimental)
There is a QuickCheck-like library called
QCheck (now in its own repo).
You will need OCaml >= 4.01.0.
The prefered way to install is through opam.
$ opam install containers
On the branch
master you will need
oasis to build the library. On the
stable it is not necessary.
To build and run tests (requires
$ opam install oUnit qtest qcheck $ ./configure --enable-tests $ make test
To build the small benchmarking suite (requires
$ opam install benchmark $ make bench $ ./benchs.native
PRs on github are welcome (patches by email too, if you prefer so).
A few guidelines:
- no dependencies between basic modules (even just for signatures);
@sincetags for new functions;
- add tests if possible (using