# Homework 4

This assignment will provide more opportunities to manipulate complete binary trees and red-black trees (from Chapter 3 of the Okasaki textbook) in a purely functional language.

## Problem 0: Heaps as Complete Binary Trees

We saw how to implement min-heaps using the `Array` library in the Heaps lecture. Now, you'll implement the same complete binary tree approach using trees directly, rather than `Array`s.

Download the skeleton file `THeaps.elm` and use it as a starting point for this problem. Look for all occurrences of `TODO` in comments, which point out where you should implement your solutions.

We'll use the same definition of `Tree` from before:

``type Tree = Empty | Node Int Tree Tree``

A heap will be represented as a complete binary `Tree` along with its size (the number of `Node`s in the `Tree`):

``````type alias InternalHeap = (Int, Tree)

type Heap = WrapHeap InternalHeap``````

You will implement all operations of the min-heap abstraction except for `merge`.

### Helper Functions

Recall the modular arithmetic used to traverse between parent and child nodes:

``````parentIndex i = (i-1) // 2

leftIndex i   = (2*i) + 1
rightIndex i  = (2*i) + 2``````

To help factor the algorithms below, we first define the notion of a path from the root of a `Tree` to the subtree at position `i` (according to the 0-based, breadth-first indexing scheme from Heaps):

``````type Dir = Left | Right

pathTo : Int -> List Dir
pathTo =
let foo i =
if i == 0 then []
else if i `rem` 2 == 1 then Left :: foo (parentIndex i)
else Right :: foo (parentIndex i)
in
List.reverse << foo``````

For example:

``````> import THeaps exposing (..)

> pathTo 0
[] : List THeaps.Dir

> pathTo 1
[Left] : List THeaps.Dir

> pathTo 2
[Right] : List THeaps.Dir

> pathTo 3
[Left,Left] : List THeaps.Dir

> pathTo 10
[Left,Right,Right] : List THeaps.Dir

> pathTo 58
[Right,Right,Left,Right,Right] : List THeaps.Dir``````

#### 4.0.1 --- Basic Operations (10 points)

First, implement the following `Heap` operations:

``````empty   : Heap
isEmpty : Heap -> Bool
findMin : Heap -> Maybe Int``````

#### 4.0.2 --- Insertion (20 points)

Next, implement the `insert` operation:

``insert : Int -> Heap -> Heap``

You may consider using the helper functions above, but you are free to implement `insert` however you wish.

Spoiler Alert: There are more hints below.

#### 4.0.3 --- Deletion (20 points)

Finally, implement the `deleteMin` operation:

``deleteMin : Heap -> Maybe Heap``

Again, you may consider using the helper functions above, but you are free to implement `insert` however you wish.

Spoiler Alert: There are more hints below.

## Problem 1: "Deleting" from Red-Black Trees

In this problem, we will simulate deletions from red-black trees without actually removing elements.

Download the skeleton files `RBMaps.elm` and `RBTreesDel.elm`, and use them as a starting point for this problem. Look for all occurrences of `TODO` in comments, which point out where you should implement your solutions.

#### 4.1.1 (20 points)

The first step is to implement a version of red-black trees that store key-value pairs rather than just `Int`s (or single values of some other `comparable` type). We will call these "red-black maps" because each node maps a key (of some `comparable` type) to a value (of type `v`).

``````type Color = R | B
type Map comparable v
= E
| T Color (Map comparable v) (comparable, v) (Map comparable v)``````

Fill in the module `RBMaps.elm` with the implementation of the following operations:

``````empty  : Map comparable v
get    : comparable -> Map comparable v -> Maybe v
insert : comparable -> v -> Map comparable v -> Map comparable v``````

Note that `get` is analogous to `member` for red-black trees, except that now a value is (maybe) returned.

When called with a key `k` that is already bound in `m`, the new map that results from `insert k v m` should bind `k` to the new value `v`. For example:

``````> import RBMaps (..)

> m = empty |> insert "a" 1 |> insert "b" 2
T B E ("a",1) (T R E ("b",2) E) : RBMaps.Map String number

> get "b" m
Just 2 : Maybe.Maybe number

> get "c" m
Nothing : Maybe.Maybe number

> get "c" (insert "c" 3 m)
Just 3 : Maybe.Maybe number

> get "b" (insert "b" 3 m)
Just 3 : Maybe.Maybe number``````

