CPSC425 Spring 2008
HW 10: An Expression Tree in ML

In class we defined the following type: 
datatype 'a tree = EmptyTree | Node of 'a * 'a tree * 'a tree
We also started to write a function makeExpTree: char list -> tree that takes a list of characters representing a prefix integer expression and returns an equivalent expression tree. For example, the list 
makeExpTree [#"+", #"1", #"*", #"2", #"3"]
would return 
Node (#"+", Node(#"1", EmptyTree, EmptyTree), Node(#"*", Node(#"2", EmptyTree, EmptyTree), 
Node(#"3", EmptyTree, EmptyTree)))
This is easier to understand with a little formatting: 
Node (#"+", 
      Node(#"1", EmptyTree, EmptyTree), 
      Node(#"*", 
           Node(#"2", EmptyTree, EmptyTree), 
           Node(#"3", EmptyTree, EmptyTree)))
Remember that we started to write makeExpTree in class and determined that we needed a function that returned the tree it constructed AND the rest of the list so that we knew where to start building the next part of the tree. This will need to be a helper function, as the type above requires that makeExpTree return just a tree.

Output

You will find that the tree that makeExpTree returns is not formatted nicely by the repl. ML will insert "#" characters for things that it doesn't have room for on a single line, so you won't be able to see the whole result.

To help with this I have provided a function printCharTree: char tree -> unit that takes a char tree and prints it nicely formatted in a style similar to that above. This function and its support functions are available in file prettyPrintTree.sml. Just copy this to your directory and load it after you load your tree type and functions. You can then pass the result of your call to makeExpTree to printCharTree and you'll get legible output.

Warning About Defining New Types

Each time you load a definition for a datatype, such as type tree above, you are defining a new type. This type is different from all other types, including previous definitions of that type. This means that values defined under a previous definition of that type are in fact of a different type. This really makes perfect sense, since the redefinition could (and typically would) change the definition of the type, so there's no reason to think they're the same. But even if the definition is identical, it's a new type. This is illustrated by the sml session below (comments were inserted after the fact by me *): 
(* define datatype tree *)
- datatype 'a tree = EmptyTree | Node of 'a * 'a tree * 'a tree;
datatype 'a tree = EmptyTree | Node of 'a * 'a tree * 'a tree

(* define t1 to be a value of type tree *)
- val t1 = EmptyTree;
val t1 = EmptyTree : 'a tree

(* redefine datatype tree, but same definition *)
- datatype 'a tree = EmptyTree | Node of 'a * 'a tree * 'a tree;
datatype 'a tree = EmptyTree | Node of 'a * 'a tree * 'a tree

(* define t2 to be a value of this new type tree -- the old tree is no *)
(* longer available*)
- val t2 = EmptyTree;
val t2 = EmptyTree : 'a tree

(* compare t1 and t1 for equality -- error indicates that they are of *)
(* different types *)
- t1 = t2;
stdIn:5.1-5.8 Error: operator and operand don't agree [tycon mismatch]
  operator domain: ''Z ?.tree * ''Z ?.tree
  operand:         ''Z ?.tree * 'Y tree
  in expression:
    t1 = t2
One solution is to put your type definition in a file separate from your functions and load that file just once, at the beginning of your session. Alternately, you can keep them all together and reload the type definition each time you reload your functions, but in this case you'll need to put ALL of your files -- including the print routines I gave you -- in one file so that they all tie to the same type definition.