# \[ANN\] patricia-tree 0.9.0 - library for patricia tree based maps and sets **URL:** \ **Category:** Community\ **Tags:** announce\ **Created:** [April 22, 2024, 2:17pm UTC](https://discuss.ocaml.org/t/ann-patricia-tree-0-9-0-library-for-patricia-tree-based-maps-and-sets/14535 "2024-04-22T14:17:50Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![dlesbre](https://avatars.discourse-cdn.com/v4/letter/d/bbce88/32.png) [@dlesbre](https://discuss.ocaml.org/u/dlesbre)\ **Post date:** [April 22, 2024, 2:17pm UTC](https://discuss.ocaml.org/t/ann-patricia-tree-0-9-0-library-for-patricia-tree-based-maps-and-sets/14535/1 "2024-04-22T14:17:50Z")
I’m happy to announce the release of a new `patricia-tree` library, version 0.9.0 on opam. This library that implements sets and maps as Patricia Trees, as described in Okasaki and Gill’s 1998 paper [_Fast mergeable integer maps_](https://www.semanticscholar.org/paper/Fast-Mergeable-Integer-Maps-Okasaki-Gill/23003be706e5f586f23dd7fa5b2a410cc91b659d). It is a space-efficient prefix trie over the big-endian representation of the key’s integer identifier. For full details, visit see [the documentation](https://codex.top/patricia-tree/) or [the source on github](https://github.com/codex-semantics-library/patricia-tree). ## Features - Similar to OCaml’s `Map` and `Set`, using the same function names when possible and the same convention for order of arguments. This should allow switching to and from Patricia Tree with minimal effort. - The functor parameters (`KEY` module) requires an injective `to_int : t -> int` function instead of a `compare` function. `to_int` should be fast, injective, and only return positive integers. This works well with [hash-consed](https://en.wikipedia.org/wiki/Hash_consing) types. - The Patricia Tree representation is stable, contrary to maps, inserting nodes in any order will return the same shape. This allows different versions of a map to share more subtrees in memory, and the operations over two maps to benefit from this sharing. The functions in this library attempt to **maximally preserve sharing and benefit from sharing** , allowing very important improvements in complexity and running time when combining maps or sets is a frequent operation. - Since our Patricia Tree use big-endian order on keys, the maps and sets are sorted in increasing order of keys. We only support positive integer keys. This also avoids a bug in Okasaki’s paper discussed in [_QuickChecking Patricia Trees_](https://www.cs.tufts.edu/comp/150FP/archive/jan-midtgaard/qc-patricia.pdf) by Jan Mitgaard. - Supports generic maps and sets: a `'m map` that maps `'k key` to `('k, 'm) value`. This is especially useful when using [GADTs](https://v2.ocaml.org/manual/gadts-tutorial.html) for the type of keys. This is also sometimes called a dependent map. - Allows easy and fast operations across different types of maps and set (e.g. an intersection between a map and a set), since all sets and maps, no matter their key type, are really positive integer sets or maps. - Multiple choices for internal representation (`NODE`), which allows for efficient storage (no need to store a value for sets), or using weak nodes only (values removed from the tree if no other pointer to it exists). This system can also be extended to store size information in nodes if needed. - Exposes a common interface (`view`) to allow users to write their own pattern matching on the tree structure without depending on the `NODE` being used. ## Comparison to other OCaml libraries ### ptmap and ptset There are other implementations of Patricia Tree in OCaml, namely [ptmap](https://github.com/backtracking/ptmap) and [ptset](https://github.com/backtracking/ptset). These are smaller and closer to OCaml’s built-in Map and Set, however: - Our library allows using any type `key` that comes with an injective `to_int` function, instead of requiring `key = int`. - We support generic (heterogeneous) types for keys/elements. - We support operations between sets and maps of different types. - We use a big-endian representation, allowing easy access to min/max elements of maps and trees. - Our interface and implementation tries to maximize the sharing between different versions of the tree, and to benefit from this memory sharing. Theirs do not. - These libraries work with older version of OCaml (`>= 4.05` I believe), whereas ours requires OCaml `>= 4.14` - Our keys are limited to positive integers. ### dmap Additionally, there is a dependent map library: [dmap](https://gitlab.inria.fr/bmontagu/dmap). It allows creating type safe dependent maps similar to our heterogeneous maps. However, its maps aren’t Patricia trees. They are binary trees build using a (polymorphic) comparison function, similarly to the maps of the standard library. Another difference is that the type of values in the map is independent of the type of the keys, allowing keys to be associated with different values in different maps. i.e. we map `'a key` to any `('a, 'b) value` type, whereas dmap only maps `'a key` to `'a`. `dmap` also works with OCaml `>= 4.12`, whereas we require OCaml `>= 4.14`. ---
**Author:** ![Matthieu\_Lemerre](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/matthieu_lemerre/32/4587_2.png) [@Matthieu\_Lemerre](https://discuss.ocaml.org/u/Matthieu_Lemerre)\ **Post date:** [April 24, 2024, 8:36am UTC](https://discuss.ocaml.org/t/ann-patricia-tree-0-9-0-library-for-patricia-tree-based-maps-and-sets/14535/2 "2024-04-24T08:36:44Z")
This library, developped by Dorian and me, was extracted from the Codex static analyzer, which was recently open sourced (and in a phase where we are writing documentation before doing a public announcement). For this reason, this library is particularly useful to implement efficient environments in an abstract interpreter (the performance of the merge is in `O(log(n)*d)`, where n is the number of bindings and d the number of mappings that differ between the two maps, instead of the `O(n)` cost of the OCaml standard `Map` based on AVL trees. ---
**Author:** ![Kakadu](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/kakadu/32/1204_2.png) [@Kakadu](https://discuss.ocaml.org/u/Kakadu)\ **Post date:** [April 24, 2024, 1:23pm UTC](https://discuss.ocaml.org/t/ann-patricia-tree-0-9-0-library-for-patricia-tree-based-maps-and-sets/14535/3 "2024-04-24T13:23:52Z")
Last time I was into integer keys, I got into feeling that we should deeply study a paper “Comparing Integer Data Structures for 32 and 64-bit Keys”. Authors have a benchmarks suite and a [paper PDF](https://github.com/nicknash/integer-structures/blob/master/jea_paper/paper.pdf) in Github. Also I found over the internet the implementations where guys are using “fat” nodes and pop count to select a right child to continue lookup ([in Haskell](https://github.com/ezyang/hamt)). Could you position your implementation with approaches from the paper and Haskell ones? ---
**Author:** ![esope](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/esope/32/2982_2.png) [@esope](https://discuss.ocaml.org/u/esope)\ **Post date:** [April 25, 2024, 2:18pm UTC](https://discuss.ocaml.org/t/ann-patricia-tree-0-9-0-library-for-patricia-tree-based-maps-and-sets/14535/4 "2024-04-25T14:18:49Z")
Thanks a lot @dlesbre and @Matthieu_Lemerre for releasing this library! I have a question for you: are your sets and maps themselves hash-consed? If not, do you have plans to implement this? (This would allow to have a constant-time equality test, save memory, and enable memoization for functions that manipulates such maps and sets!) ---
**Author:** ![esope](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/esope/32/2982_2.png) [@esope](https://discuss.ocaml.org/u/esope)\ **Post date:** [April 25, 2024, 3:27pm UTC](https://discuss.ocaml.org/t/ann-patricia-tree-0-9-0-library-for-patricia-tree-based-maps-and-sets/14535/5 "2024-04-25T15:27:50Z")
Minor correction when comparing with `dmap` (which I’m the author of). It is correct that `dmap` does not implement maps from keys of type `'a key` to values of type `('a, 'b) value`. However, `dmap` implements maps from keys of type `'a key` to values of type `'a value`, where `'a value` can be chosen by the client (it is the argument of a functor). See the module [`MakeWithValue`](https://ocaml.org/p/dmap/latest/doc/Dmap/MakeWithValue/index.html). This is slightly less general than what your library offers, but this remains quite flexible already. ---
**Author:** ![dlesbre](https://avatars.discourse-cdn.com/v4/letter/d/bbce88/32.png) [@dlesbre](https://discuss.ocaml.org/u/dlesbre)\ **Post date:** [April 25, 2024, 3:34pm UTC](https://discuss.ocaml.org/t/ann-patricia-tree-0-9-0-library-for-patricia-tree-based-maps-and-sets/14535/6 "2024-04-25T15:34:50Z")
Not yet, but with a custom `NODE` that should be fairly easy to do. We already have a `NodeWithId` which adds unique identifier to all newly generated nodes, all we need is a hashtable lookup to check if a similar node already exists. This is a good point, we’ll include it in the next release. Cf. [Draft: hashconsed maps nodes by dlesbre · Pull Request #1 · codex-semantics-library/patricia-tree · GitHub](https://github.com/codex-semantics-library/patricia-tree/pull/1) ---
**Author:** ![dlesbre](https://avatars.discourse-cdn.com/v4/letter/d/bbce88/32.png) [@dlesbre](https://discuss.ocaml.org/u/dlesbre)\ **Post date:** [April 25, 2024, 3:35pm UTC](https://discuss.ocaml.org/t/ann-patricia-tree-0-9-0-library-for-patricia-tree-based-maps-and-sets/14535/7 "2024-04-25T15:35:39Z")
Nicely spotted, sorry about that, I’ll correct it. Edit: It seems I can’t actually edit this post, but I’ve fixed it on github and in the package documentation. ---
**Author:** ![Matthieu\_Lemerre](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/matthieu_lemerre/32/4587_2.png) [@Matthieu\_Lemerre](https://discuss.ocaml.org/u/Matthieu_Lemerre)\ **Post date:** [April 25, 2024, 5:23pm UTC](https://discuss.ocaml.org/t/ann-patricia-tree-0-9-0-library-for-patricia-tree-based-maps-and-sets/14535/8 "2024-04-25T17:23:34Z")
Thanks for the references! The first paper does not mention Patricia Tries, so does not compare to it. Also, the comparison is done for C++, where allocation is inefficient and in-place mutation is fast, so probably the results they have would be quite different on an OCaml workload. That being said, I think the “burst” approach where we replace leaves by a small immutable array of leaves could be implemented on top of Patricia Tries – maybe with some small changes to the interface. It is probably also possible to group several interior nodes in a contiguous data structure. There are drawbacks though, notably there would be less cases where the shortcut in the merge function “if the subtrees are equal, then return the subtree as-is” would work. Regarding HAMT, I remember that I did once replaced Patricia Tries with HAMT (I think it was this implementation: [ocaml-hamt/src at master · recoules/ocaml-hamt · GitHub](https://github.com/recoules/ocaml-hamt/tree/master/src) ) which resulted in slower benchmarks. However, Array-mapped Tries (no need for hashing in our case) are also well-suited to fast merging, so maybe a fine-tuned implementation could be faster. Note however that AMT work well if you have a dense map; normal AMT do not have compression of the key, so e.g. a singleton map from 0b1 00000 00000 requires three interior nodes if every interior node can hold up to 32 keys. Patricia trees do not have this problem (which would also be solved by the burst approach). So, this work implements just Patricia Tries – but an optimized version of it. Comparing with other data structures would sure be very interesting – what we know is that this data structure is much more efficient that Map (based on AVL trees) for merge operation on large maps that originate from a common ancestor, a common situation in Abstract Interpretation.