As in `RedBlackTrees.elm`, your implementation of `insert` should be defined in terms of two helper functions:

``````ins : comparable -> v -> Map comparable v -> Map comparable v

balance : Color
-> Map comparable v -> (comparable, v) -> Map comparable v
-> Map comparable v``````

Finally, implement a `toList` function that returns the `List` of the key-value pairs stored in a `Map`.

``toList : Map comparable v -> List (comparable, v)``

The pairs should be ordered according to an in-order traversal of the tree. For example:

``````> toList m
[("a",1),("b",2)] : List ( String, number )``````

#### 4.1.2 (20 points)

The next step is to define a version of red-black trees, called `RBTreesDel.elm`, that uses an `RBMap` to associate each element with a `Bool` that denotes whether the element is in the set. The representation of `Set`s is as follows.

``type Set comparable = Set (Map.Map comparable Bool)``

By using the `Map` representation, we will simulate deleting an element by updating its binding to `False`. In other words, deleting an element of `Set` does not actually remove it from the `Map`; rather, it just updates its `Bool` binding. Deleting an element for which there is no `Bool` binding should not alter the `Set`.

Implement the following operations, so that `member`, `insert`, and `delete` all run in O(log n) time, where n is the size of the underlying `Map`, that is, the number of elements mapped either to `True` or `False`.

``````empty  : Set comparable
member : comparable -> Set comparable -> Bool
insert : comparable -> Set comparable -> Set comparable
delete : comparable -> Set comparable -> Set comparable``````

Finally, implement `size` to return a pair of `Ints`, where the first is the number of elements mapped to `True` and the second is the number of elements mapped to `False`. Your implementation should run in O(n) time.

``size : Set comparable -> (Int, Int)``

For sets of values where elements are deleted relatively infrequently, or in situations where deleted elements are likely to be added again later, this approach of simulating deletions may be acceptable.

## Problem 2: Optimizing the Balance Function

This problem is based on Exercise 3.10 from the Okasaki textbook.

Download the skeleton files `RBTrees1.elm`, `RBTrees2.elm`, and `RBTrees3.elm`, and use them as a starting point for this problem. Look for all occurrences of `TODO` in comments, which point out where you should implement your solutions.

While you are developing and testing your code, you will need to place `RedBlackTrees.elm` in the same directory as your solution (but you will not submit it).

You may wish to use contracts while you develop and test your solutions. If you do, make sure to "turn them off" in your final submissions.

#### 4.2.1 (10 points)

In order to reduce unnecessary pattern matches and comparisons, the definition of `balance` in `RedBlackTrees.elm` can be split into different cases depending on whether left or right subtrees are being balanced.

In `RBTrees1.elm`, split `balance` into two different separate balancing functions

``````balanceL : Color -> Tree -> Int -> Tree -> Tree
balanceR : Color -> Tree -> Int -> Tree -> Tree``````

and define `ins` to use `balanceL` when recursing into the left subtree and use `balanceR` when recursing into the right subtree. The functions `balanceL` and `balanceR` should each check only those tree configurations that might be observed at run-time.

#### 4.2.2 (20 points)

The previous optimization can be be extended further, so that the original `balance` function can be broken into four distinct cases rather than two, each of which performs only those pattern matches and comparisons which might possibly result in a rebalancing.

The idea is for `ins` to return, in addition to a new `Tree`, the next two "steps" in the search path traversed by the recursive call. This information is used by `ins` to decide which of the four balancing functions to call.

In `RBTrees2.elm`, we define the type `Dir` to describe `Left` or `Right` steps along a search path.

``type Dir = Left | Right``

First, define the following four balance functions to handle each of the four distinct cases from the original `balance` function.

``````type alias Balance = Color -> Tree -> Int -> Tree -> Tree

balanceLL : Balance
balanceLR : Balance
balanceRL : Balance
balanceRR : Balance``````

Next, define `chooseBalance` to choose from among these `Balance` functions based on the next two steps (stored in a `List`) in the search path.

``chooseBalance : List Dir -> Balance``

Finally, define `ins` to return a `List` containing (at most) the next two steps traversed in the search path. The results from a previous call should be used to determined which `Balance` function to call.

``ins : Int -> Tree -> (Tree, List Dir)``

You will also need to redefine `insert` in order to make use of this updated signature for `ins`.

#### 4.2.3 (30 points)

