user1313623 February 2016

Checking whether a given value exists in a binary tree

I am new to SML. I am trying to check whether a given value exist in the binary tree or not. Below is the snippet of the code. Upon execution it gives

Warning : match nonexhaustive (n,Node (t1, j, t2)) => ...

I cannot understand why it is showing this way. I guess I have covered all possible case. Can anyone give me hint or link which will be helpful to remove this warning.

datatype inttree = Empty | Node of inttree * int * inttree;

(*find(n,K) here n is the key that we have to find in inttree K*)
val rec find = fn(n, Node(t1,j,t2)) =>
    let 
        val t = Node(t1, j, t2)
        val compare = fn(i,j) => i = j
        val find' =
            fn (n,Empty) => false                (* if we have reached the empty node then we are not able to find the key therefore return false *)
             | (n,Node(t1,j,t2)) =>
               if compare(n,j)
               then true                         (* if value n and j are equal we have found the key n in the tree*)
               else find(n,t1) orelse find(n,t2) (* if the value is not equal check in left subtree if found return true else check in the right subtree*) 
    in
        find'(n,t)
    end;

Answers


John Coleman February 2016

Given your datatype declaration, a fairly direct recursive approach is possible. Since this seems to be homework, I don't want to give a complete solution, but here is a function which has a similar flavor:

fun allEven Empty = true
|   allEven (Node(t1,i,t2)) =
       if i mod 2 = 1 then false
       else allEven t1 andalso allEven t2;

This function returns true or false depending on whether or not all integers in the tree are even. It has a basis case

allEven Empty = true

(true since there are no odd numbers in an empty tree to serve as counter-examples) and a recursive case

allEven (Node(t1,i,t2)) =
           if i mod 2 = 1 then false
           else allEven t1 andalso allEven t2;

If the integer at the node is odd, return false -- otherwise return true if the recursive call to both branches evaluate to true.

Typical runs:

- allEven (Node(Node(Empty,3,Empty),5,Node(Node(Empty,6,Empty),7,Empty)));
val it = false : bool
- allEven (Node(Node(Empty,4,Empty),2,Node(Node(Empty,6,Empty),8,Empty)));
val it = true : bool

Your function should be about this long and follow the same basic recursive pattern.


Simon Shine February 2016

  1. Besides val rec, you can also write fun and specify the arguments on the left-hand side of the =.
  2. The helper function compare is largely redundant. You might as well use =. Also, what one would call a compare function in ML is usually one that returns the type order, having the values LESS, EQUALS and GREATER:

    - ‚ÄčInt.compare (3, 5);
    > val it = LESS : order
    
  3. When writing an if ... then true else ... or similar statement that returns the type bool, you might as well just use the combinators orelse and andalso. For example, you can replace the following:

    if compare(n,j)
    then true
    else find(n,t1) orelse find(n,t2)
    

    with:

    n = j orelse find (n, t1) orelse find (n, t2)
    
  4. Much like the built-in functions List.exists and List.all take a function as predicate and scans a list in the attempt to prove either that at least one element exists for which this is true, or that it is true for all elements, you can make functions treeExists and treeForall:

    datatype intTree = Empty | Node of inttree * int * inttree;
    
    fun treeExists f Empty = false
      | treeExists f (Node (leftTree, x, rightTree)) =
        f x orelse treeExists f leftTree orelse treeExists f rightTree
    
    fun treeForall f Empty = true
      | treeForall f (Node (leftTree, x, rightTree)) =
        f x andalso treeForall f leftTree andalso treeExists f rightTree
    

    Making functions find and allEven has now become simpler:

    fun find (x, tree) = treeExists (fn y => x = y) tree
    fun allEven tree = treeForall (fn x => x mod 2 = 0) tree
    

    since all the recursion has been left to new library functions.

Post Status

Asked in February 2016
Viewed 3,762 times
Voted 10
Answered 2 times

Search




Leave an answer