6

我需要在 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

有没有办法让它工作？

4

2 回答 2

8

您可以使用函数接口，它可以让您提供自己的哈希和相等函数。然后，您编写仅基于值的非可变部分的函数。在这个例子中，没有不可变的部分。因此，您希望在表格中找到什么并不是特别清楚。但是在一个更现实的例子中（根据我的经验），您可以使用一些不可变的部分。

如果没有任何不可变的部分，您可以专门添加它们以用于散列。例如，您可以为每个值添加任意唯一整数。

也可以基于物理相等（==）进行散列，它对引用（和其他可变值）有合理的定义。但是，您必须小心，因为身体上的平等有点棘手。例如，您不能将值的物理地址用作散列键——地址可能会因垃圾收集而随时更改。

于 2012-04-23T15:22:52.903 回答
5

可能恰好具有相同内容的可变变量仍然可以区分，因为它们存储在内存中的不同位置。它们可以与物理相等运算符 ( ==) 进行比较。然而，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类型抽象。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，因为类型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.

请注意，如果您的程序是多线程的，则需要在计数器周围加一个锁，以使增量和查找原子化。

于 2012-04-24T00:24:49.757 回答