| Safe Haskell | None |
|---|
HW02
Contents
Description
Second assignment for IB016, semester spring 2019.
Task overview
Your task is to implement an extended rope data structure and tests for it.
Rope data structure is used to efficiently store and manipulate very long strings. For example, a text editor may use a rope to represent the text. A rope provides efficient insertion, deletion and random access.
Manipulation with long strings in an ordinary list is not always the most effective way. For example, if you want to insert a substring into the string, the time complexity is linear with regards to the length of the string. The rope data structure allows us to do this more efficiently on average.
In ropes, substrings of long string are saved in leaf nodes. Each leaf node holds the length of a substring too. Each non-leaf node holds sum of the lengths of all the leaves in its left subtree ("weight" of node). For example:
This is a rope, which stores the string "Hello_World!".
Your task is to implement basic operations on the extended rope data structure (insertion, deletion, searching) as well as some tests for it. The extended rope data structure stores any list of any type.
You are given the definition of the data structure itself (you are not allowed to change it!). You can find descriptions of the required operations below.
As for the tests, writing an instance of Arbitrary for Rope is quite
tedious, as it requires generating all sorts of valid ropes. Therefore we have
written an instance of Arbitrary for Rope for you to use in the tests. However,
there is an alternative approach to testing a data structure defined in terms of
their operations: Generating a random sequence of operations and comparing the
results with a reference implementation. Write a generator for such sequences
(ActionSeq) and at least the test comparing ropes built using this sequence with
a list build from this sequence. Furthermore, write your own tests for the rest
of the functionality – all functions should be covered by tests, these test
should be written is such a way that it is likely that errors will be discovered
in the simplest possible instances. Furthermore, from the test failures it should be
clear what operation failed and what were the inputs. These tests will be a part
of your evaluation.
You should name all tests with the prop_ prefix. You can then execute them
using the runTests function we have defined for you.
Assignment summary
- Implement specified operations on the
Ropedata structure (5 points). - Implement
Arbitraryinstance forAction(2 points). - Implement your test utilities (
replayRope,replayList), theprop_compare_with_listtest, and your own tests (3 points).
Modules and packages
You can use any modules from the base package, as well as the data-default-class, and the QuickCheck packages. If you wish, you can also use Unicode syntax from base-unicode-symbols. If you want to use any other module or package, please ask in the discussion forum before use.
General Notes & Tips
- Please be sure that you calculate weights correctly.
- Don't forget to check that every tree leaf is
Leaf(everyNodenode has to have at least one descendant). - Test all functions and their combinations.
- Keep in mind that rope should have fast modification times, therefore you should either make minimal changes to its structure in insert/delete, or balance it and keep the amortized complexity in mind
Synopsis
- data Rope a
- index :: Int -> Rope a -> Maybe a
- empty :: Rope a -> Bool
- size :: Rope a -> Int
- valid :: Rope a -> Bool
- validWithRate :: Int -> Rope a -> Bool
- insert :: Int -> [a] -> Rope a -> Rope a
- delete :: Int -> Int -> Rope a -> Rope a
- fromList :: [a] -> Rope a
- fromListWithRate :: Int -> [a] -> Rope a
- toList :: Rope a -> [a]
- data Action a
- newtype ActionSeq a = ActionSeq {}
- replayRope :: ActionSeq a -> Rope a
- replayList :: ActionSeq a -> [a]
- prop_compare_with_list :: ActionSeq Char -> Property
- runTests :: IO Bool
Documentation
A rope structure, which stores a list of values of type a.
You are not allowed to change this definition.
Check if the given rope is valid: weights are calculated correctly and
every Node has at least one descendant.
validWithRate :: Int -> Rope a -> Bool #
Check if the rope is valid and if the weight of each leaf node is at most the given value (rate).
Arguments
| :: Int | beginning position to remove |
| -> Int | length of the substring to remove |
| -> Rope a | given rope |
| -> Rope a | result |
Removes a sublist. If the given position is invalid (out of range), then the given rope doesn't change. If the position is valid, but the range ends after the end of the rope, removes all elements from the position to the end.
fromListWithRate :: Int -> [a] -> Rope a #
Create a rope that stores the given list and the weight of each leaf node is at most the given value (rate). The rope should be balanced.
Tests
This data type describes actions over Rope in such a way that these
actions can be generated by QuickCheck.
Instances
| Show a => Show (Action a) # | |
| Arbitrary a => Arbitrary (Action a) # | Write an instance for generation of |
A sequence of actions for Arbitrary instance.
replayRope :: ActionSeq a -> Rope a #
Produce a Rope that corresponds to the given sequence of actions.
replayList :: ActionSeq a -> [a] #
Produce a list that corresponds to the given sequence of actions.
You are not allowed to use the functions that you implemented for the Rope
structure here, because you want to test your function against a trustworthy
implementation.
prop_compare_with_list :: ActionSeq Char -> Property #
Write a property that produces a Rope and a list from the given sequence
and compares them if they hold exactly the same data. Try to write this in
such a way that it has nice error messages.