insert - F# 树 : Node Insertion

Question

这是一个扩展 F# Recursive Tree Validation 的问题，我昨天已经很好地回答了。

这个问题涉及在现有树中插入一个 child 。这是我想使用的更新类型:

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

我的最后一个问题是关于检查树的有效性，这是我决定采用的解决方案:

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

现在我希望能够以以下形式插入一个人西蒙作为特定人汉斯的 child

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

所以，输入应该是 parent 姓名， child 和家谱。理想情况下，它应该返回修改后的家谱，即 FamilyTree 选项

我正在努力的是合并验证功能以确保它是合法的，以及一种将它正确插入到 child 列表中的方法，如果插入人已经是 parent - 也许作为一个单独的功能。

欢迎所有帮助并非常感谢 - 谢谢! :)

Answer 1

在您发表评论之后，这里的代码将按预期运行:

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)

正如我之前的回答一样，我一直避免使用 List 函数，因为除非树提供遍历，否则我认为它们不太适合树结构。

在我使用 List 函数(带有 lambda 和组合器)或纯递归的意义上，我可能有点纯粹，但总的来说，我不喜欢混合使用它们。