This assignment will provide more practice with red-black trees (from Chapter 3 of the Okasaki textbook) in a purely functional language.
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.
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 vNote 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 numberAs 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 vFinally, 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 )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 Sets 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 comparableFinally, 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.
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.
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 comparableand 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.
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 | RightFirst, 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 comparableNext, 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 comparableFinally, 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.
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 Directions.
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.
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.htmlStart 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.elmIf 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.elmMake 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
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.