Deadlines: first deadline 17th May, second deadline 27th May. Submissions by Fire.

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.hs is the AA tree itself. It should be implemented as a Haskell module and export the same functions as BinSearchTree and AVLTree in the Haskell compendium. It should also export the following two functions:

    • size :: AATree a –> Int, which returns the number of nodes in the tree;

    • maxheight :: AATree a –> Int, which returns the height of the tree, that is, the length of the longest path from the root to a leaf.

    The function checkTree is already defined for you. It checks that a tree fulfils all the requirements (i.e. satisfies the invariant) of an AA tree. 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;

    • checkNode : AATree a –> Bool, which checks that a single node satisfies its part of the invariant.

    One function in AATree.hs is optional: you don’t need to implement remove, but you must implement all other functions!

  • 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' = ⎡log2(n+1)⎤-1), and the ratio (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: 65317
Height: 24
Optimal height: 15
Height / Optimal height: 1.6
checkTree: True
First 20 words: A A A A A A A A A A ABP AC AC AD AD AD AD ADLugha ADNa ADR

    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.

Then test with the following two files:

You can download all files in one go as this big zip file.

Useful links

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.