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 - `HASHED_VALUE`

VALUE parameter for Hash-consed maps and sets, as hash-consing requires hashing and comparing values.

This is the parameter type for homogeneous maps, used in MakeHashconsedMap. A default implementation is provided in HashedValue, using Hashtbl.hash as hash function and physical equality as polyeq.

since 0.10.0

type 'a t

The type of values for a hash-consed maps.

Unlike 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 : '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).

val polyeq : 'a t -> 'b t -> bool

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 : t1 t and b : t2 t yield polyeq a b = true, then let a' : t2 t = Obj.magic a and let b' : t1 t = Obj.magic b must be safe.

Examples of safe implementations include:

Having a type 'a t which doesn't depend on 'a, in which case casting from 'a t to 'b t is always safe:

type _ t = foo
let cast : type a b. a t -> b t = fun x -> x
let polyeq : type a b. a t -> 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 (or have the same type parameter):

type _ t =
    | T_Int : int -> int t
    | T_Bool : bool -> bool t
let polyeq : type a b. a t -> 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 HashedValue. Note however that using this function can lead to identifiers no longer being unique across types. They will still be unique and behave as expected within a certain type, but since some values of different types can physically equal, we may have identifer clashes:
```
# 97 == Obj.magic 'a';;
- : bool = true
```
```
module HMap = MakeHashconsedMap(struct
    type t = int
    let to_int x = x
end)(HashedValue)()
```
```
# let m1 = HMap.singleton 5 97;;
val m1 : int HMap.t = <abstr>
# let m2 = HMap.singleton 5 'a';;
val m2 : char HMap.t = <abstr>
# HMap.to_int m1 = HMap.to_int m2;;
- : bool = true
```
This can cause problems if you wish to use identifiers of different map types together:
```
type any = Any : 'a HMap.t -> any
module MapOfMaps = MakeMap(struct
  type t = any
  let to_int (Any x) = HMap.to_int x
end)
```
Using this can lead to unexpected behaviors: in the following m3 has cardinal 1, the m1->"foo" binding has been overwritten:
```
# let m3 = MapOfMaps.of_list [ (Any m1, "foo"); (Any m2, "bar") ]
val m3 : string MapOfMaps.t = <abstr>
# MapOfMaps.to_list m3
- : (any * string) list = [(Any <abstr>, "bar")]
```
This issue does not happen with the two previous variants, since they both only return true on the same types.

Patricia Tree API - HASHED_VALUE

Patricia Tree API - `HASHED_VALUE`