Hashtable de variable mutable en Ocaml

Question

Necesito usar hashtable de variable mutable en Ocaml, pero no funciona.

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 

¿Hay alguna manera de hacerlo funcionar?

Answer 1

Las variables mutables que pueden tener el mismo contenido todavía pueden distinguirse porque están almacenadas en diferentes ubicaciones de la memoria. Se pueden comparar con el operador de igualdad física (==). Sin embargo, OCaml no proporciona nada mejor que la igualdad, no proporciona una función hash no trivial ni ordena las referencias, por lo que la única estructura de datos que puede compilar para almacenar referencias es una lista de asociaciones de alguna forma, con $ \ Theta (n) $ tiempo de acceso para la mayoría de los usos.

(En realidad, puede tocar el puntero subyacente si juega sucio. Pero el puntero puede moverse debajo de los pies. Sin embargo, hay una forma de utilizarlo, pero si necesita preguntar, no debe usar Y no estás lo suficientemente desesperado para eso de todos modos.)

Sería fácil comparar las referencias si dos referencias distintas tienen un contenido distinto. Así que hazlo así! Agregue un identificador único a sus referencias. Mantenga un contador global, increméntelo por 1 cada vez que cree una referencia, y almacene el valor del contador con los datos. Ahora sus referencias pueden ser indexadas por su valor de contador.

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) 

Para una mejor seguridad de tipos y la mejora de la eficiencia, definir una estructura de datos que contiene un valor de contador y un elemento.

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 

usted puede poner el código anterior en un módulo y hacer que el counter tipo abstracto. Además, puede definir un módulo de tabla hash utilizando la interfaz funcional Hashtbl. Aquí hay otra forma de definir variables y una estructura de tablas hash en ellas con una estructura más limpia y más modular.

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 

Necesitamos el módulo intermedio Variable porque el tipo variable es paramétrico y los funtores la estructura de datos de la biblioteca estándar (Hashtbl.Make, Set.Make, Map.Make) se define solamente para constructores de tipo con ningún argumento. Aquí hay una interfaz que expone tanto la interfaz polimórfica (con las funciones asociadas, pero no las estructuras de datos) como un funtor para construir cualquier cantidad de instancias monomórficas, con una tabla hash (y un conjunto, y un mapa) asociados.

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 

Tenga en cuenta que si usted espera que su programa puede generar más de 2^30 las variables durante la carrera, un int no se corte. Necesita dos valores int para obtener un valor de 2^60 bits o Int64.t.

Tenga en cuenta que si su programa es multiproceso, necesita un candado alrededor del mostrador, para hacer que el incremento y la búsqueda sean atómicos.

Answer 2

Puede usar la interfaz funcio- nal, que le permite suministrar sus propias funciones hash e igualdad. Luego, escribe funciones que se basan solo en las partes no mutables de sus valores. En este ejemplo, hay son sin partes no mutables. Por lo tanto, no está especialmente claro lo que esperas encontrar en la tabla. Pero en un ejemplo más realista (en mi experiencia) hay partes no mutables que puedes usar.

Si no hay partes no mutables, puede agregarlas específicamente para usar en hash. Podría agregar un entero exclusivo arbitrario a cada valor, por ejemplo.

También es posible hacer hash basado en la igualdad física (==), que tiene una definición razonable para las referencias (y otros valores mutables). Sin embargo, debes tener cuidado con esto, ya que la igualdad física es un poco complicada. Por ejemplo, no puede usar la dirección física de un valor como su clave hash; una dirección puede cambiar en cualquier momento debido a la recolección de basura.