Checking F # recursive tree
This is a somewhat beginner question. I am trying to test the following FamilyTree type. I cannot find an easy way to do this. All help would be appreciated.
type BirthYear = int;;
type Tree = Person of BirthYear * Children
and Children = Tree list;;
I want to test the given family tree in such a way that every person is older than their children, and also check if the list of children is sorted in order of their age (first, first). Preferably done with a function that returns a boolean value. Something like that:
let rec validate (Person(x,child)) =
let vali = child |> List.forall (fun (y,_) -> y < x)
source to share
I would do something like this:
let rec checkAges minBirth = function
| Person(b, _) :: t -> b >= minBirth && checkAges b t
| [] -> true
let rec validate (Person(b, c)) =
List.forall validate c && checkAges (b + minParentAge) c
where minParentAge
there is a minimum age to have children.
I would expect to checkAges
be the harder part here: the function checks if the first child it sees is younger than the limit it sets, then recursively checks the next child, with the child's current age as the new limit.
Pay attention to some methods:
-
A function that checks the ages of children takes the minimum birthday as input; this is used to check that the parent is old enough for the first child to be sane.
-
List.forall
checks the predicate for all elements in the list and early outs if the predicate fails -
function
is shorthand for creating a function that matches a template by its parameter. Hence, itcheckAges
has two arguments.
source to share
Here's a very simple solution using one recursive function. It doesn't rely on built-in functions like List.forall
, but I think it's very declarative and (hopefully) easy to follow.
- Rule 1: Everyone is older than their children.
- Rule 2: The list of children is sorted in order of their age (first first)
code:
let rec isValid = function
| Person ( _ , []) -> true // Person alone without childs -> always valid
| Person (minYear, Person (year, childs) :: brothers) ->
year > minYear && // Validate Rules (either 1 or 2)
isValid (Person (year, childs)) && // Enforce Rule 1
isValid (Person (year, brothers)) // Enforce Rule 2
I personally don't feel like List.forall
it fits well here, it helps to solve part of the problem, but not the whole, so you have to combine it with other things (see other answers) and in the end you cannot escape the recursive function.
List functions are fine for lists, but for trees, I feel like recursion is more natural, unless your tree provides a way to traverse it.
source to share
Here's a way to do it. It may be helpful to spend some time analyzing how this will work.
let rec check (Person(age, children)) =
match children with
| [] -> true
| Person(eldest, _)::_ ->
Seq.pairwise children |> Seq.forall ((<||) (>))
&& age > eldest
&& List.forall check children
source to share