Hashtable изменчивой переменной в Ocaml

Question

Мне нужно использовать hashtable изменчивой переменной в Ocaml, но это не сработает.

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 

Есть ли способ заставить его работать?

Answer 1

Переменные, которые могут иметь один и тот же контент, по-прежнему можно различать, поскольку они хранятся в разных местах памяти. Их можно сравнить с оператором физического равенства (==). Однако OCaml не обеспечивает ничего лучшего, чем равенство, он не предоставляет нетривиальной хэш-функции или порядка для ссылок, поэтому единственной структурой данных, которую вы можете построить для хранения ссылок, является список ассоциаций некоторой формы с $ \ Theta (n) время доступа для большинства применений.

(Если вы играете грязно, вы можете получить основной указатель, но указатель может двигаться под ногами. Тем не менее, есть способ использовать его, но если вам нужно спросить, вы не должны использовать это не так. И вы все равно не отчаянно нуждаетесь в этом.)

Было бы легко сравнить ссылки, если две разные ссылки имели четкое содержание. Так сделайте это так! Добавьте в свои ссылки уникальный идентификатор. Храните глобальный счетчик, увеличивайте его на 1 каждый раз при создании ссылки и сохраняйте значение счетчика с данными. Теперь ваши ссылки могут быть проиндексированы по их значению счетчика.

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) 

Для обеспечения более безопасной безопасности и повышения эффективности определите структуру данных, содержащую значение счетчика и элемент.

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 

Вы можете поместить код, указанный выше в модуле и сделать counter типа реферата. Кроме того, вы можете определить хэш-таблицу с использованием функционального интерфейса . Вот еще один способ определить переменные и структуру хеш-таблицы на них с более чистой, более модульной структурой.

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 

Нам нужен промежуточный модуль Variable, так как тип variable параметрический и стандартные функторы структуры данных библиотеки (Hashtbl.Make, Set.Make, Map.Make) определены только для конструкторов типов без аргумента. Вот интерфейс, который предоставляет как полиморфный интерфейс (со связанными функциями, но без структуры данных), так и функтор для построения любого количества мономорфных экземпляров с ассоциированным типом хэш-таблицы (и набором и картой).

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 

Обратите внимание, что если вы ожидаете, что ваша программа может генерировать более 2^30 переменных во время бега, int не будет резать. Вам нужно два значения int, чтобы сделать 2^60-битное значение, или Int64.t.

Обратите внимание, что если ваша программа многопоточная, вам нужна блокировка вокруг счетчика, чтобы сделать инкремент и поиск атома.

Answer 2

Вы можете использовать функциональный интерфейс, который позволяет вам создавать собственные функции хэша и равенства. Затем вы пишете функции, которые основаны только на не изменяемых частях ваших значений. В этом примере : нет неперемещаемых частей. Таким образом, не особенно ясно, что вы ожидаете найти в таблице. Но в более реалистичном примере (по моему опыту) есть не изменяемые части, которые вы можете использовать.

Если нет неперемещаемых частей, вы можете добавить их специально для использования в хешировании. Например, вы можете добавить произвольное уникальное целое к каждому значению.

Также возможно сделать хэширование на основе физического равенства (==), которое имеет разумное определение для ссылок (и других изменяемых значений). Вы должны быть осторожны с ним, хотя физическое равенство немного сложно. Например, вы не можете использовать физический адрес значения в качестве хеш-ключа - адрес может быть изменен в любое время из-за сбора мусора.