COMP1011 Exercises for Week 12
Computing 1A 05s2 Last updated Fri 14 Oct 2005 23:32
Mail cs1011@cse.unsw.edu.au

Tute Exercises Week 12

Trees

In the lecture, we defined generic trees as 

data  Tree a = Leaf
             | Node a (Tree a) (Tree a)
             deriving (Show)
We call trees like Tree, which store elements in their nodes, augmented trees.

As discussed in the lecture, a ordered binary tree is an augmented tree where

  1. for any given node, if the node stores a value x, then all the integers stored in nodes of the left subtree must be smaller than x.
  2. for any given node, if the node stores a value x, then all the integers stored in nodes of the right subtree must be greater than x.
(note that we assume here, for simplicity reasons, that the tree holds no duplicate items)

We defined the following functions in the lecture: 

-- insert an  element into an ordered tree so that the
-- resulting tree is ordered as well. Trying to insert an 
-- already exisiting  element into the tree leads to an error
-- message
insertTree:: Ord a => a -> Tree a -> Tree a
insertTree x  Leaf = Node x Leaf Leaf
insertTree x (Node y tree1 tree2) 
    | x < y     = Node y (insertTree x tree1) tree2
    | x == y    = error "insertTree: element already in tree!\n"
    | otherwise = Node y tree1 (insertTree x tree2)
Implement a function deleteFromTree:: Ord a => a -> Tree a -> Tree a which, given an ordered tree and an item, searches for the item and if found, deletes it from the tree. The resulting tree does not have to be ordered. Note that there is more than one correct way to delete an item from a tree. For example, deleting 5 in tree 
         Node 5                 
       /        \   
   Node 2      Node 6    
  /    \       /    \
Leaf   Leaf  Leaf   Leaf
can result in either 
         Node 2                 
         /    \   
     Leaf     Node 6    
              /  \
          Leaf    Leaf
or 
        Node 6                 
       /     \   
   Node 2     Leaf
  /     \   
Leaf   Leaf
That is, if you delete a Node value, you can either rotate the remaining elements to the left or to the right.

Data Types and Equivalence

The following is an alternative definition of an augmented tree - it stores values in the node and the leaves: 
data  Tree1 a = Leaf1 a
              | Node1 a (Tree1 a) (Tree1 a)
              deriving (Show)

Two data types T1 and T2 are equivalent if we can write functions toT2:: T1 -> T2 and toT1:: T2 -> T1 such that toT2 (toT1 x) = x and toT1 (toT1 y) = y for all x :: T2 and y :: T1 (or in more mathematical terms, the functions are bijective)

In particular, if two types differ only in the names of the data constructors, the two types are equivalent. In case of Tree and Tree1, Leaf1 has one argument, whereas Leaf has none. Are they still equivalent? Why is the type Tree a not equivalent to [a]?