aboutsummaryrefslogtreecommitdiffhomepage
path: root/lib/hashcons.mli
blob: cf3a09af4a8f4c88ddaf1c0cb836ed75e5ca5a0b (plain)
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
84
85
86
87
88
89
90
91
92
93
94
95
96
(************************************************************************)
(*  v      *   The Coq Proof Assistant  /  The Coq Development Team     *)
(* <O___,, *   INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2012     *)
(*   \VV/  **************************************************************)
(*    //   *      This file is distributed under the terms of the       *)
(*         *       GNU Lesser General Public License Version 2.1        *)
(************************************************************************)

(** Generic hash-consing. *)

(** {6 Hashconsing functorial interface} *)

module type HashconsedType =
  sig
    (** {6 Generic hashconsing signature}

        Given an equivalence relation [equal], a hashconsing function is a
        function that associates the same canonical element to two elements
        related by [equal]. Usually, the element chosen is canonical w.r.t.
        physical equality [(==)], so as to reduce memory consumption and
        enhance efficiency of equality tests.

        In order to ensure canonicality, we need a way to remember the element
        associated to a class of equivalence; this is done using a hidden state
        generated by the [Make] functor.
    *)

    type t
    (** Type of objects to hashcons. *)
    type u
    (** Type of hashcons functions for the sub-structures contained in [t].
        Usually a tuple of functions. *)
    val hashcons :  u -> t -> t
    (** The actual hashconsing function, using its fist argument to recursively
        hashcons substructures. It should be compatible with [equal], that is
        [equal x (hashcons f x) = true]. *)
    val equal : t -> t -> bool
    (** A comparison function. It is allowed to use physical equality
        on the sub-terms hashconsed by the [hashcons] function, but it should be
        insensible to shallow copy of the compared object. *)
    val hash : t -> int
    (** A hash function passed to the underlying hashtable structure. [hash]
        should be compatible with [equal], i.e. if [equal x y = true] then
        [hash x = hash y]. *)
  end

module type S =
  sig
    type t
    (** Type of objects to hashcons. *)
    type u
    (** Type of hashcons functions for the sub-structures contained in [t]. *)
    val generate : unit -> (u -> t -> t)
    (** This has the side-effect of creating (internally) a hashtable of the
        hashconsed objects. The result is a function taking the sub-hashcons
        functions and an object, and hashconsing it. It does not really make sense
        to call [generate] with different sub-hcons functions. That's why we use the
        wrappers [simple_hcons], [recursive_hcons], ... The latter just take as
        argument the sub-hcons functions (the tables are created at that moment),
        and returns the hcons function for [t]. *)
  end

module Make (X : HashconsedType) : (S with type t = X.t and type u = X.u)
(** Create a new hashconsing, given canonicalization functions. *)

(** {6 Wrappers} *)

(** These are intended to be used together with instances of the [Make]
    functor. *)

val simple_hcons : (unit -> 'u -> 't -> 't) -> ('u -> 't -> 't)
(** [simple_hcons f sub obj] creates a new table each time it is applied to any
    sub-hash function [sub]. *)

val recursive_hcons : (unit -> ('t -> 't) * 'u -> 't -> 't) -> ('u -> 't -> 't)
(** As [simple_hcons] but intended to be used with well-founded data structures. *)

val recursive2_hcons :
  (unit -> ('t1 -> 't1) * ('t2 -> 't2) * 'u1 -> 't1 -> 't1) ->
    (unit -> ('t1 -> 't1) * ('t2 -> 't2) * 'u2 -> 't2 -> 't2) ->
      'u1 -> 'u2 -> ('t1 -> 't1) * ('t2 -> 't2)
(** As [recursive_hcons] but with two mutually recursive structures. *)

(** {6 Hashconsing of usual structures} *)

module type HashedType = sig type t val hash : t -> int end

module Hstring : (S with type t = string and type u = unit)
(** Hashconsing of strings.  *)

module Hlist (D:HashedType) :
  (S with type t = D.t list and type u = (D.t list -> D.t list)*(D.t->D.t))
(** Hashconsing of lists.  *)

module Hobj : (S with type t = Obj.t and type u = (Obj.t -> Obj.t) * unit)
(** Hashconsing of OCaml values. *)