How to Model a Simple Hierarchy with a Single Root

I want to model a hierarchy in F#, where each node must have a single parent, exception, obviously, the root node, which has no parent. My naive solution

type Node = {
    Id: int // meta data for node
    Parent: Node option
}
let root = { Id = 1; Parent = None}
let child1 = { Id = 2; Parent = Some(root)}
let child2 = { Id = 3; Parent = Some(child1)}

But my entry into F# has been through @swlaschin and he’s blown my mind with creating descriptive domains. So it feels smelly to me that Parent is an option, when 99% of the time, it’s required. My best effort:

type Node = 
    | Node of NodeMeta * Node
    | Root of NodeMeta
and NodeMeta = {
    Id: int
}
let root = Root({Id = 1})
let child1 = Node({Id = 2}, root)
let child2 = Node({Id = 3}, child1)

Is there a more idiomatic way?

FYI, reposted here and got an interesting answer: https://stackoverflow.com/questions/50839160/how-to-model-a-simple-hierarchy-with-a-single-root/50842376#50842376

Thanks for posting the SO response. Maybe it’s really common in the wild, but I was really taken by the “shape” of Node's definition:

  • DU cases at the top;
  • each member is a match expression on a Node

It seems formulaic in a good way. I wonder whether that “form” has applicability for other kinds of common structures apart from hierarchies.