Records with recursive field type, that is sometimes optional


#1

I am trying to write type for a recursive tree as a record. So the type would look something like this -

type tt = {
  type_: string,
  value: int,
  children: list(tt)
};

But when I do this, it complains type mismatch

let jsont: tt = {
  "type_": "node",
  "value": 9,
  "children": [{
    "type_": "node",
    "value": 5,
    "children": [{
      "type_": "leaf",
      "value": 3
    }, {
      "type_": "leaf",
      "value": 2
    }]
  }]
};

The type error reads

 This has type:
    {. "children": list({. "children": list({. "type_": string, "value": int}),
                          "type_": string, "value": int}),
      "type_": string, "value": int}
  But somewhere wanted:
    tt

How do I write children to be optional?


#2

Hello, actually here the error comes from mixing two different types: tt which is a record type, and the literal value {"type_": "node", ...} which is a JavaScript object type. First you have to decide which one you want. If it’s a record type, then the type definition is as above and the values would look like:

let jsont = {
  type_: "node",
  value: 9,
  children: [],
};

If it’s a JavaScript object type, then the value would look like:

let jsont = {
  "type_": "node",
  "value": 9,
  "children": [],
};

In either case the field must be present, but you can show that it’s the ‘leaf’ node by giving it an empty list of children.


#3

Thank you! That makes sense.

But how do I specify an optional field of a list in a record? When I do this -

type tt = {
  type_: string,
  value: int,
  children: option(list(tt))
};

The type system, now complains –

The constructor :: does not belong to type option.

How do I write an optional field of list of things?


#4

You can specify that like:

let jsont = {
  type_: "node",
  value: 9,
  children: Some([]), // or children: None
};

But you don’t actually need it to be an option(list(tt)), because list(tt) by itself already can be empty. So something being optional and possibly empty, is redundant.