F # Tree: Node Insert
This is a question that extends F #'s recursive tree validation , which I answered well yesterday.
This question is about inserting a child into an existing tree. This is the updated type I would like to use:
type Name = string
type BirthYear = int
type FamilyTree = Person of Name * BirthYear * Children
and Children = FamilyTree list
My last question was about tree validation, 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 Person Simon as a child of a specific Person Hans in the following form
insertChildOf "Hans" simon:Person casperFamily:FamilyTree;;
So the input must be parent name, child and family tree. Ideally it should return a modified family tree, i.e. the FamilyTree parameter
What I am struggling with is to include a validate function to make sure it is legal, and a way to insert it correctly into the list of children if the Person insert is already a parent - perhaps as a separate function.
All help is greatly appreciated and greatly appreciated - thanks! :)
source to share
Following your comment, enter some code here 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 continue to avoid using List functions as I don't think they are a good fit for a tree structure unless the tree provides traverse.
I could be a bit purist in the sense that I use list functions (with lambdas and combinators) or pure recursion, but in general I don't like mixing the two.
source to share