I think the solution you came up with is totally reasonable. In general, getting two objects to point at each other in Reason/OCaml is tough, and mutability is often appropriate. However, I’ll put a few alternative solutions below.
For all the alternatives below, I’m going to assume you’ve already defined the following:
module Input = {
type tree =
| Leaf(int)
| Node(int, list(tree));
};
Alternative 1
If, for example, you don’t like the fact that children is mutable (maybe you want to expose this type in your .rei and don’t want to allow users to mutate the children), that’s solvable with something very close to what you have. Just do two passes over the tree and fill in the parents on the second pass. Note, parent is still mutable, so we haven’t changed anything that much.
type tree = {
value: int,
mutable parent: option(tree),
children: list(tree),
};
let rec firstPassNoParents = input : tree =>
switch (input) {
| Input.Leaf(v) => {value: v, parent: None, children: []}
| Node(v, c) =>
let children = List.map(firstPassNoParents, c);
{value: v, parent: None, children};
};
let fillParents = tree => {
let rec fillParents = (parent, tree) => {
tree.parent = parent;
List.iter(fillParents(Some(tree)), tree.children);
};
fillParents(None, tree);
};
let create: Input.tree => tree =
input => {
let tree = firstPassNoParents(input);
fillParents(tree);
tree;
};
Alternative 2 (doesn’t actually work)
This is what I was hoping would work, but Reason/OCaml isn’t having any of it. Note the use of let rec node = ... and cs = ...;. You can define certain values in a mutually recursive way, but apparently not these values. The compiler error is:
This kind of expression is not allowed as right-hand side of `let rec’
I don’t claim to understand this too well, but the manual talks about what values are and aren’t allowed here (http://caml.inria.fr/pub/docs/manual-ocaml/extn.html#s%3Aletrecvalues). If you’re fluent in context-free grammars, go at it.
(again, the following does not work)
type tree =
| Leaf(int, option(tree))
| Node(int, option(tree), list(tree));
let create: Input.tree => tree =
input => {
let rec loop = (input, parent) =>
switch (input) {
| Input.Leaf(v) => Leaf(v, parent)
| Node(v, children) =>
let rec node = Node(v, parent, cs)
and cs = List.map(input => loop(input, Some(node)), children);
node;
};
loop(input, None);
};
Alternative 3
So here’s a working version of the above code, but using Lazy.t which is basically a deferred computation stored in a ref. I’m not sure it’s different enough from Alternative #1 to post, but it has the slight benefit that it’s clear that the parent is only going to be computed once and it wouldn’t be settable by users of the api. It’s probably a bit too complicated, but if you care a lot about your exposed interface (.rei) then it might have the best properties.
type tree =
| Leaf(int, Lazy.t(option(tree)))
| Node(int, Lazy.t(option(tree)), list(tree));
let create: Input.tree => tree =
input => {
let rec loop = (input, parent) =>
switch (input) {
| Input.Leaf(v) => Leaf(v, parent)
| Node(v, children) =>
let rec node = lazy (Some(Node(v, parent, Lazy.force(cs))))
and cs = lazy (List.map(input => loop(input, node), children));
get_exn(Lazy.force(node));
};
loop(input, Lazy.from_val(None));
};
