Homework Treenumbers

Task description

It is possible to define some kind of arithmetics for nearly any data structure by specifying the semantics of various operations. In the case of Haskell, the most general numeric type class, Num only defines addition, subtraction, multiplication and a handful of unary operations, e.g. absolute value. Your task is to define addition and subtraction for binary search trees (BSTs) the following way:

• t₁ + t₂ = t, where t contains all the elements of t₁ and t₂
• t₁ – t₂ = t, where t contains only the elements of t₁ not found in t₂

Example (@ denotes leaves):

              t1                t2                  t1+t2               t1-t2

              4                 3                     4                   2
             / \               / \                   / \                 @ \
            /   \             /   \                 /   \                   7
           2     7           1     5               /     \                 / @
          / @   / @         @ @   / \             2       7               6
         1     6                 4   8           / \     / \             @ @
        @ @   @ @               @ @ @ @         1   3   6   8
                                               @ @ @ @ / @ @ @
                                                      5
                                                     @ @

The set of binary search trees must be closed under the above defined addition and subtraction operations, i.e. if both t₁ and t₂ are BSTs, t must also be a BST. In essence, if we interpret these trees as sets, addition corresponds to taking the union, and subtraction corresponds to the usual definition of set subtraction.

Note that there are several different valid outcomes for both operations. As long as the result is a BST, it is considered correct.

Haskell specification

Use the following datatype definition:

{-
  Ord a => Tree a: a binary tree that holds values of type a in each
  of its nodes, the left child of the root is a BST whose elements are
  all less than the value in the root, and the right child of the root
  is a BST whose elements are all greater than the value in the
  root. No value occurs more than once in the tree.
-}

data Tree a = Leaf | Node a (Tree a) (Tree a) deriving Show

First of all, define two auxiliary operators to insert (-->) and remove (<--) individual elements:

-- The operators are right associative with a low precedence
infixr 1 -->
infixr 1 <--

{-
  n --> t = the tree obtained by inserting n into t. If n was
  already in t, then t is returned unchanged.
-}
(-->) :: (Ord a) => a -> Tree a -> Tree a

{-
  n <-- t = the tree obtained by removing n from t. If n was
  not in t, then t is returned unchanged.
-}
(<--) :: (Ord a) => a -> Tree a -> Tree a

Afterwards, given the constraints (Ord a, Num a) make the type (Tree a) the instance of the Num class, and overload the + and - operators according to the definitions given above. Implement the rest of the necessary operations (*, abs, signum, fromInteger) to simply produce an empty tree.

Examples

If your auxiliary functions and overloads are working properly, you can easily test the example above:

*Main> 6 --> 7 --> 1 --> 2 --> 4 --> Leaf
Node 4 (Node 2 (Node 1 Leaf Leaf) Leaf) (Node 7 (Node 6 Leaf Leaf) Leaf)

*Main> 4 --> 8 --> 1 --> 5 --> 3 --> Leaf
Node 3 (Node 1 Leaf Leaf) (Node 5 (Node 4 Leaf Leaf) (Node 8 Leaf Leaf))

*Main> (6 --> 7 --> 1 --> 2 --> 4 --> Leaf) + (4 --> 8 --> 1 --> 5 --> 3 --> Leaf)
Node 4 (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf)) (Node 7 (Node 6 (Node 5 Leaf Leaf) Leaf) (Node 8 Leaf Leaf))

*Main> (6 --> 7 --> 1 --> 2 --> 4 --> Leaf) - (4 --> 8 --> 1 --> 5 --> 3 --> Leaf)
Node 2 Leaf (Node 7 (Node 6 Leaf Leaf) Leaf)

Other tests:

*Main> 1 <-- 5 <-- (4 --> 3 --> 2 --> 1 --> Leaf)
Node 2 Leaf (Node 3 Leaf (Node 4 Leaf Leaf))

*Main> foldr (-->) Leaf [6,2,3,9,7]
Node 7 (Node 3 (Node 2 Leaf Leaf) (Node 6 Leaf Leaf)) (Node 9 Leaf Leaf)

Optional improvement

Try to define multiplication (*) as an intersection, i.e. t₁ * t₂ = t, where t is a BST that contains only the values present in both t₁ and t₂. For example:

*Main> (6 --> 7 --> 1 --> 2 --> 4 --> Leaf) * (4 --> 8 --> 1 --> 5 --> 3 --> Leaf)
Node 4 (Node 1 Leaf Leaf) Leaf