In this lab you will implement AA trees in Haskell. The goal of the lab is to:
You will define and test an implementation of AA trees. Your code will consist of two files, AATree.hs
and Main.hs
:
AATree
AATree.hs is the AA tree itself. It should be implemented as a Haskell module and export the type AATree
and following functions:
emptyTree :: AATree a
, which returns an empty AA treeget :: Ord a => a -> AATree a -> Maybe a
, which returns the value in the tree which is equal to the given value, or Nothing if such a value does not exist in the treeinsert :: Ord a => a -> AATree a -> AATree a
, which inserts the given value unless a value equal to it already exists in the treeinorder :: AATree a -> [a]
, which returns a list of all elements in the tree in increasing ordersize :: AATree a –> Int
, which returns the number of nodes in the tree (seen as a binary tree, not as a 2-3-tree)height :: AATree a –> Int
, which returns the height of the tree (seen as a binary tree, not as a 2-3-tree)checkTree :: Ord a => AATree a -> Bool
, which checks that the tree satisfies the AA tree invariantThe function checkTree
is already defined for you. Unfortunately, it is not yet fully implemented. You need to complete the following helper functions:
isSorted :: Ord a => [a] –> Bool
, which checks that a list is sortedcheckLevels :: AATree a –> Bool
, which checks that a single node satisfies its part of the invariant,and a couple more simple functions (see AATree.hs).
One function in AATree.hs is optional: you don’t need to implement remove
, but you must implement all other functions!
Note that the tree should not contain any duplicate elements (insert only adds an element if it’s not in a tree). So what you’re implementing is a data structure that could be used as a set.
Main
Main.hs
is the main program. It should read in words from standard input and make a tree from them. Then it should compute and print out the tree’s size (\(n\)) and height (\(h\)), the optimal height (\(h' = ⎡\log_2(n+1)⎤-1\)), and the ratio (\(\frac{h}{h'}\)) between the actual and optimal height. (In a correct implementation of AA trees, the ratio should never be greater than 2.) It should also test the tree with the function checkTree
and print the result. Finally, it should print the first 20 words in the tree in dictionary order.
Example output from Main.hs
with swahili-small.txt
:
Size: 12582
Height: 18
Optimal height: 13
Height / Optimal height: 1.3846153846153846
checkTree: True
First 20 words: A ABP AC AD ADLugha ADNa ADR ADSL ADWabantu ADwaarabu AIDS AL ...
Note that depending on what definition of tree height you implement, the value in your output may differ from the one above.
The words in the input data are separated with spaces or newlines. The easiest way to read them in is with the standard functions getContents
and words.
Some presentations of AA trees do not store the level of each node. Instead, they colour each node red or black — red means that a node is at the same level as its parent. In particular, Sedgewick’s book does this and calls it a “red-black BST” (not to be confused with a red-black tree).
If you want to, for whatever reason, you can implement this version instead. In that case you should start by downloading AATree-alternative.hs and renaming it to AATree.hs
. Apart from that, the lab will work the same.
First try some small examples, which should involve rotations. One example you could try is the sentence “The quick brown fox jumps over the lazy dog”.
You must also use the test program, CheckInsert.hs
. This program builds trees from all possible permutations of lists up to length 10. Each tree is then tested if it satisfies the invariant by calling the function checkTree
. It is also checked that the tree contains the right elements by calling the function inorder
and compare the result to the sorted version of the list.
Then test with the following two files:
swahili-small.txt
(400KB) contains about 65000 words from the Swahili Wikipedia, of which 12600 are unique;sorted-small.txt
(100KB) contains just the 12600 unique words from swahili-small.txt
, in dictionary order.You can download all files in one go as this big zip file.
Submit Main.hs
and AATree.hs
to Fire.
insert
— say what you do and why