Ocamlで可変変数のハッシュテーブル

Question

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）ほとんどの使用のための$アクセス時間。

（汚れている場合は実際に下にあるポインタに移動できますが、ポインタは足の下で動くことがありますが、それでもなおそれを利用する方法がありますが、質問する必要がある場合は、とにかくそんなに欲求不満ではありません）。

2つの異なる参照が別個の内容を持っていれば、参照を比較するのは簡単です。だからそれを作る！あなたの参照に一意の識別子を追加してください。グローバルカウンタを保持し、参照を作成するたびに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タイプの要約を行うことができます。また、ファンクションインタフェースHashtblを使用してハッシュテーブルモジュールを定義することもできます。よりクリーンでモジュラーな構造で変数とハッシュテーブル構造を定義する別の方法があります。

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パラメトリックと標準ライブラリデータ構造ファンクタ（Hashtbl.Make、Set.Make、Map.Makeが）のみなし引数で型コンストラクタのために定義されているので、我々は中間モジュールVariableを必要とします。ここでは、ポリモフィックインターフェイス（関連する関数はあるがデータ構造はない）と、関連するハッシュテーブル（およびセットとマップ）タイプを持つ任意の数の単相性のインスタンスを作成するファンクタを公開するインターフェイスを示します。あなたはあなたのプログラムが実行中に以上2^30変数を生成することが予想される場合には、intはそれをカットしないこと

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^60ビットの値を作成するには、2つのint値、またはInt64.tが必要です。

プログラムがマルチスレッドの場合、インクリメントと参照をアトミックにするには、カウンタの周りにロックが必要であることに注意してください。

Answer 2

独自のハッシュ関数と等価関数を提供できるように、ファンクションインタフェースを使用できます。次に、値の変更不可能な部分にのみ基づいている関数を記述します。この例では、はです。変更不可能な部分はありません。それで、あなたがテーブルで見つけたいと思っているものは特にはっきりしません。しかし、もっと現実的な例（私の経験では）では、あなたが使うことができる変更不可能な部分があります。

変更できない部分がない場合は、ハッシュに使用するために特別に追加することができます。たとえば、各値に任意の一意の整数を追加することができます。

物理的な等価性（==）に基づいてハッシュを行うこともできます。これは、参照（および他の変更可能な値）について妥当な定義を持っています。あなたはそれに注意する必要がありますが、肉体的平等はややこしいので注意してください。たとえば、値の物理アドレスをハッシュキーとして使用することはできません。アドレスはガベージコレクションのためにいつでも変更できます。