Hashtable della variabile mutabile in Ocaml

Question

Ho bisogno di usare l'hashtable della variabile mutabile in Ocaml, ma non funziona.

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 

C'è un modo per farlo funzionare?

Answer 1

Le variabili mutabili che possono capitare di avere lo stesso contenuto possono ancora essere distinte perché sono memorizzate in posizioni diverse nella memoria. Possono essere confrontati con l'operatore di uguaglianza fisica (==). Tuttavia, OCaml non fornisce nulla di meglio dell'uguaglianza, non fornisce una funzione hash non banale o un ordine sui riferimenti, quindi l'unica struttura di dati che è possibile creare per memorizzare riferimenti è un elenco di associazioni di qualche forma, con $ \ Theta (n) $ tempo di accesso per la maggior parte degli usi.

(Si può effettivamente raggiungere il puntatore sottostante se giochi sporco, ma il puntatore può spostarsi sotto i piedi. C'è comunque un modo per utilizzarlo, ma se hai bisogno di chiedere, non dovresti usare it. E non sei abbastanza disperato per quello comunque.)

Sarebbe facile confrontare i riferimenti se due riferimenti distinti avevano un contenuto distinto. Quindi fallo! Aggiungi un identificatore univoco ai tuoi riferimenti. Mantieni un contatore globale, incrementalo di 1 ogni volta che crei un riferimento e memorizza il valore del contatore con i dati. Ora i tuoi riferimenti possono essere indicizzati dal loro valore contatore.

Per una migliore sicurezza del tipo e una migliore efficienza, definire una struttura dati contenente un valore del contatore e 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 

È possibile inserire il codice di cui sopra in un modulo e fare il counter tipo astratto. Inoltre, è possibile definire un modulo tabella hash utilizzando l'interfaccia funzionale Hashtbl. Ecco un altro modo per definire variabili e una struttura tabella hash su di loro con una struttura più pulita, più modulare.

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 

abbiamo bisogno del modulo intermedio Variable perché il tipo variable è parametrico ei funtori struttura dei dati della libreria standard (Hashtbl.Make, Set.Make, Map.Make) sono definiti solo per i costruttori di tipo con nessun argomento. Ecco un'interfaccia che espone sia l'interfaccia polimorfica (con le funzioni associate, ma senza strutture dati) e un functor per creare un numero qualsiasi di istanze monomorfiche, con un tipo di tabella hash associata (e set e mappa).

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 

Si noti che se si prevede che il programma può generare più di 2^30 variabili durante una corsa, un int non è tagliato. Sono necessari due valori int per creare un valore 2^a 60 bit o uno Int64.t.

Si noti che se il programma è multithread, è necessario un blocco attorno al contatore per rendere l'incremento e la ricerca atomici.

Answer 2

È possibile utilizzare l'interfaccia funzionale, che consente di fornire le proprie funzioni di hash e uguaglianza. Quindi scrivi funzioni basate solo sulle parti non mutabili dei tuoi valori. In questo esempio, sono senza parti non modificabili. Quindi, non è particolarmente chiaro quello che ti aspetti di trovare sul tavolo. Ma in un esempio più realistico (nella mia esperienza) ci sono parti non mutabili che puoi usare.

Se non ci sono parti non modificabili, è possibile aggiungerle specificatamente per l'hashing. Ad esempio, è possibile aggiungere un numero intero univoco arbitrario a ciascun valore.

È anche possibile eseguire l'hashing basato sull'uguaglianza fisica (==), che ha una definizione ragionevole per i riferimenti (e altri valori mutabili). Devi stare attento a questo, però, dato che l'uguaglianza fisica è un po 'complicata. Ad esempio, non è possibile utilizzare l'indirizzo fisico di un valore come chiave hash: un indirizzo può cambiare in qualsiasi momento a causa della garbage collection.