Ocaml中的可变变量的哈希表 [英] Hashtable of mutable variable in Ocaml

问题描述

我需要在Ocaml中使用可变变量的哈希表，但无法解决.

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?

推荐答案

可能碰巧具有相同内容的可变变量仍然可以区分，因为它们存储在内存中的不同位置.可以将它们与物理相等运算符(==)比较.但是，OCaml不能提供比相等更好的任何东西，它不提供对引用的非平凡哈希函数或顺序，因此，您可以构建用于存储引用的唯一数据结构是某种形式的关联列表，并带有$ \ Theta( n)$大部分使用时间.

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.)

如果两个不同的引用具有不同的内容，则比较引用将很容易.那就这样吧！向您的引用添加唯一标识符.保留一个全局计数器，每次创建引用时将其递增1，并将计数器值与数据一起存储.现在，您的引用可以通过它们的计数器值进行索引.

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

您可以将上面的代码放入模块中，并使counter类型抽象.另外，您可以使用Hashtbl函数接口定义哈希表模块.这是使用更干净，更模块化的结构来定义变量和哈希表结构的另一种方法.

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

我们需要中间模块Variable，因为类型variable是参数化的，并且标准库数据结构函子(Hashtbl.Make，Set.Make，Map.Make)仅为不带参数的类型构造函数定义.这是一个接口，它同时公开了多态接口(具有关联的函数，但没有数据结构)和一个函子，用于构建具有关联的哈希表(以及集合和映射)类型的任意数量的单态实例.

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

请注意，如果您希望程序在运行期间可能会生成2 ^ 30个以上的变量，则int不会将其剪切.您需要两个int值来构成2 ^ 60位值或Int64.t.

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.

这篇关于Ocaml中的可变变量的哈希表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！