home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / src / compiler / Hasht.sig < prev    next >
Encoding:
Text File  |  1997-08-18  |  3.0 KB  |  70 lines  |  [TEXT/R*ch]
  1. (* Hasht.sig *)
  2.  
  3. (* Hash tables and hash functions *)
  4.  
  5. (* Hash tables are hashed association tables, with in-place modification. *)
  6.  
  7. type ('a, 'b) t;
  8.         (* The type of hash tables from type ['a] to type ['b]. *)
  9.  
  10. val new : int -> ('_a, '_b) t;
  11.         (* [new n] creates a new, empty hash table, with initial size [n].
  12.            The table grows as needed, so [n] is just an initial guess.
  13.            Better results are said to be achieved when [n] is a prime
  14.            number. *)
  15.  
  16. val clear : ('a, 'b) t -> unit;
  17.         (* Empty a hash table. *)
  18.  
  19. val insert : (''_a, '_b) t -> ''_a -> '_b -> unit;
  20.         (* [insert tbl x y] adds a binding of [x] to [y] in table [tbl].
  21.            The previous binding for [x] is removed (if any). *)
  22.  
  23. val find : (''a, 'b) t -> ''a -> 'b;
  24.         (* [find tbl x] returns the current binding of [x] in [tbl],
  25.            or raises [Subscript] if no such binding exists. *)
  26.  
  27. val peek : (''a, 'b) t -> ''a -> 'b option;
  28.         (* [peek tbl x] returns SOME v, where v is the current binding of
  29.            x in tbl, if any; otherwise returns NONE. *)
  30.  
  31. val remove : (''a, 'b) t -> ''a -> unit;
  32.         (* [remove tbl x] removes the current binding of [x] in [tbl].
  33.            It does nothing if [x] is not bound in [tbl]. *)
  34.  
  35. val apply : ('a -> 'b -> unit) -> ('a, 'b) t -> unit;
  36.         (* [apply f tbl] applies [f] to all bindings in table [tbl].
  37.            [f] receives the key as first argument, and the associated
  38.            value as second argument. The order in which the bindings
  39.            are passed to [f] is unpredictable. *)
  40.  
  41. val fold : ('a -> 'b -> 'c -> 'c) -> 'c -> ('a, 'b) t -> 'c
  42.         (* [fold f e tbl] computes f k1 d1 (f k2 d2 (...(f kn dn c)...)) 
  43.            where (k1, d1), (k2, d2), ..., (kn, dn) are the bindings of 
  44.        tbl in some unpredictable order. *)
  45.  
  46. (*** The polymorphic hash primitive *)
  47.  
  48. val hash : 'a -> int;
  49.         (* [hash x] associates a positive integer to any value of
  50.            any type. It is guaranteed that
  51.                 if [x = y], then [hash x = hash y].
  52.            Moreover, [hash] always terminates, even on cyclic
  53.            structures. *)
  54.  
  55. prim_val hash_param : int -> int -> 'a -> int = 3 "hash_univ_param";
  56.         (* [hash_param n m x] computes a hash value for [x], with the
  57.            same properties as for [hash]. The two extra parameters
  58.            [n] and [m] give more precise control over hashing.
  59.            Hashing performs a depth-first, right-to-left traversal of
  60.            the structure [x], stopping after [n] meaningful nodes
  61.            were encountered, or [m] nodes, meaningful or not, were
  62.            encountered. Meaningful nodes are: integers;
  63.            floating-point numbers; strings; characters; booleans; and
  64.            constant constructors. Larger values of [m] and [n] means
  65.            that more nodes are taken into account to compute the
  66.            final hash value, and therefore collisions are less likely
  67.            to happen.  However, hashing takes longer. The parameters
  68.            [m] and [n] govern the tradeoff between accuracy and
  69.            speed. *)
  70.