Добавление узла в дерево в SML

Question

Мне посоветовали задать этот вопрос как отдельный вопрос, чтобы я это сделал.

У меня есть дерево людей, как в генеалогии. Он начинается с человека и уходит в родителей, дедушек и бабушек и т. Д. Я хочу, чтобы вы могли вставить человека в пятно на дереве (в основном заменяя того, кто там).

Эти типы данных имеют важное значение:

datatype year = Year of int | UnkYear | Irrelevant 
datatype name = Name of string | UnkName 
datatype sex  = Man | Woman | UnkSex 
datatype person = Person of name * sex * year * year 
datatype parents = Dad | Mom 
datatype tree = Unspec | Info of person * tree * tree 

Назначение выглядит следующим образом: Объявить функцию вставки: дерево * список родителей * человек -> дерево, так что вызов вставки (т, поз, р) вставьте человека p в позицию pos в дереве i - при условии, что позиция существует в дереве. Если это не так, он должен вернуть t.

Так что мне нужно иметь возможность взять человека на моем дереве (допустим, мама) и заменить ее Люси (Мама и Люси - оба предварительно объявленные значения, используя лицо типа данных).

До сих пор у меня есть это:

fun insert (Info(n,mf,ft) , Mom::xs , p) = Info(p, mf, insert(ft,xs,p)) 
    | insert (Info(n,mf,ft) , Dad::xs , p) = Info(p, insert(mf,xs,p), ft) 
    | insert (Info(n,mf,ft) , [] , p)  = Unspec 

Все есть, кажется, делает это удалить тот, кто находится в пос Т- и заменить корень с р - не совсем то, что я хочу, чтобы это сделать: S Кроме того, соответствие шаблону не завершено.

Любые идеи, чтобы заставить меня двигаться сюда?

Answer 1

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

Так что вам нужно сделать, это:

В случае, когда родители-список еще не пуст, не заменяют человеку n с p - просто пройти в соответствующее поддерево.

В случае, когда список родителей пуст, и вы сейчас находитесь в Info-узле, замените человека в этом узле на p.

В случае, когда список родителей пуст, и вы находитесь на узле Unspec, замените Unspec новым информационным узлом, содержащим p и двумя пустыми поддеревьями (то есть Unspec s).

В случае, если вы достигли узла Unspec, хотя список родителей еще не пуст, просто верните Unspec, сохранив дерево без изменений в соответствии с назначением.