Standard ML binary tree type

Question

I'm studying ML in class and I've run into a homework problem I am stuck on. I've spent all day yesterday searching but made little progress and we did not talk about this in class, so I am hoping you guys can help me.

We are given:

datatype which = STRING of string | INT of int

Part 1. We are told we need to create another datatype named whichTree for a binary tree containing the values of type which where data is only at the leaves of the tree.

Part 2. We need to create a whichSearch function having type whichTree -> int -> bool returning true or false based on whether the int is in the tree.

This is what I have so far:

datatype which = STRING of string | INT of int;
datatype whichTree = Empty | Node of int*whichTree*whichTree;

val t1 = Node(6, Node(4,Empty,Empty), Node(15, Node(11,Empty,Empty), Node(24,Empty,Empty)));
val t2 = Node(157,Empty,Empty);
val t3 = Node(102,t1,t2);

fun whichSearch (i, Empty) = false
| whichSearch (i, Node(entry, left, right)) =
    if i = entry then true
    else whichSearch (i, left)
    orelse whichSearch (i, right);

The problem I am now facing is this:

1. My whichTree does not contain the type which. I am not sure how I can fix that.
2. I should have my whichSearch function of type whichTree -> int -> bool but it is int * whichTree -> bool and am working on trying to figure out how to fix things. I am not sure how I would go about fixing this as I have to specify a value for i in whichSearch to search for. I'm searching on this but any tips would be great.

Can anyone help? If so thank you! And thank you to the guys who already responded.

Answer 1

Based on what you've come up with, I think I should point out a few rules in the Standard-ML language that you are breaking, which I hope will make it easier for you to procede:

• Each name you introduce, be it a type, function or variable, can only mean one thing (as long as they are in the same scope in the program).

  • You break this by first defining a datatype which and then defining a function by the same name.
  • You also break it by first defining a datatype whichTree and then defining another datatype by the same name.
  • You actually also break it on the 3rd line, by introducing two new datatype constructors (STRING and INT) that were already introduced on the 1st line. Remember that when you use these datatype declarations, you're not only defining a type name but also the constructors for the type.

• If you wish to introduce a datatype constructor taking two parameters, which it looks as though you want to do on line 3, you should use an asterisk * between the types, not the arrow operator ->.

I would also agree with Victor, you should think in general terms about what a binary tree actually is, conceptually. Then translate this into Standard-ML.

---

Edit after the code in the question was rewritten: Your new code is much better. As you point out, you stand now with two questions:

1. How do you make the tree a tree of which values? Well, your tree is currently a tree of int values, so doesn't it make sense that you should change int for which? But you also state that your tree datatype should be "a binary tree containing the values of type "which" where data is only at the leaves of the tree". This is distinct from what you've currently coded, which keeps an int at every non-leaf node. The non-leaf nodes are determined by the recursive case in the datatype declaration, while the leaf nodes are determined by the non-recursive case.

2. A function of type (A * B) -> C (where A, B and C are types) can be rewritten to be of type A -> B -> C. Both are valid and usable in Standard-ML, but the second form is usually preferred in functional programming languages because it allows a technique known as currying, which means "partial function application". To make the change, you basically write parameters in a different way: Instead of myFunction(a, b), you write myFunction a b -- both where you define the function and where you use it.

Note that I suggest you handle point 2 later, first focus on getting the datatypes correct and getting a working search function, then you can change its type when you know it's otherwise correct.

Answer 2

Forget about ML. Using pen and paper (or marker and white board), can you explain how a binary tree containing your data in the leaves would look like? Can you explain in broad terms how you would search for an element in the tree? (hint: a search needs to traverse nodes by deciding whether to go left or right, so you need to keep some information in the tree nodes to help the search algorithm decide).

Once you ave the representation and algorithms laid out as english sentences, translating them to SML will be easier.