Ocaml Record design

Learning
1

Hi,

I have a node record structure as below:

type node_t = {
    line_number: int;
    parent: node_t;
    children: node_t list;
}

Now, node may or may not have children. So, I do not want to store children field in memory for those nodes who does not have any children.

Is there any possibility to design such record structure?

Thank you in advance.

3

I don’t think you can do it with just a record; but you could use a sum type to differentiate between the two cases:

type node_t =
  | Inner of {line_number: int; parent: node_t; children: node_t list}
  | Leaf of {line_number: int; parent: node_t}

(the memory layout of the Inner case is identical to your record type, for the Leaf case, the memory representation contains only two fields.)

Best wishes,
Nicolás

2 Likes
4

But then you have to store the tag for the sum type in memory no ?

How about:

type node_t = {
    line_number: int;
    parent_and_children: node_t list;
}
let parent node = List.hd node.parent_and_children
let children node = List.tl node.parent_and_children

I’d also recommend to make the type private and provide a constructor that forces you to respect the invariant that parent_and_children is not empty.

5

Records, like any other boxed value, also carry a tag (zero).

Best wishes,
Nicolás

1 Like
6

Oh I see, you are exploiting the fact that the record is actually inline in type t = A of { … } (but I’m guessing it’s not inlined for type tt = { … } type t = A of tt).

Yeah, my bad, your answer is cleaner.

7

Indeed, if the record payload to the constructor(s) was not inline there would be an extra indirection in the runtime representation.

Best wishes,
Nicolás

1 Like
8

Thank you Nicolás for this suggestion.
It worked for me :slight_smile: