Statically "extend" a record-ish data type without indirection hassle

Question

I am currently working with a three-level process for which I need some information to flow being accessed and updated. The information is also three-leveled, in such a way that a process at one level may need to access/update information at its level and at higher levels.

type info_0 = { ... fields ... }
type info_1 = { ... fields ... }
type info_2 = { ... fields ... }

fun0 will do some stuff with an info_0, then pass it to fun1 along with an info_1, then get back the resulting info_0 and proceed, calling another fun1 with another info_1. The same happens at the lower level.

---

My current representation has

type info_0 = { ... fields ... }
type info_1 = { i0: info_0; ... fields ... }
type info_2 = { i1: info_1; ... fields ... }

In fun2, updating info_0 get pretty messy:

let fun2 (i2: info_2): info_2 =
  {
    i2 with
      i1 = {
        i2.i1 with
          i0 = update_field0 i2.i1.i0
      }
  }

---

Something simpler would be:

type info_0 = { ... fields ... }
type info_1 = { ... fields ... }
type info_2 = { ... fields ... }
type info_01 = info_0 * info_1
type info_012 = info_0 * info_1 * info_2

let fun2 (i0, i1, i2): info_012 =
  (update_field0 i0, i1, i2)

---

Does the last solution look good?

Is there an even better solution to this kind of problem? (for instance, one where I could write a function that can handle updating a field0, no matter whether it's dealing with a info_0, info_1 or info_2)

Would OCaml modules help? (I could include a Sig0 inside Sig1 for instance...)

Nance

Answer 1

What you need is an idiomatic way of updating nested immutable data structures. I don't know any relevant work in OCaml, but there are a few techniques available in Scala/Haskell including Zippers, Tree rewriting, and Functional lenses:

Cleaner way to update nested structures

Is there a Haskell idiom for updating a nested data structure?

For F#, a descendant of OCaml, functional lenses gives a nice solution. Therefore, lenses is the most relevant approach here. You can get the idea of using it from this thread:

Updating nested immutable data structures

since F# record syntax is almost the same as that of OCaml.

EDIT:

As @Thomas mentioned in his comment, there is a complete implementation of lenses in OCaml available here. And particularly, gapiLens.mli is of our interest.

Bresnahan

Thanks, this bugsquash.blogspot.com/2011/11/lenses-in-f.html deals with exactly my issue! – Nance

Yes, it does. I hope someone will build a similar library to work in general cases in OCaml. – Bresnahan

The unsatisfying thing is, at my call site, I still have to remember where I am to call the right functions, say bookEditorCarMileage.Set or just editorCarMileage.Set or carMileage.Set... With the class approach and inheritance I can just obj#set_mileage whatever obj is. – Nance

I admit that you still have to write boilerplate codes in this approach. But I prefer staying immutable, managing mutable update of class hierarchy is a huge pain. When I use a functional language, I try to avoid mutation at all cost. – Bresnahan

if you want lenses, you can find a pretty complete implementation here – Dickinson

Answer 2

You seem to want the ability to treat a more complex value as though it was a simpler one. This is (more or less) the essence of the OO model. I usually try to avoid the OO subset of OCaml unless I really need it, but it does seem to meet your needs here. You would have a base class corresponding to info_0. The class info_1 would be a subclass of info_0, and info_2 would be a subclass of info_1. It's worth thinking about, anyway.

Vershen

Would the object model of OCaml work well with the immutable nature of the current code ? If mutability is not a problem, records can also be modified in place... – Limner

This is a good point. I was thinking about the subtyping more than about mutability. Something else to think about, for sure. – Vershen

That looks like a decent solution: I lose record access syntax, but at the benefits of inheritance (I can define a getter/setter in class info_0, and inherit it in info_1). However, I forgot to mention that I needed immutable updates, as I sometimes need to do non-deterministic processes and then backtrack (keep only one of these), and I don't want to deal with this myself... So as @FabriceLeFessant mentioned, this won't really solve my problem. – Nance

@Nance OCaml objects can be immutable just like records can be. What may be a problem is that in Jeffrey's model, the objects would replicate the information instead of pointing to each other, so your data may end up using significantly more memory. – Vouch

@Gilles I need functional updates, with sharing, is that even possible? – Nance

Answer 3

As Jeffrey Scofield suggested, You can save the hassle at use and update time by using classes: make info_1 a derived class, and a subtype, of info_0, and so on.

class info_1 = object
  inherit info_0
  val a_1_1 : int
  …
  method update_a_1_1 v = {<a_1_1 = v>}
end
…
let x : info_1 = new info_1 … in
let y = x#update_a_1_1 42 in
…

The downside of this direct object approach is that all the data in an object is copied if you update any of the fields; you can't share the info_0 pieces between x and y.

You can use objects and retain the sharing behavior from your design with records, but the boilerplate at definition time and the constant run-time overhead become larger.

class info_1 = object
  val zero : info_0
  method get_a_0_1 = zero#get_a_0_1
  method update_a_0_1 = {<zero = zero#update_a_0_1>}
  val a_1_1 : int
  method get_a_1_1 = a_1_1
  method update_a_1_1 v = {<a_1_1 = v>}
end
let x : info_1 = new info_1 … in
let y = x#update_a_1_1 42 in
…

Valentia