Adding a node to a tree in SML

Question

I was advised to ask this as a separate question, so that I will do.

I have a tree of people, like in genealogy. It starts with a person and branches off into parents, grandparents, etc. I want to be able to insert a person into a spot on the tree (basically replacing whoever is there).

These datatypes are important:

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

The assignment is as follows: Declare a function insert : tree * parents list * person -> tree, so that calling insert (t, pos, p) will insert the person p in the postion pos in the tree i - assuming that the position exists in the tree. If it doesn't it should return t.

So I need to be able to take a person in my tree (let's say Mom) and replace her with Lucy (Mom and Lucy are both pre-declared values using the datatype person).

So far I have this:

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

All is seems to do is delete whoever is in pos of t and replace the root with p - not quite what I want it to do :S Also, the pattern matching isn't finised.

Any ideas to get me moving here?

Answer 1

Ok, when you reach the given position, you want to replace the person at that point in the tree with the given person. What you're doing is, you're replacing the person each step of the way, except when you reach the destination, in which case you simply delete the node that is there.

So what you need to do is:

In the case where the parents-list is not yet empty, don't replace the person n with p - just traverse into the appropriate subtree.

In the case where the parents-list is empty and you're currently at an Info-node, do replace the person in that node with p.

In the case where the parents-list is empty and you're currently at an Unspec-node, replace the Unspec with a new Info-node containing p and two empty subtrees (i.e. Unspecs).

In the case where you reach an Unspec node although the parents-list is not yet empty, just return Unspec, keeping the tree unchanged as per the assignment.