# HW 8 - Applicative Functors and Functional Data structures

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

```
module Main where
import Prelude hiding (zipWith,zipWith3)
```

This assignment is divided in two parts. The first part consists of some exercises on the use of applicative functors. The goal of the second part 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.

## Part 1. Applicative functors

Recall the definition of `Applicative`

:

```
class Functor f => Applicative f where
(<*>) :: f (a -> b) -> f a -> f b
pure :: a -> f a
```

Recall also that for convenience we use the infix symbol `<$>`

for `fmap`

.

```
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
```

`--(a)`

Complete the Applicative instance for the list constructor [ ].

```
instance Applicative [ ] where
pure = undefined
(<*>) = undefined
```

Use the applicative operations to redefine the transpose function for matrices as in hw1.

```
transpose :: [[a]] -> [[a]]
transpose = undefined
```

When working on list it is sometime convenient to be able to `zip`

together the elements of different lists and apply a function to the result of the zipping. This can be done by using a family of functions named zipWith, zipWith3, zipWith4...

` zipWith (+) [1,2,3] [1,0,1] = [2,2,4]`

Define zipWith and zipWith3 in terms of the applicative functor operations.

```
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith = undefined
```

```
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith3 = undefined
```

Use these operations to define the sum of two Integer matrices.

```
mSum :: [[Int]] -> [[Int]] -> [[Int]]
mSum = undefined
```

## Part 2. AVL trees

We start with the following type declaration for balanced binary search trees.

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

As before, empty trees are represented by the `E`

data constructor.

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

```
isEmpty :: AVL e -> Bool
isEmpty E = True
isEmpty _ = False
```

When we create a node, we calculate the additional information that is stored with the node. The height is the length of the longest path from this node to any leaf. The 'balance factor' is the difference in height between left subtree and the right subtree.

```
-- | create a new AVL tree with the given element and left and
-- right subtrees
node :: AVL e -> e -> AVL e -> AVL e
node l x r = N bf ht l x r where
ht = 1 + max (height l) (height r)
bf = height l - height r
```

```
-- | Access the height component of the AVL tree
height :: AVL e -> Int
height E = 0
height (N _ ht _ _ _) = ht
```

- Write a function for looking up elements in this tree.

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

- Now define a few properties that correspond to each of the AVL tree invariants. The result for these property checks should be returned in the Error monad. i.e. If the entire tree satisfies the property then the result should be
`Right ()`

. Otherwise, if some subtree violates that property then the result should be`Left s`

where`s`

is a string that describes the problem.

```
-- | The height at each node is correctly calculated.
prop_ht :: Show e => AVL e -> Either String ()
prop_ht = undefined
```

```
-- | The balance factor at each node is correctly calculated.
prop_bf :: Show e => AVL e -> Either String ()
prop_bf = undefined
```

```
-- | The balance factor at each node is between -1 and +1.
prop_balance :: Show e => AVL e -> Either String ()
prop_balance = undefined
```

```
-- | The items stored in the tree are in strictly increasing order.
prop_inorder :: (Ord e, Show e) => AVL e -> Either String ()
prop_inorder = undefined
```

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

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

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

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

- Write a function
`check`

that checks each of the invariants of AVL trees. If any of these conditions fail, the`check`

should return an error message.

```
-- | Check all invariants of an AVL tree
check :: (Ord e, Show e) => AVL e -> Either String ()
check = undefined
```

- Write a
`main`

action that uses`check`

to test all of your example trees. Make sure that the good trees are accepted silently and that the bad ones are correctly identified.

```
main :: IO ()
main = undefined
```

You can delete the calls to failing tests from `main`

once this step is finished, so that your whole program prints nothing at all when it runs.

- 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 start by writing a checking function that tests not only whether the AVL invariants hold for the result tree, but that the result tree also contains all of the elements from the original tree (plus the newly added element.)

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
```

```
checkInsert :: (Show e, Ord e) => e -> AVL e -> Either String (AVL e)
checkInsert = undefined
```

- Write a function

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

that removes an element from a tree and rebalances the resulting tree as necessary.

## 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.