This is documentation for the **development version** of Patricia Tree,
the latest released version is
**v0.10.0**.

Click here
to redirect to the latest version.

#
Patricia Tree API - `HeterogeneousHashedValue`

Generic implementation of `HETEROGENEOUS_HASHED_VALUE`

. Uses `Hashtbl.hash`

for hashing and physical equality for equality. Note that this may lead to maps of different types having the same identifier (`MakeHashconsedHeterogeneousMap.to_int`

), see the documentation of `HASHED_VALUE.polyeq`

for details on this.

The type of values for a hash-consed maps.

Unlike `HETEROGENEOUS_VALUE.t`

, **hash-consed values should be immutable**. Or, if they do mutate, they must not change their `hash`

value, and still be equal to the same values via `polyeq`

`val hash : ('key, 'map) t -> int`

`hash v`

should return an integer hash for the value `v`

. It is used for hash-consing.

Hashing should be fast, avoid mapping too many values to the same integer and compatible with `polyeq`

(equal values must have the same hash: `polyeq v1 v2 = true ==> hash v1 = hash v2`

).

Polymorphic equality on values.

**WARNING: if polyeq a b is true, then casting b to the type of a (and a to the type of b) must be type-safe.** Eg. if

`a : (k, t1) t`

and `b : (k, t2) t`

yield `polyeq a b = true`

, then `let a' : (k,t2) t = Obj.magic a`

and `let b' : (k,t1) t = Obj.magic b`

must be safe.Examples of safe implementations include:

Having a type

`('key, 'map) t`

which doesn't depend on`'map`

(i can depend on`'key`

), in which case casting form`('key, 'a) t`

to`('key, 'b) t`

is always safe:`type ('k, _) t = 'k list let cast : type a b. ('k, a) t -> ('k, b) t = fun x -> x let polyeq : type a b. ('k, a) t -> ('k, b) t -> bool = fun x y -> x = y`

Using a GADT type and examining its constructors to only return

`true`

when the constructors are equal:`type (_, _) t = | T_Int : int -> (unit, int) t | T_Bool : bool -> (unit, bool) t let polyeq : type k a b. (k, a) t -> (k, b) t -> bool = fun x y -> match x, y with | T_Int i, T_Int j -> i = j (* Here type a = b = int, we can return true *) | T_Bool i, T_Bool j -> i && j (* same here, but with a = b = bool *) | _ -> false (* never return true on heterogeneous cases. *)`

Using physical equality:

`let polyeq a b = a == Obj.magic b`

While this contains an

`Obj.magic`

, it is still type safe (OCaml just compares the immediate values) and we can safely cast values from one type to the other if they satisfy this (since they are already physically equal).This is the implementation used in

`HeterogeneousHashedValue`

. Note however that using this function can lead to**identifiers no longer being unique across types**. See`HASHED_VALUE.polyeq`

for more information on this.