|COMP1011 Exercises for Week 12|
|Computing 1A 05s2||
Fri 14 Oct 2005 23:32
In the lecture, we defined generic trees as
We call trees like Tree, which store elements in their nodes, augmented trees.data Tree a = Leaf | Node a (Tree a) (Tree a) deriving (Show)
As discussed in the lecture, a ordered binary tree is an augmented tree where
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 Leafcan result in either
Node 2 / \ Leaf Node 6 / \ Leaf Leafor
Node 6 / \ Node 2 Leaf / \ Leaf LeafThat is, if you delete a Node value, you can either rotate the remaining elements to the left or to the right.
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]?