Hashtable of mutable variable in Ocaml

Question

I need to use hashtable of mutable variable in Ocaml, but it doesn't work out.

let link = Hashtbl.create 3;;
let a = ref [1;2];;
let b = ref [3;4];;
Hashtbl.add link a b;;

# Hashtbl.mem link a;;
- : bool = true

# a := 5::!a;;
- : unit = ()

# Hashtbl.mem link a;;
- : bool = false

Is there any way to make it works?

Answer 1

You can use the functorial interface, which lets you supply your own hash and equality functions. Then you write functions that are based only on the non-mutable parts of your values. In this example, there are no non-mutable parts. So, it's not especially clear what you're expecting to find in the table. But in a more realistic example (in my experience) there are non-mutable parts that you can use.

If there aren't any non-mutable parts, you can add them specifically for use in hashing. You could add an arbitrary unique integer to each value, for example.

It's 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 it, though, as physical equality is a little tricky. For example, you can't use the physical address of a value as your hash key--an address can change at any time due to garbage collection.

Answer 2

Mutable variables that may happen to have the same content can still be distinguished because they are stored at different locations in memory. They can be compared with the physical equality operator (==). However, OCaml doesn't provide anything better than equality, it doesn't provide a nontrivial hash function or order on references, so the only data structure you can build to store references is an association list of some form, with $\Theta(n)$ access time for most uses.

(You can actually get at the underlying pointer if you play dirty. But the pointer can move under your feet. There is a way to make use of it nonetheless, but if you need to ask, you shouldn't use it. And you aren't desperate enough for that anyway.)

It would be easy to compare references if two distinct references had a distinct content. So make it so! Add a unique identifier to your references. Keep a global counter, increment it by 1 each time you create a reference, and store the counter value with the data. Now your references 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 v x = v := (fst !v, x)
let hash_var v = Hashtbl.hash (fst !v)

For better type safety and improved efficiency, define a data structure containing a counter value and an item.

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 a module and make the counter type abstract. Also, you can define a hash table module using the Hashtbl functorial interface. Here's another way to define variables and a 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 v x = 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 = A.t Variable.variable
    include Variable
  end
  module Hashtbl = Hashtbl.Make(M)
  module Set = Set.Make(M)
  module Map = Map.Make(M)
end

We need the intermediate module Variable because the type variable is parametric and the standard library data structure functors (Hashtbl.Make, Set.Make, Map.Make) are only defined for type constructors with no argument. Here's an interface that exposes both the polymorphic interface (with the associated functions, but no data structures) and a functor to build any number of monomorphic instances, with an associated hash table (and set, and map) type.

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 = A.t variable.variable
    val make : A.t -> t
    val update : t -> A.t -> unit
    val get : t -> A.t
    val equal : t -> t -> bool
    val hash : t -> int
    val compare : t -> t -> int
  end
  module Hashtbl : Hashtbl.S with type key = M.t
  module Set : Set.S with type key = M.t
  module Map : Map.S with type key = M.t
end

Note that if you expect that your program may generate more than 2^30 variables during a run, an int won't cut it. You need two int values to make a 2^60-bit value, or an Int64.t.

Note that if your program is multithreaded, you need a lock around the counter, to make the incrementation and lookup atomic.