Nicollet.Net

Objective Caml supports recursive types out of the box, like most programming languages. A classic example is the tree, for instance to represent an expression:

type lambda =
  | Var of int
  | App of lambda * lambda
  | Abs of lambda

The problem is that such definitions are not very useful. Sure, they define a variant composite type that can be used to represent trees, but the nodes in those trees cannot be extended in any way. For instace, if you wanted to type-check a lambda-expression using the classic ruleset, and bind a type to every sub-expression, you would have no way of doing so because you cannot attach data to an existing value in Objective Caml.

What you would end up doing is something like this:

type lambda =
  | Var of int
  | App of term * term
  | Abs of term

and term  =
  {
    term_type : your_term_type ;
    term_form : lambda
  }

That’s better (you can now bind arbitrary data to every term) but you still have to change the original definition of your term if you need new data to be added.

One way of improving things is to give every term a unique identifier (and be stuck with the issue of generating unique identifiers, which is not a trivial thing to do once you need to account for child expressions depending on parent expressions and cloning). It can work, but I would advise against it.

My personal advice is to use this:

type 'term lambda =
  | Var of int
  | App of 'term * 'term
  | Abs of 'term

(* Somewhere else *)
type term =
  {
    term_type : your_term_type ;
    term_form : term lambda
  }

The variant is defined on its own, without any recursion, so that it may be used in any number of ways with different data associated. So, one module may use the recursive definition as a standalone type for marshaling, another may use the recursive definition with some information about whether an abstraction’s variable is used anywhere for better execution speed, and a third may also add type information or code generation information.

And you can even convert between the various definitions using a map-like (non-recursive) function that translates terms from one type to another!

Conclusion: separate concerns. Being a variant is one concern, being recursive is another. So, define the variant non-recursively, then define the recursion as part of another type (along with per-node additional data, if any).