Hashtable mutable variable in Ocaml

Question

I need to use the hash table of a mutable variable in Ocaml, but it does not work.

let link = Hashtbl.create 3;; let a = ref [1;2];; let b = ref [3;4];; Hashtbl.add link ab;; # Hashtbl.mem link a;; - : bool = true # a := 5::!a;; - : unit = () # Hashtbl.mem link a;; - : bool = false 

Is there any way to make it work?

Answer 1

Variables that can have the same content can still be distinguished, because they are stored in different places in memory. They can be compared with the physical equality operator ( == ). However, OCaml does not provide anything better than equality, it does not provide a nontrivial hash function or order for links, so the only data structure you can build to store links is a list of associations of some form with $ \ Theta (n) $ for most goals.

(If you play dirty, you can get the main pointer, but the pointer can move underfoot. Nevertheless, it is possible to use it, but if you need to ask, you should not use it. And yet you do not need it enough. )

It would be easy to compare links if two different links had separate content. So do it like that! Add a unique identifier to your links. Store the global counter, increment it by 1 each time you create a link and save the value of the counter with the data. Now your links can be indexed by their counter value.

 let counter = ref 0 let new_var x = incr counter; ref (!counter, x) let var_value v = snd !v let update_var vx = v := (fst !v, x) let hash_var v = Hashtbl.hash (fst !v) 

For better type safety and increased efficiency, define a data structure containing the counter value and element.

 let counter = ref 0 type counter = int type 'a variable = { key : counter; mutable data : 'a; } let new_var x = incr counter; {key = !counter; data = x} let hash_var v = Hashtbl.hash v.key 

You can put the code above in the module and create a counter tag. In addition, you can define a hash table using the Hashtbl functional interface. Here's another way to define variables and hash table structure on them with a cleaner, more modular structure.

 module Counter = (struct type t = int let counter = ref 0 let next () = incr counter; !counter let value c = c end : sig type t val next : unit -> t val value : t -> int end) module Variable = struct type 'a variable = { mutable data : 'a; key : Counter.t; } let make x = {key = Counter.next(); data = x} let update vx = v.data <- x let get v = v.data let equal v1 v2 = v1 == v2 let hash v = Counter.value v.key let compare v1 v2 = Counter.value v2.key - Counter.value v1.key end module Make = functor(A : sig type t end) -> struct module M = struct type t = At Variable.variable include Variable end module Hashtbl = Hashtbl.Make(M) module Set = Set.Make(M) module Map = Map.Make(M) end 

We need the Variable intermediate module, because the Variable type is parametric, and the standard library structure functions ( Hashtbl.Make , Set.Make , Map.Make ) are defined only for type constructors without an argument. Here is an interface that provides both a polymorphic interface (with related functions, but not data structures), and a functor for constructing any number of monomorphic instances with an associated type of hash table (and set and display).

 module Variable : sig type 'a variable val make : 'a -> 'a variable val update : 'a variable -> 'a -> unit val get : 'a variable -> 'a val equal : 'a -> 'a -> bool val hash : 'a variable -> int val compare : 'a variable -> 'b variable -> int end module Make : functor(A : sig type t end) -> sig module M : sig type t = At variable.variable val make : At -> t val update : t -> At -> unit val get : t -> At val equal : t -> t -> bool val hash : t -> int val compare : t -> t -> int end module Hashtbl : Hashtbl.S with type key = Mt module Set : Set.S with type key = Mt module Map : Map.S with type key = Mt end 

Note that if you expect your program to generate more than 2 ^ 30 variables during a run, int will not trim it. You need two int values ​​to make a 2 ^ 60-bit value, or Int64.t .

Please note that if your program is multi-threaded, you need a lock around the counter in order to increment and search for the atom.

Answer 2

You can use the functional interface that allows you to create your own hash functions and equality functions. Then you write functions that are based only on the immutable parts of your values. There are no non-moving parts in this example. Therefore, it is not particularly clear what you expect to find in the table. But in a more realistic example (in my experience) there are non-variable parts that you can use.

If there are no non-moving parts, you can add them specifically for use in hashing. For example, you can add an arbitrary unique integer to each value.

It is also possible to do hashing based on physical equality (==), which has a reasonable definition for references (and other mutable values). You have to be careful with him, although physical equality is a bit complicated. For example, you cannot use the physical address of a value as a hash key - the address can be changed at any time due to garbage collection.