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

Question

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 this??? *)
}

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.

Answer 1

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.

Answer 2

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

Answer 3

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.