Lab 3: AA trees in Haskell

In this lab you will implement AA trees in Haskell. The goal of the lab is to:

• let you compare the functional and object-oriented approaches to programming,
• let you practise defining modules and abstract data types in Haskell, and
• let you practise defining recursive functions over recursive data structures.

The task

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 tree
• get :: 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 tree
• insert :: Ord a => a -> AATree a -> AATree a, which inserts the given value unless a value equal to it already exists in the tree
• inorder :: AATree a -> [a], which returns a list of all elements in the tree in increasing order
• size :: 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 invariant

The 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 sorted
• checkLevels :: 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.

An alternative version of AA trees

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.

Testing

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.

Useful links

• Standard library: http://www.haskell.org/ghc/docs/latest/html/libraries/
• Hoogle, a search engine for the Haskell libraries: http://www.haskell.org/hoogle/

Submission

Submit Main.hs and AATree.hs to Fire.

• Your code should compile without warnings
• It must also pass the testing section above
• All function definitions should be adequately commented
• Give the time complexity of each function
• Also comment how you modify the tree in insert — say what you do and why