# Lab 5 (100 points)

This assignment will provide more practice with red-black trees (from Chapter 3 of the Okasaki textbook) in a purely functional language.

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

#### 5.1.1 (20 points)

The first step is to implement a version of red-black trees that store key-value pairs rather than just “single” values of some `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 exposing (..)

> 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 `RedBlackTree.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 )``````

#### 5.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 `RedBlackTree.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.

#### 5.2.1 (10 points)

In order to reduce unnecessary pattern matches and comparisons, the definition of `balance` in `RedBlackTree.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

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

balanceL : Balance comparable
balanceR : Balance comparable``````

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.

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

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

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

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 : comparable -> Tree comparable -> (Tree comparable, List Dir)``

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

#### 5.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 : comparable
-> Tree comparable
-> (Tree comparable, (Balance comparable, Balance comparable))``````

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 `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 hw5
% cd hw5
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw5/RBMaps.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw5/RBTreesDel.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw5/RBTrees1.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw5/RBTrees2.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw5/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 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 "hw5 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-spr-17/repository``

# Hints

#### 5.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 comparable`.