Type-checked way of modeling parent-child relationships?

Question

I have a type, Item. An Item may have a parent Item or one or more child Items or neither (ie, there doesn't have to be a relationship, and relationships are at most one level deep).

Transformations on Items sometimes affect the parent, and sometimes the children. So I need to be able to traverse both ways.

A naive representation is to have a ParentID: ID option and ChildIDs: ID list fields on Item. But that allows illegal states.

I could instead have a Relationships field on Item of type Relationship = ParentID of ID | ChildIDs of ID * ID list | None, which is better (the ChildIDs tuple to ensure there's at least one child in that case).

But is there a way to have the compiler ensure the consistency of the two-way relationship?

I was thinking I could do away with linkages on IDs altogether, and introduce a discriminated union at the very top: type Item = Item of Item | Compound of Item * Item * Item list. (Again, the Compound tuple represents a parent, at least one child, maybe more children.)

The downside is now every transformation on Item needs to check cases and handle Compounds. (Or maybe this is good since it forces me to think about knock-on effects of every transformation?)

The advantage is that all the Items that a function may need to touch are always available in one, consistent bundle.

Is that "idiomatic"? Any other approaches to consider?

user_227606 · Answer

Would something like this work? The Item is a record that contains the payload (ID and data attributes).

The discriminated union defines your four scenarios.

type Item = {ID: int; Name:string} //whatever is required

type ItemNode =
| StandaloneItem of Item
| ItemWithParent of Item * Item
| ItemWithChilren of Item * Item list
| ItemWithParentAndChildren of Item * Item * Item list

let processItem (item:Item) = 42

Then you could implement your processing of the nodes similar to this:

let processNode (item:ItemNode) = 
    match item with
    | StandaloneItem it -> it |> processItem 
    | ItemWithParent (parent, it) -> [parent; it] |> List.map processItem |> List.sum
    | ItemWithChilren (it, children) -> (it |> processItem) + (children |> List.map processItem |> List.sum)
    | ItemWithParentAndChildren (it, parent, children) -> (it |> processItem) 
                                                          + (parent |> processItem) 
                                                          + (children |> List.map processItem |> List.sum)

In this way you do not have to add any conditional logic (on top of match) to your processing - you deal with the tuples with known content.

You can also implement records instead of tuples, which will lead to even bigger transparency.

Type-checked way of modeling parent-child relationships?

1 Answers