F#: To Design or not design with mutually dependably record types

Question

• I try to model trees with their nodes using F# records.
• Here is an abstraction of what my design looks like:

type Tree = { Root: Node }
and Node = { Tree: Tree }

• (There are other record fields, of course.)
• The rationale is that given a tree I want to quickly access its root node; furthermore, I want to know the associated tree for any given node (including a root node).
• Initializing a tree with its root works:

let rec newTree = { Root = newRoot }
and newRoot = { Tree = newTree }

• Now, I read in this Stackoverflow post that this only works because of some accidental internal visibility on the backing fields, which also leads that any function initializing such tree/root records must reside within the same assembly as the type definitions (not too great, but I can live with that).
• This post describes using options for the mutually dependable fields, but I really want to model that each tree has a root node (no empty trees in my system) and each node has a tree, without having to test for Some/None.
• Is my design approach sound? Or should I rather model the intrinsic bound between trees and their nodes in another way?

Answer 1

there is no need to declare a type for root. from a type perspective, a tree is a node. the canonical way to define a tree in f# is like so

type Node = 
   | N of int * Node list // (inner) node
   | L of int  // leaf

let tree = N(3, [L(5); L(7)])

its your choice if you define a separate case for the leaf or simply use

type Node = N of int * Node list

int is the node data type. you will customize this or even use a generic.

i often use mutable children collections, then i use records like

type Node = { data: int; mutable children: Node list }

let root = { data=3; children=[] }
root.children <- [{ data=7; children=[] }]