Defining Tree's and Search Function

Question

I am trying to define my tree and create a search function, but I think I am getting lost in the syntax of SML. Here is my tree

datatype either = ImAString of string | ImAnInt of int;
datatype eitherTree = Empty
                    | eLEAF of either 
                    | eINTERIOR of (either*eitherTree*eitherTree);

This is my search function

fun eitherSearch (eLEAF(v)) x = false
  | eitherSearch (eINTERIOR(ImAnInt(v), lt, rt)) x =
    if x < v then eitherSearch lt v
    else if x > v then eitherSearch rt v
    else true;

And this is how I defined my tree

val T2 = eINTERIOR(ImAnInt(4), eLEAF(ImAnInt(1), eLEAF(ImAnInt(2), Empty, Empty), Empty), eINTERIOR(ImAnInt(3), Empty, Empty));

This returns

val T2 =
  eINTERIOR
    (ImAnInt 4,eINTERIOR (ImAnInt #,eINTERIOR #,Empty),
     eINTERIOR (ImAnInt #,Empty,Empty)) : eitherTree

I'm guessing this isn't correct because those # symbols don't make sense. Is there a better way to define the tree so that it works in the search function? When I define a smaller tree like

val T1 = eINTERIOR(ImAnInt(5), eLEAF(ImAnInt(4)), eLEAF(ImAnInt(6)));

The search function works correctly, but in T2 I don't think I'm understanding how to write mult layered trees.

My question is why my implementation of T2 doesn't work with the search function when T1 does. And why does T2 have the # in the declaration. I'll edit it to make it more clear @SimonShine — TrashMachine139, Feb 20 '18 at 07:20
The `#`s are a byproduct of SML/NJ. See [Increasing the print depth in SML/NJ](https://stackoverflow.com/questions/5060049/increasing-the-print-depth-in-sml-nj), [Expanding # in sml](https://stackoverflow.com/questions/5051081/expanding-in-sml) or [SMLNJ expand # in output](https://stackoverflow.com/questions/3756460/smlnj-expand-in-output) — sshine, Feb 20 '18 at 07:21
Do you know why my T2 doesn't work properly in the search function? It can only read true for the head of the tree and every other number input returns an error. @SimonShine — TrashMachine139, Feb 20 '18 at 07:32

score 1 · Answer 1 · answered Feb 20 '18 at 07:57

Doing if ... then ... else true is slightly redundant; often you might instead use the lazy binary operators orelse and andalso, but when you're specifically interested in whether something is less, equal or greater, use Int.compare:
```
if x < v then eitherSearch lt v
else if x > v then eitherSearch rt v
else true;
```
becomes:
```
case Int.compare (x, v) of
     EQUAL   => true
   | LESS    => eitherSearch lt v
   | GREATER => eitherSearch rt v
```
You don't need three constructors in your tree; Empty, eLEAF, eINTERIOR, since you can create the same tree in different ways; this will just make functions that recurse over them more complicated. For example, the following values are equivalent:
```
val t1 = eINTERIOR (ImAnInt 42, Empty, Empty)
val t2 = eLEAF (ImAnInt 42)
```
A simpler binary tree definition could look like this:
```
fun eitherTree = Empty | Interior of either * eitherTree * eitherTree
```
You might have noticed a warning as you compile the function eitherSearch:
```
! Warning: pattern matching is not exhaustive
```
See what happens when you run it with a tree containing an ImAString ... value:
```
- eitherSearch (eINTERIOR (ImAString "Hello", Empty, Empty)) 42;;
! Uncaught exception:
! Match
```
or an Empty subtree:
```
- eitherSearch (eINTERIOR (ImAnInt 41, Empty, Empty)) 42;
! Uncaught exception:
! Match
```
Functions should ideally not crash at run-time.

Since your eitherTrees can contain both strings and ints, and your function eitherSearch explicitly looks for ints, you need to specify how it should deal with strings. It seems that you assume that eitherTrees are sorted as binary search trees as long as the nodes contain ints, but what happens when they contain strings instead? Must you then assume that the result could be in either sub-tree?

I wouldn't know how to complete the following:
```
fun eitherSearch Empty = false
  | eitherSearch (Interior (ImAString s, lt, rt)) = ???
  | eitherSearch (Interior (ImAnInt n, lt, rt)) = ...
```
As for T2, I can't compile it: You're using eLEAF but giving it three arguments. Perhaps in the version that you're testing with, rather than the version you posted, you are using eINTERIOR instead. This problem will go away once you (1) stick to just two constructors in your datatype definition, and (2) cover all patterns in eitherSearch.

How do I ask and answer homework questions?

Thank you for your advice, I greatly appreciate it. I will continue trying to make the tree work. Thanks again for taking the time too look at it. — TrashMachine139, Feb 20 '18 at 08:17

Defining Tree's and Search Function

1 Answers1