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.
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 Arrays.
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 TreeA heap will be represented as a complete binary Tree along with its size (the number of Nodes in the Tree):
type alias InternalHeap = (Int, Tree)
type Heap = WrapHeap InternalHeapYou will implement all operations of the min-heap abstraction except for merge.
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) + 2To 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 << fooFor 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.DirFirst, implement the following Heap operations:
empty : Heap
isEmpty : Heap -> Bool
findMin : Heap -> Maybe IntNext, implement the insert operation:
insert : Int -> Heap -> HeapYou may consider using the helper functions above, but you are free to implement insert however you wish.
Spoiler Alert: There are more hints below.
Finally, implement the deleteMin operation:
deleteMin : Heap -> Maybe HeapAgain, 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.
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 Ints (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 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 (..)
> 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 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 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 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.
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 -> Treeand 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.
type alias Balance = Color -> Tree -> Int -> Tree -> Tree
balanceLL : Balance
balanceLR : Balance
balanceRL : Balance
balanceRR : BalanceNext, 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 -> BalanceFinally, 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.
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 : 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.
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.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 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.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 THeaps.elm
% 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 "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
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 -> TreeOne 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 -> TreeHint: 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.