How to update records with fields, which support in-place modifications, in a functional way in OCaml?

Assume I have a record with a Hashtbl field:

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

How should I update it in a functional way, i.e. something like that:

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 thi开发者_StackOverflows??? *)
}

I'd love to hear about general approach, that's not specific to Hashtbl. I'll obviously have to copy such a structure, and then modify the copy. But what I'm experiencing difficulty with is how to make the resultant code as "functional" as possible.

I'd love to hear about general approach, that's not specific to Hashtbl

The general problem you are trying to solve is to take a mutable data structure and treat it as if it were immutable. The fact that this occurs as you create a new record is a red herring here. (Although I will point out that because you are creating a record in which every field is different, the old_rec with is superfluous and distracting.)

The general solution to treating a mutable data structure as if it were immutable is copy, then mutate. But this solution is fraught with peril:

• It's not clear under exactly what circumstances a shallow copy is good enough or when you might have to write a deep copy.

• If the abstraction is mutable, there's no guarantee it even offers a copy operation (or the appropriate copy operation).

• Copies can be expensive, especially deep copies.

This considerations are what lead people to avoid mutable state in the first place. I realize that this is hard to do in Caml, because the standard libraries are unusually imperative for a functional language. Nevertheless, I believe the correct "general" strategy in the long run is to replace mutable abstractions with purely functional data structures.

Addendum: Here's a example for hash tables:

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

Provided Hashtbl.copy is deep enough, you can use this as a functional way of extending a hash table. But you'd be better off with red-black trees.

To make it's usage as functional as possible, you can do something like this,

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

Of course, if you are doing this a lot, it would be better to use a functional data-structure --a Map in ocaml. This is the general approach as well, if the data-structure is mutable it must be copied to be used in a functional way. Just for reference (for weighing if you should replace the structure), the Hashtbl implementation is an array of linked lists;

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

Hashtbl is no functional datastructure, but change-based. You'll have to copy and afterwards modify it.

Just from viewing the online documentation, I'd guess.

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

Hashtbl.replace tbl x y replaces the current binding of x in tbl by a binding of x to y. If x is unbound in tbl, a binding of x to y is added to tbl. This is functionally equivalent to Hashtbl.remove tbl x followed by Hashtbl.add tbl x y.