Although the way we factored the optimization in the previous subproblem is intuitive and readable, it still involves unnecessary pattern matching and comparisons to manipulate the `List` of previous `Dir`ections.

In `RBTrees3.elm`, you will refactor your solution from the previous subproblem as follows. Rather than returning a `List Dir`, define `ins` to return a pair of `Balance` functions to choose from.

``ins : Int -> Tree -> (Tree, (Balance, Balance))``

Your task is to figure out which `Balance` functions to return in each case, and how to choose from among the `Balance` functions returned by a recursive call to `ins`. The net effect should be the same as the previous approach that used a `List` of `Left` and `Right` steps.

Spoiler Alert: There are some hints below.

# Grading and Submission Instructions

Submit the files `THeaps.elm`, `RBMaps.elm`, `RBTreesDel.elm`, `RBTrees1.elm`, `RBTrees2.elm`, and `RBTrees3.elm`, updated with your changes. You are free to modify these files as you wish, as long as you do not change any of the required type signatures.

Your solution will be graded using a combination of automated grading scripts and manual review. It is a good idea for you to design some test cases of your own to exercise more sample behaviors than just the ones provided in the writeup. We also reserve the right to take into account the organization and style of your code when assigning grades.

If you are not able to finish all parts of the assignment, make sure that all of your submitted files compile successfully. If not, you risk getting zero points for the assignment. In particular, for each file `Foo.elm`, make sure that it can be loaded into the Elm REPL

``````% elm-repl
> import Foo
>``````

and that it can be compiled to a standalone HTML file:

``````% elm-make Foo.elm --output=Foo.html
Successfully generated Foo.html``````

### Submitting Your Code

Start by navigating to the folder where you checked out your repo. Next, create a subfolder for this assignment and populate it with the skeleton code:

``````% svn mkdir hw4
% cd hw4
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw4/THeaps.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw4/RBMaps.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw4/RBTreesDel.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw4/RBTrees1.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw4/RBTrees2.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw4/RBTrees3.elm``````

If `wget` or a similar tool (such as `curl`) is not available on your machine, download and save the skeleton files provided above in some other way. Then add only these files to your repo:

``````% svn add THeaps.elm
% svn add RBMaps.elm
% svn add RBTreesDel.elm
% svn add RBTrees1.elm
% svn add RBTrees2.elm
% svn add RBTrees3.elm``````

Make sure you choose the same exact names for directories and files that you create. Once you are ready to submit:

``% svn commit -m "hw4 submission"``

You can resubmit as many times as you wish, and we will grade the most recent versions submitted. Late days, if any, will be computed based on your submission times.

As a sanity check, you can visit the Web-based frontend for your repository to make sure that you have submitted your files as intended:

``https://phoenixforge.cs.uchicago.edu/projects/USER-cs223-win-16/repository``

# Hints

#### 4.0.2 and 4.0.3

One option for `insert` is to start with the following and define the helper function `insertAndBubbleUp`.

``````insert x (WrapHeap (n, t)) =
if n == 0
then WrapHeap (1, Node x Empty Empty)
else WrapHeap (1 + n, insertAndBubbleUp x (pathTo (parentIndex n)) t)

insertAndBubbleUp : Int -> List Dir -> Tree -> Tree``````

One option for `deleteMin` is to start with the following and define the helper functions `removeElement` and `bubbleDown`. (NOTE: I've renamed an identifier below from `minElement` to `lastElement` to more accurately represent its purpose.)

``````deleteMin (WrapHeap (n, t)) =
if n == 0 then Nothing
else if n == 1 then Just empty
else
let (lastElement, t') = removeElement (pathTo (n-1)) t in
case t' of
Empty -> Debug.crash "deleteMin: impossible"
Node _ left right ->
Just (WrapHeap (n - 1, bubbleDown (Node lastElement left right)))

removeElement : List Dir -> Tree -> (Int, Tree)

bubbleDown : Tree -> Tree``````

#### 4.2.3

Hint: Look for a pattern that leads to the appropriate `Balance` function (i.e. `balanceLL`, `balanceLR`, `balanceRL`, or `balanceRR`) being (a) in the first component of the pair returned by the recursive call when recursing on the left subtree and (b) being in the second component of the pair returned by the recursive call when recursing on the right. It may be helpful to draw out a couple example search paths and the flow of values from recursive calls up to their parent nodes.

Hint: Notice that the data constructor `T` has type `Balance`.