Patricia Tree API

Opam packageLatest releaseOCaml versionsLicenseBuild

This is an OCaml library that implements sets and maps as Patricia Trees, as described in Okasaki and Gill’s 1998 paper Fast mergeable integer maps. It is a space-efficient prefix trie over the big-endian representation of the key’s integer identifier.

The source code of this library is available on Github under an LGPL-2.1 license.

For a quick overview of how to use the library, see the examples.

Documentation versions

See any of these for more details on this library, what it can do, some small examples and the full documentation.

Changes between versions are listed in the changelog.


This library can be installed with opam:

opam install patricia-tree

Alternatively, you can clone the source repository and compile with dune:

git clone
cd patricia-tree
opan install . --deps-only
dune build -p patricia-tree
dune install
# To build documentation
opam install . --deps-only --with-doc
dune build @doc