CODEWITHSUNDEEP
inserttreef#treenode
Simon Emil
Simon Emil

Reputation: 85

F# Tree: Node Insertion

This is a question that extends F# Recursive Tree Validation, which I had nicely answered yesterday.

This question concerns inserting a child in an existing tree. This is the updated type I'd like to use:

type Name           = string
type BirthYear      = int
type FamilyTree     = Person of Name * BirthYear * Children
and Children        = FamilyTree list

My last question concerned checking the validity of the tree, this was the solution I decided to go with:

let rec checkAges minBirth = function
    | Person(_,b,_) :: t -> b >= minBirth && checkAges b t
    | [] -> true

let rec validate (Person(_,b,c)) =
    List.forall isWF c && checkAges (b + 16) c

Now I would like to be able to insert a Person Simon as a child of specific Person Hans in the following form

insertChildOf "Hans" simon:Person casperFamily:FamilyTree;;

So, input should be parent name, child and the family tree. Ideally it should then return a modified family tree, that is FamilyTree option

What I am struggling with is to incorporating the validate function to make sure it is legal, and a way to insert it properly in the list of children, if the insertion Person is already a parent - maybe as a seperate function.

All help is welcome and very appreciated - thanks! :)

Upvotes: 4

Views: 421

Answers (1)

Gus
Gus

Reputation: 26174

After your comment here's a code that will behave as expected:

let insert pntName (Person(_, newPrsnYear, _) as newPrsn) (Person (n,y,ch)) =
    let rec ins n y = function
        | [] -> if y < newPrsnYear && n = pntName then Some [newPrsn] else None
        | (Person (name, year, childs) as person) :: bros ->
            let tryNxtBros() = Option.map (fun x -> person::x) (ins n y bros)
            if y < newPrsnYear && n = pntName then // father OK
                if newPrsnYear < year then // brother OK -> insert here
                    Some (newPrsn::person::bros)
                else tryNxtBros()
            else // keep looking, first into eldest child ...
                match ins name year childs with
                | Some i -> Some (Person (name, year, i) :: bros)
                | _      -> tryNxtBros() // ... then into other childs
    Option.map (fun x -> Person (n, y, x)) (ins n y ch)

As in my previous answer I keep avoiding using List functions since I don't think they are a good fit in a tree structure unless the tree provides a traverse.

I might be a bit purist in the sense I use either List functions (with lambdas and combinators) or pure recursion, but in general I don't like mixing them.

Upvotes: 3

Related Questions