# HW 8 - Purely Functional Data structures

```
-- Advanced Programming
-- by <YOUR NAME HERE> <pennkey> and <PARTNER's NAME HERE> <partner's pennkey>
{-# OPTIONS -Wall -fwarn-tabs -fno-warn-type-defaults #-}
{-# LANGUAGE KindSignatures, ScopedTypeVariables, FlexibleInstances #-}
```

```
module Main where
import Prelude hiding (zipWith,zipWith3)
import Test.QuickCheck hiding (elements)
```

The goal this homework is to implement a purely functional version of AVL trees in Haskell. If you are unfamiliar with this data structure, the wikipedia page is a good start.

As usual, you should work in pairs on this file and then submit it via the course website.

AVL trees are an alternative implementation of balanced binary trees. Like Red Black trees, they can be used to implement a set data structure.

```
class Set s where
empty :: s a
member :: Ord a => a -> s a -> Bool
insert :: Ord a => a -> s a -> s a
elements :: s a -> [a]
delete :: Ord a => a -> s a -> s a
```

Your job in this homework will be to implement and test the following type class instance.

```
instance Set AVL where
empty = avlEmpty
member = avlMember
insert = avlInsert
elements = avlElements
delete = avlDelete
```

## Set invariants

- Go through the lecture notes and define some general correctness properties about sets. These properties can be specialized to AVL trees here, but you should only use functions from the
`Set`

type class in their definition.

```
prop_empty :: Bool
prop_empty = undefined
```

```
prop_elements :: AVL Int -> Bool
prop_elements x = undefined
```

```
prop_insert1 :: Int -> AVL Int -> Bool
prop_insert1 x t = undefined
```

```
prop_insert2 :: Int -> AVL Int -> Bool
prop_insert2 x t = undefined
```

```
prop_delete1 :: AVL Int -> Bool
prop_delete1 t = undefined
```

```
prop_delete2 :: AVL Int -> Bool
prop_delete2 t = undefined
```

```
prop_delete3 :: AVL Int -> Int -> Property
prop_delete3 t x = undefined
```

```
set_properties :: Property
set_properties =
printTestCase "empty" prop_empty .&&.
printTestCase "elts" prop_elements .&&.
printTestCase "insert1" prop_insert1 .&&.
printTestCase "insert2" prop_insert2 .&&.
printTestCase "delete1" prop_delete1 .&&.
printTestCase "delete2" prop_delete2 .&&.
printTestCase "delete3" prop_delete3
```

## AVL tree definition & invariants

- AVL trees can be implemented with the following datatype definition. This definition is similar to that of standard binary trees, the only difference is that nodes store the height of the tree.

```
data AVL e = E -- empty tree
| N -- non-empty tree
Int -- cached height of the tree
(AVL e) -- left subtree
e -- value
(AVL e) -- right subtree
deriving Show
```

What makes a member of this datatype an `AVL`

tree is that it satisfies a specific invariants that ensure that the tree is balanced. In this problem, you'll need to define quickcheck properties for those invariants.

Of course, AVL trees must be binary search trees.

```
-- | The tree is a binary search tree
prop_bst :: AVL Int -> Bool
prop_bst = undefined
```

The height of a tree is the maximum distance from a node any leaf below it. In a wellformed AVL tree, we should be able to access this component straight off.

```
-- | The height at each node is correctly calculated.
prop_ht :: AVL Int -> Bool
prop_ht = undefined
```

```
height :: AVL e -> Int
height E = 0
height (N h _ _ _) = h
```

The balance factor corresponds to the difference in height between the left subtree and the right subtree of the node. An invariant of AVL trees is that the balance factor must be between -1 and 1.

```
-- | The balance factor at each node is between -1 and +1.
prop_balance :: AVL Int -> Bool
prop_balance = undefined
```

```
-- | Calculate the balance factor of a node
bf :: AVL e -> Int
bf E = 0
bf (N _ l _ r) = height l - height r
```

```
avl_properties :: Property
avl_properties =
printTestCase "bst" prop_bst .&&.
printTestCase "height" prop_ht .&&.
printTestCase "balance" prop_balance
```

In order to use quick check test these properties of AVL trees, we need to define what it means for two AVL trees to be equal and also define a generator for arbitrary AVL trees.

```
instance (Eq a) => Eq (AVL a) where
(==) = undefined
```

```
instance (Ord e, Arbitrary e) => Arbitrary (AVL e) where
arbitrary = undefined
```

## AVL tree operations

2a) Define the first three operations, the empty tree (and a function to determine if a tree is empty), the function to list the elements of the AVL tree, and a function for lookup up elements in the tree.

```
-- | an empty AVL tree
avlEmpty :: AVL e
avlEmpty = undefined
```

```
-- | list the elements in the tree, in order
avlElements :: AVL e -> [e]
avlElements t = undefined
```

```
-- | Determine if an element is contained within the tree
avlMember :: Ord e => e -> AVL e -> Bool
avlMember = undefined
```

## Sample trees

- Build a few particular trees that you can use as test cases later---some that obey all of the AVL invariants...

```
t1 = ...
t2 = ...
t3 = ...
```

```
t1 :: AVL Int
t1 = undefined
```

```
t2 :: AVL Int
t2 = undefined
```

```
t3 :: AVL Int
t3 = undefined
```

... and some others that do not...

```
bad1 = ...
bad2 = ...
bad3 = ...
```

```
bad1 :: AVL Int
bad1 = undefined
```

```
bad2 :: AVL Int
bad2 = undefined
```

```
bad3 :: AVL Int
bad3 = undefined
```

- Write a function
`rebalance`

that takes a tree`e`

whose root node has balance factor -2 or +2 and rearranges it to an equivalent tree with -1/0/+1 balance factors.

For this step, you will probably find it helpful to have a good diagram to refer to (such as the one on Wikipedia.) Note, though, that most explanations of AVL trees will talk about "rotating" the nodes near the root, which implies some sort of pointer manipulation. Here, we're simply rebuilding a completely new tree out of the pieces of the old one, so the notion of rotating doesn't really apply. In particular, you may find it easier to implement the "double rotations" that standard presentations of the algorithm talk about in a single step.

Even so, a diagram that shows the effect such rotations are trying to achieve is a useful guide to implementing your rearrangement. I named the variables in my patterns to match the labels in the diagram I was looking at, and this made it very much easier to write the rearranged trees correctly.

```
rebalance :: (Ord e) => AVL e -> AVL e
rebalance = undefined
```

- Write an insertion function for adding new elements to AVL trees.

You should use quickcheck to verify your implementation of `avlInsert`

.

```
-- | Insert a new element into a tree, returning a new tree
avlInsert :: (Ord e) => e -> AVL e -> AVL e
avlInsert = undefined
```

- Write a function that removes an element from a tree and rebalances the resulting tree as necessary. Again, use the properties defined above to test your implementation.

```
avlDelete :: Ord e => e -> AVL e -> AVL e
avlDelete = undefined
```

```
main :: IO ()
main = return ()
```

## News :

Welcome to CIS 552!

See the home page for basic
information about the course, the schedule for the lecture notes
and assignments, the resources for links to the required software
and online references, and the syllabus for detailed information about
the course policies.