代码之家 › 专栏 › 技术社区 › P Shved

在ocaml中,如何使用支持就地修改的字段以功能方式更新记录?

ocaml structure functional-programming

P Shved · 技术社区 · 14 年前

假设我有 Hashtbl 领域:

type rec = {
  table : (int, int) Hashtbl.t;
  value : int;
  (* more fields... *)
}

我应该如何以功能性的方式更新它,例如:

let new_rec = { old_rec with
  value = old_rec.value + 1 ;                 (* that's ok *)
  table = hash_table + (key -> value binding) (* but how should I do this??? *)
}

我很想听听一般的方法,这不是 哈什特尔 . 显然,我必须复制这样的结构,然后修改副本。但我遇到的困难是如何使生成的代码尽可能“实用”。

3 回复 | 直到 14 年前

Norman Ramsey 14 年前

我很想听听一般的方法,这不是hashtbl特有的

你要解决的一般问题是 采用可变数据结构,并将其视为不可变的 . 当你创建一个新的记录时,这种情况就出现了,这是一个危险的事实。(尽管我会指出,因为你正在创建一个 每一个 场是不同的, old_rec with 是多余的和令人分心的。)

将可变数据结构视为不可变数据结构的一般解决方案是 复制,然后变异 . 但这个解决方案充满了危险:

下面不清楚 确切地 什么样的情况下,一个浅显的副本足够好,或者当你可能不得不写一个深刻的副本。
如果抽象是可变的,就不能保证它是可变的提供复制操作(或适当的复制操作)。
拷贝可能很贵,尤其是深度拷贝。

这种考虑是导致人们首先避免可变状态的原因。我意识到在caml中很难做到这一点,因为标准库对于函数式语言来说是非常必要的。不过,我相信从长远来看,正确的“总”战略是 用纯函数数据结构替换可变抽象 .

附录:下面是哈希表的示例:

let extend key val tbl =
  let h = Hashtbl.copy tbl in
  let _ = Hashtbl.replace tbl key val in
  h

提供 Hashtbl.copy 足够深,可以将其用作扩展哈希表的函数方法。但你最好还是种上红黑相间的树。

nlucaroni 14 年前

为了使它的使用尽可能的实用,你可以这样做,

let functional_insert tbl k v =
    let x = Hashtbl.copy tbl in
    let () =  Hashtbl.replace x k v
    x

当然,如果您经常这样做,那么最好使用功能性数据结构——ocaml中的映射。这也是一般的方法,如果数据结构是可变的,则必须复制它才能以函数方式使用。hashtbl实现是一个链表数组,仅供参考(如果需要替换结构的话,可以进行权衡);

type ('a, 'b) t =
  { mutable size: int;                        (* number of elements *)
    mutable data: ('a, 'b) bucketlist array } (* the buckets *)

and ('a, 'b) bucketlist =
    Empty
  | Cons of 'a * 'b * ('a, 'b) bucketlist

Dario 14 年前

hashtbl不是功能性数据结构,而是基于更改的。你必须 copy 然后修改它。

只是从网上看 documentation 我猜。

val replace : ('a, 'b) t -> 'a -> 'b -> unit

替换tbl x y用x到y的绑定替换tbl中x的当前绑定。如果x在tbl中未绑定,则将x到y的绑定添加到tbl。这在功能上等同于hashtbl.remove tbl x后跟hashtbl.add tbl x y。