CODEWITHSUNDEEP
f#
David Faivre
David Faivre

Reputation: 2342

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?

Upvotes: 6

Views: 280

Answers (2)

MrD at KookerellaLtd
MrD at KookerellaLtd

Reputation: 2795

The pure functional idiomatic way to generate a tree is to use a Tree<'a> with no reference to the parent....a tree...is a tree, the "parent" property is derived from being a child of an existing node.

You then use a Zipper to navigate through the tree from parent to child and child to parent...rather like a "cursor" in a list of items.

see http://tomasp.net/blog/tree-zipper-query.aspx/

You can, if you want create your own tree, with distinct root and non root types, where only non roots are allowed to be added to existing nodes. You would then probably have to roll your own zipper as well, so the cost is high.

Upvotes: 0

Aaron M. Eshbach
Aaron M. Eshbach

Reputation: 6510

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)

Upvotes: 6

Related Questions