Insert Tree in F#

Question

Can this be improved, or made more concise?

type Government = {
    Id : Id;
    Name : string;
    Abbreviation : string;
    ParentId : string option;
}

let govList =
    [
        {Id = "1"; Name = "United States"; Abbreviation = "USA"; ParentId = None}
        {Id = "2"; Name = "California"; Abbreviation = "CA"; ParentId = Some("1")}
        {Id = "3"; Name = "Texas"; Abbreviation = "TX"; ParentId = Some("1")}
        {Id = "4"; Name = "Houston"; Abbreviation = "HOU"; ParentId = Some("3")}
        {Id = "5"; Name = "Dallas"; Abbreviation = "DAL"; ParentId = Some("3")}
        {Id = "6"; Name = "San Antonio"; Abbreviation = "SANAN"; ParentId = Some("3")}
        {Id = "7"; Name = "El Paso"; Abbreviation = "ELP"; ParentId = Some("3")}
        {Id = "8"; Name = "Canada"; Abbreviation = "CAN"; ParentId = None}
        {Id = "9"; Name = "France"; Abbreviation = "FRN"; ParentId = None}
    ]


type GovernmentStructure<'gov> = 
| Root of Government : 'gov * SubGov : GovernmentStructure<'gov> list
| Node of Government : 'gov * SubGov : GovernmentStructure<'gov> list
| Leaf of Government : 'gov


let insertGovernment (posGov: Government) (newGov : Government)
    (currentStructure : GovernmentStructure<Government>) =

    let updateStructure (govPos : Government) (newGov : Government)
        (currentStructure : GovernmentStructure<Government>) =

        // iterate over the nodes to find position and insert. parentId is useless, will fix later. 
        let rec findPosAndInsertInto parentId (startStructure : GovernmentStructure<Government>) =
            match startStructure with
            | Node (g, sg) when g = govPos ->
                Node(g, [
                            yield Node(newGov, [])
                            yield! sg
                        ])
            | Node (g, sg) ->
                Node (g, [
                            for x in sg do
                                yield findPosAndInsertInto g.Id x
                    ])
            | Leaf(g) when g = govPos -> 
                Node (g, [Leaf(newGov)])
            // better logic needed, should not hit this
            | node -> node

        match currentStructure with
        // Insert if position is at root
        | Root(gov', subGov) when gov' = govPos ->

            Root(gov', [    
                            yield Node(newGov, [])
                            yield! subGov
                       ]) 
        // Insert if position if at node or leaf
        | node -> 
            match node with
            | Root (gov', subGov) ->
                Root(gov', [
                            for x in subGov do
                                yield findPosAndInsertInto gov'.Id x 
                        ])
            // better logic needed, shouldn't hit this level
            | node -> node

    updateStructure posGov newGov currentStructure

Answer 1

The record type could be simplified by using the abbreviations themselves as the identifiers; ISO 3166 provides standard codes for at least countries & immediate subordinates (although there are collisions - Western Australia & Washington State are both 'WA' - so you might want to qualify them by their parent, e.g., USA:WA v. AUS:WA).