I'm learning F# and I'm trying to solve this exercise but my solution feels really... heavy and I suspect that there might an easier way of solving this task.

The task goes like that:

Declare two mutually recursive functions:

insertChildOf: Name -> FamilyTree -> FamilyTree -> FamilyTree option 
insertChildOfInList: Name -> FamilyTree -> Children -> Children option 

The value of insertChildOf n c t = Some t when t is the family tree obtained from t by insertion of c as a child of the person with name n. The value is None if such an insertion is not possible. Similarly, the value of insertChildOfInList n c cs = Some cs when cs is the list of children obtained from cs by inserting c as a child of a person named n in one of the children in cs. The value is None if such an insertion is not possible. Note that the person named n may occur anywhere in the family tree.

The type for the tree:

type Name = string;;
type Sex = 
    | M // male
    | F // female
type YearOfBirth = int;;
type FamilyTree = P of Name * Sex * YearOfBirth * Children
and Children = FamilyTree list;;

You can assume that the tree has the following proprieties.

1. All children are younger than their parent.
2. The children are arranged form the oldest to the youngest.

Make sure that the tree you return also has those parameters.

My code:

let rec insertChildOf n c t = 
    let (P (_, _, yobi, _)) = c
    match t with
    | (P (name, sex, yob, children)) when  n = name && yob < yobi -> 
        match insertHere c children -infinity  with
        | Some a -> Some ( P (name, sex, yob, a ))
        | None -> None 
    | (P (name, _, yob, children)) when  n = name && yob > yobi -> None
    | (P (n, s, y, children)) -> 
        match insertChildOfInList n c children with
        | Some a -> Some ( P (n, s, y, a ))
        | None -> None 
and  insertChildOfInList n c cs   = 
    match cs with
    | h::t -> 
        match insertChildOf n c h with
        | Some h2 -> 
            match insertChildOfInList n c t with
            | Some a -> Some (h2::a)
            | None -> None
        | None -> None
    | [] -> Some []
and insertHere  t cs acc =
    match cs with
    | [] -> Some [t]
    | h::tail -> 
        let (P (_, _, yob, _)) = t
        let (P (_, _, yob2, _)) = h
        if acc < yob && yob < yob2 then Some (t::h::tail) 
        else if yob = yob2 then None
        else // h::(insertHere t tail (float yob2))
            match insertHere t tail (float yob2) with
            | Some a -> Some (h::a )
            | None -> None

Once again, my question is: Can I do it in any simpler way?

Also, is there any way to return None if we didn't find FamilyTree with the right name? The one way I can think of is making all the functions return one more extra value called (found) which would signal if the node with the correct name was found, and creating a wrapper that would check the value of that variable and return None if the found was false.

CodePudding user response：

To be honest, it isnt really any shorter than yours. I've not used any 'fancy' library methods (e.g. things like sortby, or Option.map as you havent either) I can't guarentee that its completely correct I've written it as explicit lambda functions to make the types explicit - this isnt normal. I didnt use the tuple syntax you need, because i find tuple syntax clumsy in this example. I've put some test cases at the end.

type Name = string
type Sex = 
    | M // male
    | F // female
type YearOfBirth = int
type FamilyTree = 
    { name: string
      sex: Sex
      yearOfBirth: YearOfBirth
      children: Children
    }
and Children = FamilyTree list


let makeFamilyTree name sex yearOfBirth children = 
    { name = name
      sex = sex
      yearOfBirth = yearOfBirth
      children = children
    }

let rec addChild : FamilyTree -> Children -> Children = 
    fun newChild children ->
        match children with
        | [] ->
            [newChild]
        | eldest :: tail when eldest.yearOfBirth < newChild.yearOfBirth ->
            newChild :: eldest :: tail
        | eldest :: tail ->
            eldest :: addChild newChild tail            

let rec insertChildOf: Name -> FamilyTree -> FamilyTree -> FamilyTree option =
    fun name childTree tree ->
        let childrenMaybe = 
            if name = tree.name && tree.yearOfBirth < childTree.yearOfBirth  then
                addChild childTree tree.children
                |> Some
            else
                insertChildOfInList name childTree tree.children
        match childrenMaybe with
        | Some children ->
            Some { tree with children = children }
        | None ->
            None
and insertChildOfInList: Name -> FamilyTree -> Children -> Children option =
    fun name childTree children ->
        match children with
        | [] -> 
            None
        | eldest :: younger ->
            match insertChildOf name childTree eldest with
            | Some eldest' ->
                Some (eldest' :: younger)
            | _ ->
                None

let jon =
    { name = "Jon"
      sex = Sex.M
      yearOfBirth = 1100
      children = []
    }

let jon2 = 
    insertChildOf 
        "Jon"
        (makeFamilyTree
            "Dave"
            Sex.M
            1120
            [])
        jon
        

let jon3 = 
    insertChildOf 
        "Dave"
        (makeFamilyTree
            "Mary"
            Sex.F
            1140
            [])
        jon2.Value
        

let jon4 = 
    insertChildOf 
        "Dave"
        (makeFamilyTree
            "Elizabeth"
            Sex.F
            1141
            [])
        jon3.Value
        

let jon5 = 
    insertChildOf 
        "Dave"
        (makeFamilyTree
            "George"
            Sex.F
            1142
            [])
        jon4.Value