Removing and adding nodes to a tree

Question

I have an assignment, and I can't figure out what to do about it. I have a tree of people with their name, birth and death year. Think genealogy here. I have a bunch of datatypes to take care of ages, names, the tree itself, etc. and then I have a bunch of people and a tree.

The datatypes are:

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

First I need to be able to remove someone from this position and everything "under" it - so removing "Mom" will remove mom and her parents, grandparents, etc. If there's no person in the position called, the function should return the tree. It's supposed to be like this: remove : Tree * parents list -> Tree and the call is remove(t, pos)

This is what I have, but it's not quite right. I've been told that I can do it in 4 lines.

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;

An idea I have:

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;

But it's not correct. What do I do?

I'm also supposed to be able to insert a person p, into a tree t in the position pos - if the position doesn't exist it should just return the tree. insert : tree * parents list * person -> tree

I just can't get my head around this, and I'm hoping that someone will be able to help me. I hope I've been clear enough in this (I know it's long).

Answer 1

(Reposting as apparently my previous answer didn't survive the db crash).

You're taking the head of the list to decide whether to branch into the mother or the father subtree. This is correct. You then use the tail of the list as the rest of the path. This is also correct. However when the list is empty (i.e. you have reached your destination), you do this:

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

In other words: Nothing. If you change this to:

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

It will work as intended, replacing the Node of the tree that your path leads you to with Unspec.