F#递归树验证 [英] F# Recursive Tree Validation

问题描述

这是一个初学者的问题.我一直在尝试验证以下类型的FamilyTree.我找不到执行此操作的简单方法.所有帮助将不胜感激.

This is a somewhat beginner question. I have been trying to validate the following type of FamilyTree. I can't find a simple 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 validate a given family tree such that every Person is older than their Children and furthermore check if the list of Children is sorted in order of their age (eldest first). Preferably done with a function that return a boolean. Something along the lines of this:

let rec validate (Person(x,child)) = 
    let vali = child |> List.forall (fun (y,_) -> y < x)

推荐答案

我会做这样的事情:

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

其中minParentAge设置为可以生育的合理最低年龄.

where minParentAge is set to a reasonable minimum age to have children at.

我希望checkAges在这里是最困难的部分:该函数检查它看到的第一个孩子是否比给定的限制年轻，然后递归检查下一个孩子，并以当前孩子的年龄为准.新的限制.

I'd expect checkAges to be the more difficult part here: the function checks whether the first child it sees is younger than the limit it is given, then recursively checks the next child, with the current child's age as the new limit.

请注意一些技巧:

• 检查儿童年龄的功能将最小生日作为输入；这用于验证父母的年龄足以使第一个孩子变得合理.

• The function that checks child ages takes the minimum birthday as input; this is used to validate that the parent is old enough for the first child to be reasonable.

List.forall检查列表中所有项目的谓词，如果不满足谓词，则进行提前检查

List.forall checks a predicate for all items in a list, and early-outs if a predicate is not fulfilled

function是创建一个函数的简写形式，该函数对其参数进行模式匹配.因此，checkAges实际上有两个参数.

function is a shorthand to create a function that does pattern matching on its parameter. Therefore, checkAges actually has two arguments.

这篇关于F#递归树验证的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！