index.mld

{0 Package patricia-tree}

This library contains a single module: {!PatriciaTree}.

This is version [0.11.0] of the library. It is known to work with OCaml versions
ranging from [4.14] to [5.3].

This is an {{: https://ocaml.org/}OCaml} library that implements sets and maps as
Patricia Trees, as described in Okasaki and Gill's 1998 paper
{{: https://www.semanticscholar.org/paper/Fast-Mergeable-Integer-Maps-Okasaki-Gill/23003be706e5f586f23dd7fa5b2a410cc91b659d}{i 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 {{: https://github.com/codex-semantics-library/patricia-tree}on Github}
under an {{: https://choosealicense.com/licenses/lgpl-2.1/}LGPL-2.1} license.

This library was written by {{: https://www.researchgate.net/profile/Matthieu-Lemerre}Matthieu Lemerre},
then further improved by {{: https://www.normalesup.org/~dlesbre/}Dorian Lesbre},
as part of the {{: https://codex.top/}Codex semantics library}, developed at
{{: https://list.cea.fr/en/} CEA List}.

{1:install Installation}

This library can be installed with {{: https://opam.ocaml.org/}opam}:
{@bash skip[
opam install patricia-tree
]}

Alternatively, you can clone the source repository and install with {{: https://dune.build/}dune}:
{@bash skip[
git clone git@github.com:codex-semantics-library/patricia-tree.git
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
]}

See the {{!examples}examples} to jump right into using this library.

{1 Features}

{ul
{li Similar to OCaml's {{: https://ocaml.org/api/Map.S.html}[Map]} and {{: https://ocaml.org/api/Set.S.html}[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.}
{li The functor parameters ({{!PatriciaTree.KEY}[KEY]} module) requires an injective [to_int : t -> int]
  function instead of a [compare] function. {{!PatriciaTree.KEY.to_int}[KEY.to_int]} should be fast,
  and injective.
  This works well with {{: https://en.wikipedia.org/wiki/Hash_consing}hash-consed} types.}
{li 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 {{!PatriciaTree.BASE_MAP.functions_on_pairs}operations over two maps} to benefit from this sharing. The functions in
  this library attempt to {b 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.

  To do so, these functions often have extra requirements on their argument
  (e.g. [inter f m1 m2] can be optimized by not inspecting common subtrees when
  [f] is idempotent). To avoid accidental errors, they are renamed (e.g. to
  [idempotent_inter] for the efficient version and [nonidempotent_inter_no_share]
  for the general one)}
{li Since our Patricia Tree use big-endian order on keys, the maps and sets are
  sorted in increasing {b {{!PatriciaTree.unsigned_lt}unsigned order}} of keys.
  This means negative keys are sorted above positive keys, with [-1] being the
  largest possible key, and [0] the smallest.
  This also avoids a bug in Okasaki's paper discussed in
  {{: https://www.cs.tufts.edu/comp/150FP/archive/jan-midtgaard/qc-patricia.pdf}{i QuickChecking Patricia Trees}}
  by Jan Mitgaard.

  It also affects functions like {{!PatriciaTree.BASE_MAP.unsigned_min_binding}[unsigned_min_binding]}
  and {{!PatriciaTree.BASE_MAP.pop_unsigned_minimum}[pop_unsigned_minimum]}. They will return the smallest
  positive integer of both positive and negative keys are present; and not the smallest negative,
  as one might expect.}
{li Supports generic maps and sets: a ['m map] that maps ['k key] to [('k, 'm) value].
  This is especially useful when using {{: https://v2.ocaml.org/manual/gadts-tutorial.html}GADTs}
  for the type of keys. This is also sometimes called a dependent map.}
{li Allows easy and fast operations across different types of maps and set
  which have the same type of keys (e.g. an intersection between a map and a set).}
{li Multiple choices for internal representation ({{!PatriciaTree.NODE}[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.}
{li Exposes a common interface ({!type:PatriciaTree.NODE.view}) to allow users to write their own pattern
  matching on the tree structure without depending on the {{!PatriciaTree.NODE}[NODE]} being used.}
{li Additionally, hashconsed versions of heterogeneous/homogeneous maps/sets are
  available. These provide constant time equality and comparison, and ensure
  maps/set with the same constants are always physically equal. It comes at the cost
  of a constant overhead in memory usage (at worst, as hash-consing may allow
  memory gains) and constant time overhead when calling constructors.}}

{1 Quick overview}

{2 Functors}

This library contains a single module, {!PatriciaTree}.
The functors used to build maps and sets are the following:
{ul
{li For homogeneous (non-generic) maps and sets: {{!PatriciaTree.MakeMap}[MakeMap]} and
    {{!PatriciaTree.MakeSet}[MakeSet]}. These are similar to the standard library's maps and sets.
    {@ocaml skip[
      module MakeMap(Key: KEY) : MAP with type key = Key.t
      module MakeSet(Key: KEY) : SET with type elt = Key.t
    ]}}
{li For Heterogeneous (generic) maps and sets: {{!PatriciaTree.MakeHeterogeneousMap}[MakeHeterogeneousMap]}
    and {{!PatriciaTree.MakeHeterogeneousSet}[MakeHeterogeneousSet]}.
    {@ocaml skip[
      module MakeHeterogeneousMap(Key: HETEROGENEOUS_KEY)(Value: HETEROGENEOUS_VALUE) :
        HETEROGENEOUS_MAP
        with type 'a key = 'a Key.t
         and type ('k,'m) value = ('k,'m) Value.t
      module MakeHeterogeneousSet(Key: HETEROGENEOUS_KEY) : HETEROGENEOUS_SET
        with type 'a elt = 'a Key.t
    ]}}
{li
  There are also {{: https://en.wikipedia.org/wiki/Hash_consing}hash-consed} versions
  of these four functors: {{!PatriciaTree.MakeHashconsedMap}[MakeHashconsedMap]}, {{!PatriciaTree.MakeHashconsedSet}[MakeHashconsedSet]},
  {{!PatriciaTree.MakeHashconsedHeterogeneousMap}[MakeHashconsedHeterogeneousMap]} and {{!PatriciaTree.MakeHashconsedHeterogeneousSet}[MakeHashconsedHeterogeneousSet]}.
  These uniquely number their nodes, which means:
  - [equal] and [compare] become constant time operations;
  - two maps with the same bindings (where keys are compared by {{!PatriciaTree.KEY.to_int}[KEY.to_int]} and
    values by {{!PatriciaTree.HASHED_VALUE.polyeq}[HASHED_VALUE.polyeq]}) will always be physically equal;
  - functions that benefit from sharing will see improved performance;
  - constructors are slightly slower, as they now require a hash-table lookup;
  - memory usage is increased: nodes store their tags inside themselves, and
    a global hash-table of all built nodes must be maintained;
  - hash-consed maps assume their values are immutable;
  - {b WARNING:} when using physical equality as {{!PatriciaTree.HASHED_VALUE.polyeq}[HASHED_VALUE.polyeq]}, some maps of different
    types may be given the same identifier.  See the end of
    the documentation of {{!PatriciaTree.HASHED_VALUE.polyeq}[HASHED_VALUE.polyeq]} for details.
    Note that this is the case in the default implementations
    {{!PatriciaTree.HashedValue}[HashedValue]}
    and {{!PatriciaTree.HeterogeneousHashedValue}[HeterogeneousHashedValue]}.
  - All hash-consing functors are {b generative}, since each functor call will
    create a new hash-table to store the created nodes. Calling a functor
    twice with same arguments will lead to two numbering systems for identifiers,
    and thus the types should not be considered compatible.
}}

{2 Interfaces}

Here is a brief overview of the various module types of our library:
{ul
{li {{!PatriciaTree.BASE_MAP}[BASE_MAP]}: the underlying module type of all our trees (maps end sets). It
  represents a ['b map] binding ['a key] to [('a,'b) value], as well as all
  functions needed to manipulate them.

  It can be accessed from any of the more specific maps types, thus providing a
  unified representation, useful for cross map operations. However, for practical
  purposes, it is often best to use the more specific interfaces:
  {ul
  {li {{!PatriciaTree.HETEROGENEOUS_MAP}[HETEROGENEOUS_MAP]} for heterogeneous maps (this is just {{!PatriciaTree.BASE_MAP}[BASE_MAP]} with a
    [WithForeign] functor).}
  {li {{!PatriciaTree.MAP}[MAP]} for homogeneous maps, this interface is close to {{: https://ocaml.org/api/Map.S.html}[Stdlib.Map.S]}.}
  {li {{!PatriciaTree.HETEROGENEOUS_SET}[HETEROGENEOUS_SET]} for heterogeneous sets (sets of ['a elt]). These are just
    maps to [unit], but with a custom node representation to avoid storing [unit] in
    nodes.}
  {li {{!PatriciaTree.SET}[SET]} for homogeneous sets, this interface is close to {{: https://ocaml.org/api/Set.S.html}[Stdlib.Set.S]}.}
  }}
{li The parameter of our functor are either {{!PatriciaTree.KEY}[KEY]} or {{!PatriciaTree.HETEROGENEOUS_KEY}[HETEROGENEOUS_KEY]}.
  These just consist of a type, a (polymorphic) equality function, and an
  injective [to_int] coercion.

  The heterogeneous map functor also has a {{!PatriciaTree.HETEROGENEOUS_VALUE}[HETEROGENEOUS_VALUE]} parameter to specify the
  [('a, 'b) value] type.}
{li The internal representations of our tree can be customized to use different
  internal {{!PatriciaTree.NODE}[NODE]}. Each node come with its own private constructors and destructors,
  as well as a cast to a uniform {{!type:PatriciaTree.NODE.view}[NODE.view]} type used for pattern matching.

  A number of implementations are provided:
  - {{!PatriciaTree.SimpleNode}[SimpleNode]}: exactly the {{!type:PatriciaTree.NODE.view}[NODE.view]} type;
  - {{!PatriciaTree.WeakNode}[WeakNode]}: only store weak pointer to its elements;
  - {{!PatriciaTree.NodeWithId}[NodeWithId]}: node which contains a unique identifier;
  - {{!PatriciaTree.SetNode}[SetNode]}: optimized for sets, doesn't store the [unit] value;
  - {{!PatriciaTree.WeakSetNode}[WeakSetNode]}: both a {{!PatriciaTree.WeakNode}[WeakNode]} and a {{!PatriciaTree.SetNode}[SetNode]}
  - {{!PatriciaTree.HashconsedNode}[HashconsedNode]}: performs hash-consing (it also stores a unique identifier, but checks when
    building a new node whether a node with similar content already exists);
  - {{!PatriciaTree.HashconsedSetNode}[HashconsedSetNode]}: both a {{!PatriciaTree.HashconsedNode}[HashconsedNode]} and a {{!PatriciaTree.SetNode}[SetNode]}.

  Use the functors {{!PatriciaTree.MakeCustomMap}[MakeCustomMap]} and {{!PatriciaTree.MakeCustomSet}[MakeCustomSet]}
  (or their heterogeneous versions {{!PatriciaTree.MakeCustomHeterogeneousMap}[MakeCustomHeterogeneousMap]} and
  {{!PatriciaTree.MakeCustomHeterogeneousSet}[MakeCustomHeterogeneousSet]}) to build
  maps using these nodes, or any other custom nodes.}
}

{1:examples Examples}

To use this library, {{!install}install it} and add the following to your
dune files:
{@dune[
(executable ; or library
  ...
  (libraries patricia-tree ...)
)
]}

{2 Homogeneous map}

Here is a small example of a non-generic map:

{ol
{li Start by creating a key module. We use [type int] for keys in this example,
    but you can use any type, so long as it supports an efficient and injective
    {{!PatriciaTree.KEY.to_int}[to_int]} function.
  {@ocaml[
  module IntKey : PatriciaTree.KEY with type t = int = struct
    type t = int
    let to_int x = x (* to_int must be injective and fast *)
  end
  ]}}
{li Use it to instanciate the map/set functors:
  {[
  module IMap : PatriciaTree.MAP with type key = int
              = PatriciaTree.MakeMap(IntKey)

  module ISet : PatriciaTree.SET with type elt = int
              = PatriciaTree.MakeSet(IntKey)
  ]}}
{li You can now use it as you would any other map, most of the interface is
    shared with the standard library's {{: https://ocaml.org/api/Map.S.html}[Map]}
    and {{: https://ocaml.org/api/Set.S.html}[Set]} (some functions have
    been renamed to highlight their differing requirements).
  {[
  # let map =
    IMap.empty |>
    IMap.add 1 "hello" |>
    IMap.add 2 "world" |>
    IMap.add 3 "how do you do?";;
  val map : string IMap.t = <abstr>
  ]}
  (We also have {{!PatriciaTree.MAP.of_list}[of_list]} and
  {{!PatriciaTree.MAP.of_seq}[of_seq]} functions for quick initialization)
  {[
  # IMap.find 1 map;;
  - : string = "hello"

  # IMap.cardinal map;;
  - : int = 3
  ]}}
{li The strength of Patricia Tree is the speedup of operations on multiple maps
    with common subtrees. For example, in the following, the
    {{!PatriciaTree.MAP.idempotent_inter_filter}[idempotent_inter_filter]} function
    will skip recursive calls to physically equal subtrees (kept as-is in the intersection).
    This allows faster than [O(n)] intersections.
  {[
  # let map2 =
      IMap.idempotent_inter_filter (fun _key _l _r -> None)
        (IMap.add 4 "something" map)
        (IMap.add 5 "something else" map);;
  val map2 : string IMap.t = <abstr>

  # map == map2;;
  - : bool = true
  ]}
  Physical equality is preserved as much as possible, although some intersections
  may need to build new nodes and won't be fully physically equal, they will
  still share some subtrees.
  {[
  # let str = IMap.find 1 map;;
  val str : string = "hello"

  # IMap.add 1 str map == map (* already present *);;
  - : bool = true

  # IMap.add 1 "hello" map == map
    (* new string copy isn't physically equal to the old one *);;
  - : bool = false
  ]}
  Note that physical equality isn't preserved when creating new copies of values
  (the newly created string ["hello"] isn't physically equal to [str]).
  It can also fail when maps have the same bindings but were created differently:
  {[
    # let map3 = IMap.remove 2 map;;
    val map3 : string IMap.t = <abstr>

    # IMap.add 2 (IMap.find 2 map) map3 == map;;
    - : bool = false
  ]}
  If you want to maintain full physical equality (and thus get
  cheap equality test between maps), use the provided
  {{!PatriciaTree.section-hash_consed}hash-consed maps and sets}.}
{li Our library also allows cross map/set operations through the
  {{!PatriciaTree.MAP.WithForeign}[WithForeign]} functors:
  {[
    module CrossOperations = IMap.WithForeign(ISet.BaseMap)
  ]}
  For example, you can only keep the bindings of [map]
  whose keys are in a given set:
  {[
    # let set = ISet.of_list [1; 3];;
    val set : ISet.t = <abstr>

    # let restricted_map = CrossOperations.nonidempotent_inter
      { f = fun _key value () -> value } map set;;
    val restricted_map : string IMap.t = <abstr>

    # IMap.to_list map;;
    - : (int * string) list = [(1, "hello"); (2, "world"); (3, "how do you do?")]

    # IMap.to_list restricted_map;;
    - : (int * string) list = [(1, "hello"); (3, "how do you do?")]
  ]}
}}

{2 Heterogeneous map}

Heterogeneous maps work very similarly to homogeneous ones, but come with extra
liberty of having a generic type as a key.

{ol
{li Here is a GADT example to use for our keys: a small typed expression language.
    {[
      type 'a expr =
        | G_Const_Int : int -> int expr
        | G_Const_Bool : bool -> bool expr
        | G_Addition : int expr * int expr -> int expr
        | G_Equal : 'a expr * 'a expr -> bool expr
    ]}
    We can create our {{!PatriciaTree.HETEROGENEOUS_KEY}[HETEROGENEOUS_KEY]} functor
    parameter using this type as follows:
    {[
      module Expr : PatriciaTree.HETEROGENEOUS_KEY with type 'a t = 'a expr = struct
        type 'a t = 'a expr

        (** Injective, so long as expressions are small enough
            (encodes the constructor discriminant in two lowest bits).
            Ideally, use a hash-consed type, to_int needs to be fast *)
        let rec to_int : type a. a expr -> int = function
          | G_Const_Int i ->   0 + 4*i
          | G_Const_Bool b ->  1 + 4*(if b then 1 else 0)
          | G_Addition(l,r) -> 2 + 4*(to_int l mod 10000 + 10000*(to_int r))
          | G_Equal(l,r) ->    3 + 4*(to_int l mod 10000 + 10000*(to_int r))

        (** Full polymorphic equality, requires annotation to type properly *)
        let rec polyeq : type a b. a expr -> b expr -> (a, b) PatriciaTree.cmp =
          fun l r -> match l, r with
          | G_Const_Int l, G_Const_Int r -> if l = r then Eq else Diff
          | G_Const_Bool l, G_Const_Bool r -> if l = r then Eq else Diff
          | G_Addition(ll, lr), G_Addition(rl, rr) -> (
              match polyeq ll rl with
              | Eq -> polyeq lr rr
              | Diff -> Diff)
          | G_Equal(ll, lr), G_Equal(rl, rr) ->    (
              match polyeq ll rl with
              | Eq -> (* this match is no-op, but it is required to typecheck *)
                      (match polyeq lr rr with Eq -> Eq | Diff -> Diff)
              | Diff -> Diff)
          | _ -> Diff
      end
    ]}
    Note the full polymorphic equality, that returns a GADT term {!PatriciaTree.cmp}
    which, when equal ({{!PatriciaTree.Eq}[Eq]}), is a proof of type equality
    between the type parameters.}
{li We can now instanciate our map functor. Note that in the heterogeneous case,
    we must also specify the value type (second functor argument) and how it depends
    on the key type (first parameter) and the map type (second parameter).
    Here the value only depends on the type of the key, not that of the map
    {[
      module EMap = PatriciaTree.MakeHeterogeneousMap
                      (Expr)
                      (struct type ('key, 'map) t = 'key end)
    ]}}
{li You can now use this as you would any other dependent map:
    {[
      # let map : unit EMap.t =
        EMap.empty |>
        EMap.add (G_Const_Bool false) false |>
        EMap.add (G_Const_Int 5) 5 |>
        EMap.add (G_Addition (G_Const_Int 3, G_Const_Int 6)) 9 |>
        EMap.add (G_Equal (G_Const_Bool false, G_Equal (G_Const_Int 5, G_Const_Int 7))) true
      val map : unit EMap.t = <abstr>

      # EMap.find (G_Const_Bool false) map;;
      - : bool = false

      # EMap.find (G_Const_Int 5) map;;
      - : int = 5

      # EMap.cardinal map;;
      - : int = 4
    ]}}
{li Physical equality preservation allows fast operations on multiple maps with common
    ancestors. In the heterogeneous case, these functions are a bit more complex
    since OCaml requires that first-order polymorphic functions be wrapped in records:
    {[
      # let map2 = EMap.idempotent_inter_filter
          { f = fun _key _l _r -> None } (* polymorphic 1rst order functions are wrapped in records *)
          (EMap.add (G_Const_Int 0) 8 map)
          (EMap.add (G_Const_Int 0) 9 map)
      val map2 : unit EMap.t = <abstr>
    ]}
    Even though [map] and [map2] have the same elements, they may not always
    be physically equal:
    {[
      # map == map2;;
      - : bool = false
    ]}
    This is because they were created through different processes. They will still
    share subtrees. If you want to maintain full physical equality (and thus get
    cheap equality test between maps), use the provided
    {{!PatriciaTree.section-hash_consed}hash-consed maps and sets}.
}}


{1 Release status}

This should be close to a stable release. It is already being
used as part of a {{: https://codex.top}larger project} successfully, and this usage as helped us mature
the interface. As is, we believe the project is usable, and we don't anticipate
any major change before 1.0.0. We didn't commit to a stable release straight
away as we would like a bit more time using this library before doing so.

{1 Known issues}

There is a bug in the OCaml typechecker which prevents us from directly
defining non-generic maps as instances of generic maps. To avoid this, non-generic maps
use a separate value type {{!PatriciaTree.snd}[('a, 'b) snd]} (instead of just using ['b])
{[
type (_, 'b) snd = Snd of 'b [@@unboxed]
]}
It should not incur any extra performance cost as it is unboxed, but can appear
when manipulating non-generic maps.

For more details about this issue, see {{: https://discuss.ocaml.org/t/weird-behaviors-with-first-order-polymorphism/13783}the OCaml discourse discussion}
or {{: https://github.com/ocaml/ocaml/issues/13292}the github issue}.

{1 Comparison to other OCaml libraries}

{2 ptmap and ptset}

There are other implementations of Patricia Tree in OCaml, namely
{{: https://github.com/backtracking/ptmap}ptmap} and
{{: https://github.com/backtracking/ptset}ptset}, both by J.C. Filliatre.
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 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] (for the new interface of {{: https://v2.ocaml.org/api/Ephemeron.html}[Ephemeron]} used in
  {{!PatriciaTree.WeakNode}[WeakNode]}).

{2 dmap}

Additionally, there is a dependent map library: {{: https://gitlab.inria.fr/bmontagu/dmap}dmap},
which gave us the idea of making our PatriciaTree dependent.
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 from 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] or ['a value].

[dmap] also works with OCaml [>= 4.12], whereas we require OCaml [>= 4.14].

{1 Contributions and bug reports}

Any contributions are welcome!

You can report any bug, issues, or desired features using the {{: https://github.com/codex-semantics-library/patricia-tree/issues}Github issue tracker}.
Please include OCaml, dune, and library version information in you bug reports.

If you want to contribute code, feel free to fork {{: https://github.com/codex-semantics-library/patricia-tree}the repository on Github}
and open a pull request. By doing so you agree to release your code under this
project's license ({{: https://choosealicense.com/licenses/lgpl-2.1/}LGPL-2.1}).


There is no imposed coding style for this repository, here are just a few guidelines and conventions:
- Module type names should use [SCREAMING_SNAKE_CASE].
- Module and functor names use [PascalCase], functors names start with [Make].
- Even though the library implements homogeneous maps as a specialization of
  heterogeneous ones, the naming convention is that no prefix means homogeneous,
  and all heterogeneous objects are prefixed with [heterogeneous].
- Please document any new functions in the interface, using {{: https://v2.ocaml.org/manual/ocamldoc.html#s%3Aocamldoc-comments}ocamldoc style comments}.
- Please consider adding test for new features/fixed bugs if at all possible.
  This library uses a {{: https://www.ocaml.org/p/quickcheck/latest/doc/QuickCheck/index.html}QuickCheck} framework for tests.