Дерево F#: вставка узла

Это вопрос, который расширяет проверку рекурсивного дерева F#, на который я вчера хорошо ответил.

Этот вопрос касается вставки дочернего элемента в существующее дерево. Это обновленный тип, который я хотел бы использовать:

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

Теперь я хотел бы иметь возможность вставить человека Simon в качестве дочернего элемента определенного человека Hans в следующей форме

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

Таким образом, входными данными должны быть имя родителя, ребенка и генеалогическое древо. В идеале он должен возвращать измененное генеалогическое древо, то есть параметр FamilyTree.

То, с чем я борюсь, - это включить функцию проверки, чтобы убедиться, что она законна, и способ правильно вставить ее в список дочерних элементов, если вставка Person уже является родителем - возможно, как отдельная функция.

Любая помощь приветствуется и очень ценится - спасибо! :)


f# insert tree treenode
person Simon Emil    schedule 27.11.2014    source источник
comment
Я предполагаю, что если имя совпадает, а возраст недействителен, он должен вернуть None, но что, если имя не соответствует ни одному из имен в генеалогическом древе? Должен ли он возвращать неизмененное дерево? Вы думали об этих двух разных случаях? А что, если совпало более одного имени?   -  person Gus    schedule 27.11.2014
comment
Прежде всего; большое спасибо за ваше время! Возвращаемое значение должно быть None в случае, если вставка невозможна. То есть, если возраст не совпадает или вы не можете найти имя. Пока скажем просто, что дубликатов имен не будет :p   -  person Simon Emil    schedule 27.11.2014

Ответы (1)


arrow_upward
3
arrow_downward

После вашего комментария вот код, который будет вести себя так, как ожидалось:

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)

Как и в моем предыдущем ответе, я продолжаю избегать использования функций списка, поскольку я не думаю, что они хорошо вписываются в древовидную структуру, если только дерево не обеспечивает обход.

Я могу быть немного пуристом в том смысле, что использую либо функции списка (с лямбда-выражениями и комбинаторами), либо чистую рекурсию, но в целом мне не нравится их смешивать.

person Gus    schedule 27.11.2014
comment
Это потрясающе, Густаво! Спасибо - person Simon Emil; 27.11.2014
comment
Кажется, он вставляет newPerson как последнего человека в дереве, не так ли? - person Simon Emil; 28.11.2014
comment
@SimonEmil Я понимаю, что вы имеете в виду, да, в старшей дочерней ветке была ошибка. Теперь должно быть хорошо. - person Gus; 28.11.2014