AVL Tree in ML- Rotate left, Warning: match nonexhaustive

Question

I am implementing an AVL tree in SML:

Here are my datatypes:

datatype 'a AVLTree = Nil | Br of ((int*('a))*('a AVLTree)*('a AVLTree));
datatype Balance = RR | LR | LL | RL;
exception NotFound;
exception NullValue

I am now writing the function Rotate- Left, and I wrote it as follows:

fun rotate_left Nil = Nil
     |rotate_left (Br(x,A,Br(y,B,C))) = (Br(y,Br(x,A,B),C));

I am getting from the interpreter:

Warning: match nonexhaustive

How do I fix this with the current datatypes I have? I tried using wildcards but with no success..

Answer 1

I am getting from the interpreter:

Warning: match nonexhaustive

How do I fix this with the current datatypes I have? [...]

Perhaps this warning should not be avoided. You can after all not rotate all trees.

The left rotation would look like this:

  A              B
 / \            / \
…   B     ~>   A   C
   / \        / \ / \
  …   C      …   …   …
     / \
    …   …

---

Given an AVL tree type that does not keep track of the height,

datatype 'a AVLTree = Nil | Br of 'a * 'a AVLTree * 'a AVLTree

(the parentheses are not necessary) your version of rotate_left is correct. I've rewritten it below and renamed the left and right sub-branches. One point is that B's left sub-branch becomes A's new right sub-branch.

fun rotate_left (Br (a, leftA, Br (b, leftB, rightB))) =
                 Br (b, Br (a, leftA, rightB), rightB)

This is a partial function, and the patterns it fails to match are:

• Nil – but a left-rotation of an empty tree isn't well-defined.

• Br (a, leftA, Nil) – but the following left-rotation also isn't well-defined:

    A             ?
   / \           / \
  …   Nil   ~>  A   …
               / \
              …   ?
  

If you were to try and perform a left-rotation of one of those trees, there would not be a meaningful result. Having the Warning: match nonexhaustive is not satisfying either. You could instead raise a meaningful exception, e.g.

fun rotate_left (Br (a, leftA, Br (b, leftB, rightB))) =
                 Br (b, Br (a, leftA, rightB), rightB)
  | rotate_left _ = raise Fail "Invalid left-rotation"

---

Now, you haven't really explained why there's an extra int in your datatype definition. Maybe this is the pre-computed height of the tree? That'd be neat (you could encode that meaning using a type alias), since then your invariance check becomes cheaper. In that case, a left-rotation would need to update the heights:

type height = int
datatype 'a AVLTree = Nil | Br of height * 'a * 'a AVLTree * 'a AVLTree

According to the top drawing, A's new height is max(height(leftA), height(leftB)) + 1 and B's new height max(height(new A), height(rightB)). Extending the rotate_left function for this:

fun height Nil = 0
  | height (Br (h, _, _, _)) = h

fun rotate_left (Br (ha, a, leftA, Br (hb, b, leftB, rightB))) =
    let val ha' = Int.max (height leftA, height leftB) + 1
        val hb' = Int.max (ha', height rightB) + 1
    in Br (hb', b, Br (ha', a, leftA, rightB), rightB) end
  | rotate_left _ = raise Fail "Invalid left-rotation"

---

Edit: It occurs to me that the extra int is in a nested tuple and so probably turns the tree into a mapping from some integer to some 'a. In that case, disregard the optimization of keeping the height in the tree.

Answer 2

I played around with this functions a little bit and this is what I got that works:

 fun RL node =
  case node of Br(x,A,Br(y,B,C)) => (Br(y,Br(x,A,B),C))
                             | _ => node;

Answer 3

You function is not defined for values with the shape Br(x, A, NIL).

What should happen in this case?

fun rotate_left Nil = Nil
  | rotate_left (Br(x,A,Br(y,B,C))) = (Br(y,Br(x,A,B),C))
  | rotate_left (Br(x, A, Nil)) = (* ??? *);