(*tsearch-followup*)

(* Tree search data structures and traversal and insertion fns *)


(* Tutorial/Practical *)
(*
(1) Traverse x using preorder, inorder, and postorder
(2) Draw (using pen and paper) the tree x
    NOTE: you may have to manually analyse x as follows
          val Tree(l,a,r) = x;  (etc!) *)

val Tree(lx,a,rx) = x;
val Tree(llx,b,rlx) = lx and Tree (lrx,c,rrx) = rx;
(* and so on, to determine "shape" of x *)

(*
(3) Create a new type of tree, using a different type and predicate
    For example, a dictionary of strings. Hint: you must define
    the appropriate binary predicate. *)

(* NOTE: I did not mean that you redefine datatype 'a tree !! *)

fun bp (x:string) (y:string) = x<y; (* binary predicate *)

val cats = make_tree bp ["ted","alice","poppy","nelson","ginger"] tempty;

(*
(4) Write a function that will deliver true if a specific object
    can be found in a tree (think... object is either in the left
    branch, or in the right branch)  *)

fun p x y = x=y (* p is a predicate *)

fun find_silly p x tempty = false
   |find_silly p x (Tree(l,a,r)) = 
       if p x a 
       then true
       else (find_silly p x l) orelse 
            (find_silly p x r);
(* Why is it silly? Belts and braces??? *)

fun find_very_silly p x y = 
    if y = tempty
    then false
    else let val Tree(l,a,r) = y
         in if p x a 
            then true
            else (find_very_silly p x l) orelse
                 (find_very_silly p x r) end;

fun find p x tempty = false
   |find p x (Tree(l,a,r)) = (p x a) orelse 
                             (find p x l) orelse 
                             (find p x r);

(*
(5) Write a function that delivers an integer result n, where n
    is the number of nodes in a tree *)

(* Mmmmm.... could I modify "find" ? *)

fun count tempty = 0
   |count (Tree(l,_,r)) = 1 + (count l) + (count r);

(* 0 as false, + as orelse? Maybe .... *)

(*
(6) Write a function that delivers an integer result n, where n
    is the number of "leaf" nodes in a tree *)

fun leafs tempty = 0
   |leafs x = if leafp x
              then 1
              else let val Tree(l,_,r) = x
                   in (leafs l) + (leafs r) end;

(*
(7) Write a function that takes two trees as arguments and 
    checks for equality (are 2 trees equal?).
    NOTE: 2 interpretations are possible, 
          (a) T1 is same "shape as" T2
          (b) The contents of the nodes of T1 are the same
              as the contents of the nodes of T2 *)

(* Quite a number of ways to do this, one below !!! *)

fun equal_trees x y = (inorder x) = (inorder y);

fun equaltrees tempty tempty = true
   |equaltrees (Tree(_,_,_)) tempty = false
   |equaltrees tempty (Tree(_,_,_)) = false
   |equaltrees (Tree(lx,x,rx)) (Tree(ly,y,ry)) =
          (x=y) andalso (equaltrees lx ly) andalso (equaltrees rx ry);

(*
(8) Write a function to delete a node from a tree *)

fun remove e [] = []
   |remove e (h::t) = if e=h
                      then t
                      else h::(remove e t);

fun delete e t = make_tree p (remove e (inorder t)) tempty;


(* again a few ways to go!!! *)

(*
Notes/observations

 (a) Most students had problems with question 1. They did not know what was
     expected of them.
 (b) Most students were using things like "if a = b then true else false"
     This is kid's stuff. Consequently most students were unaware of 
     the semantics of andolso and orelse, and how they can be exploited.
 (c) Note the use of (Tree(l,a,r)) as a functions argument. Why is it in
     brackets? I dont know!
 (d) Note also use of (Tree(_,_,_)) in equaltrees. That is, so long as 
     it is not tempty, and I dont care what it contains.
 (e) POLYMORPHISM. Many tried to remove/destry it. They did so by redefining
     the data type when we did question 2. This make the rest of the functions useless,
     or at least again destroys polymorphism. 
 (f) POLYMORPHISM. why bother? What is to stop us having a tree that has nodes
     Tree(l,a,r) where a is again a tree, Tree(l,a,r). How could this be useful.
     Imagine we have a tree of cities, where each node is a tree of the surnames of 
     people in that city, where each node is a tree of people in a city with a given 
     surname. We can then have a directory enquires: Which city, what name, first name?
     and respond in 3nlogn. However, we then need a binary predicate that works between
     trees. That's not too difficult, is it?
*)