1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
open! Import
module type Key = sig
type t [@@deriving_inline compare, sexp_of]
val compare : t -> t -> int
val sexp_of_t : t -> Ppx_sexp_conv_lib.Sexp.t
[@@@end]
(** Values returned by [hash] must be non-negative. An exception will be raised in the
case that [hash] returns a negative value. *)
val hash : t -> int
end
module Hashable = struct
type 'a t =
{ hash : 'a -> int
; compare : 'a -> 'a -> int
; sexp_of_t : 'a -> Sexp.t
}
(** This function is sound but not complete, meaning that if it returns [true] then it's
safe to use the two interchangeably. If it's [false], you have no guarantees. For
example:
{[
> utop
open Core;;
let equal (a : 'a Hashtbl_intf.Hashable.t) b =
phys_equal a b
|| (phys_equal a.hash b.hash
&& phys_equal a.compare b.compare
&& phys_equal a.sexp_of_t b.sexp_of_t)
;;
let a = Hashtbl_intf.Hashable.{ hash; compare; sexp_of_t = Int.sexp_of_t };;
let b = Hashtbl_intf.Hashable.{ hash; compare; sexp_of_t = Int.sexp_of_t };;
equal a b;; (* false?! *)
]}
*)
let equal a b =
phys_equal a b
|| (phys_equal a.hash b.hash
&& phys_equal a.compare b.compare
&& phys_equal a.sexp_of_t b.sexp_of_t)
;;
let hash_param = Caml.Hashtbl.hash_param
let hash = Caml.Hashtbl.hash
let poly = { hash; compare = Poly.compare; sexp_of_t = (fun _ -> Sexp.Atom "_") }
let of_key (type a) (module Key : Key with type t = a) =
{ hash = Key.hash; compare = Key.compare; sexp_of_t = Key.sexp_of_t }
;;
let to_key (type a) { hash; compare; sexp_of_t } =
(module struct
type t = a
let hash = hash
let compare = compare
let sexp_of_t = sexp_of_t
end : Key
with type t = a)
;;
end
include Hashable
module type Hashable = sig
type 'a t = 'a Hashable.t =
{ hash : 'a -> int
; compare : 'a -> 'a -> int
; sexp_of_t : 'a -> Sexp.t
}
val equal : 'a t -> 'a t -> bool
val poly : 'a t
val of_key : (module Key with type t = 'a) -> 'a t
val to_key : 'a t -> (module Key with type t = 'a)
val hash_param : int -> int -> 'a -> int
val hash : 'a -> int
end
|
