How to Model a Simple Hierarchy with a Single Root

Question

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?

Answer 1

If I was building this for my own model in a Domain-Driven Design, I would probably define nodes as follows:

[<Struct>] type NodeId = private NodeId of int

module NodeId =
    let create id =
        // Replace with the proper validation rules for a Node Id
        if id < 0
        then Error "NodeId must be non-negative" // I would actually use a DU with each error case
        else Ok <| NodeId id

    let value (NodeId id) = id

type [<Struct>] RootNode = {Id: NodeId}
type [<Struct>] ChildNode = {Parent: Node; Id: NodeId}

and Node =
    | Root of RootNode
    | Node of ChildNode
    member node.Id =
        match node with
        | Root r -> r.Id
        | Node n -> n.Id
    member node.Parent =
        match node with
        | Root _ -> None
        | Node n -> Some n.Parent
    member node.IsRootNode =
        match node with
        | Root _ -> true
        | Node _ -> false
    member node.IsChildNode = 
        not node.IsRootNode

This gives us the following:

• A type for NodeId that wraps int and an accompanying module that encapsulates any business rules around what makes a valid identifier
• Specific types for RootNode and ChildNode that allow them to have only the required fields for that type of node
• A single Node type that allows us to represent RootNode and ChildNode as the same type without requiring them to have the same fields, but still providing direct access to the underlying fields and allowing us to easily distinguish between RootNodes and ChildNodes

Then, I would have a module for creating Nodes like:

module Node = 
    let createRoot = 
        NodeId.create >> Result.bind((fun id -> Root {Id = id}) >> Ok)

    let createChild parent =
        NodeId.create >> Result.bind((fun id -> Node {Id = id; Parent = parent}) >> Ok)