向树中删除和添加节点

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

首先，我需要能够从这个位置删除某人以及它“下面”的所有内容 - 因此删除“妈妈”将删除妈妈和她的父母、祖父母等。如果调用的位置中没有人，则该函数应该归还树。它应该是这样的： 删除：树*父母列表->树和调用是remove(t, pos)

这就是我所拥有的，但它不太正确。有人告诉我可以用 4 行来完成。

fun replace (Info(n,mf,ft) , Mom::[]) = Info(n,replace(mf,[]),Unspec)
  | replace (Info(n,mf,ft) , Dad::[]) = Info(n,Unspec,replace(ft,[]))
  | replace (Info(n,mf,ft) , [])      = Info(n,mf,ft)
  | replace (Info(n,mf,ft) , Mom::xs) = Info(n,replace(mf,[]),replace(ft,xs))
  | replace (Info(n,mf,ft) , Dad::xs) = Info(n,replace(mf,xs),replace(ft,[]))
  | replace (Unspec , x::xs)          = Unspec
  | replace (Unspec , [])             = Unspec;

我有一个想法：

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

但这不正确。我该怎么办？

我还应该能够将一个人 p, 插入树 t 的位置 pos - 如果该位置不存在，它应该只返回树。 插入：树 * 父母列表 * 人 ->树

我只是无法理解这个问题，我希望有人能够帮助我。我希望我已经说得足够清楚了（我知道它很长）。

Answer 1

（重新发布显然我之前的答案没有在数据库崩溃中幸存下来）。

您将使用列表的头部来决定是分支到母亲子树还是父亲子树。这是正确的。然后，您可以使用列表的尾部作为路径的其余部分。这也是正确的。然而，当列表为空时（即您已到达目的地），您将执行以下操作：

| remove (Info(n,mf,ft) , [])      = Info(n,mf,ft)

换句话说：什么也没有。如果您将其更改为：

| remove (Info(n,mf,ft) , [])      = Unspec

它将按预期工作，用 Unspec 替换路径引导您到达的树的节点。