Lab 2: The Unionized Time Cutter

Posted on October 9, 2017

Imagine you and your friends want to set times to study together. Your friends email their schedules to you, and you must find the times in which all of you are free. Of course, you could do this by hand—but now you know Haskell!

In today’s lab, you will write logic to answer such questions as, “Given these schedules, what times are we all free?” Or, “This activity requires commitment at these various times: do these conflict with my schedule?”

Continuous Time Ranges (CTRs)

The building blocks for this lab are several forms of simple, continuous time ranges:

Range	Input Syntax
⌀	`NoTime`
( − ∞, t₂)	`<2016-05-07T03:22:53`
[t₁, ∞)	`>=2017-04-20T06:35:27`
[t₁, t₂)	`2016-05-07T03:22:53-2017-04-20T06:35:27`
( − ∞, ∞)	`AllTime`

Discontinuous Time Ranges (DTRs)

Your schedule isn’t a simple block of time, however. It’s a set of blocks of time.

dtr₁ = {(−∞,t₁),[t₂, t₃),[t₄, t₅),[t₆, ∞)}

Your free time is the inverse, i.e. the set difference from the universe.

free₁ = {(−∞,∞)} \ dtr₁

And the times you can get together with your friends is the intersection of all your free times.

possibleHappyTimes = free₁ ∩ free₂ ∩ free₃ ∩ free₄

So that’s the basic idea—let’s talk about what specifically you are going to create.

Today’s Lab

You will produce a program that takes queries line-by-line and outputs the response to those queries.

$ ./Main
intersection <2016-05-07T03:22:53 >=2017-04-20T06:35:27
NoTime
intersection >=2016-05-07T03:22:53 <2017-04-20T06:35:27
2016-05-07T03:22:53-2017-04-20T06:35:27
difference <2016-05-07T03:22:53 >=2017-04-20T06:35:27
<2016-05-07T03:22:53
difference >=2016-05-07T03:22:53 <2017-04-20T06:35:27
>=2017-04-20T06:35:27
difference >=2016-05-07T03:22:53 <2017-04-20T06:35:27 2018-06-01T07:03:58-2019-08-05T17:36:33
2017-04-20T06:35:27-2018-06-01T07:03:58,>=2019-08-05T17:36:33
equal AllTime <2016-05-07T03:22:53,>=2016-05-07T03:22:53
True

There are five kinds of queries, listed below.

Query	Meaning
`intersection`	The intersection of all the given DTRs—where they all overlap. (`intersectAll`)
`union`	The union of all the given DTRs. (`unionAll`)
`difference`	Start with the first DTR and remove the others from it. (`differenceAll`)
`disjoint`	Are all given DTRs disjoint—do none of them overlap with each other? (`areAllDisjoint`)
`equal`	Are all given DTRs equivalent to each other? (`areAllEqual`)

Each query takes a list of discontinuous time ranges (DTRs). DTRs are separated by spaces, while the continuous time ranges within a DTR are separated by commas. For example, the following is two DTRs, the first consisting of three CTRs, the second only one.

<2016-05-07T03:22:53,>=2016-05-07T03:22:53,2018-06-01T07:03:58-2019-08-05T17:36:33 AllTime

DTRs do not need to be tidy. The following is a valid DTR:

AllTime,NoTime,NoTime,AllTime

Conceptually, the DTR is the union of all its CTRs. Don’t worry about cleaning it up. Overlapping and duplicate CTRs are fine within a DTR: as long as the union represents the right thing.

Just before display, there is a normalizeDTR function that will elegantly consolidate overlapping and touching CTRs.

Your Job

A considerable skeleton of code has been provided for you. Pull your repository (if you are forced to write a merge commit message, hit :x to exit vim). In the lab2 folder you will find four files. You only need to modify TimeRanges.hs and Main.hs. However, you should read through and understand even the parts of the program you do not need to modify. Reading source code is an important exercise for becoming a better programmer.

Tasks

Fill in occurrences of undefined in TimeRanges.hs. A few comments point out three places you must use foldr. However, unlike last lab you will not need to rack your brain figuring out new cases: all cases have been divided out for you, ready for you to fill in.
Fill in occurrences of undefined in Main.hs.
Fill in the main function in Main.hs to take a line of input, process it, print the result, and then wait for another line of input.

The SimpleTime.hs file should not be modified.

The Tests.hs file will not be graded; do what you like with it.

Hints

Begin and End derive Ord, which allows you to use min and max. The derived order is based on the order of the constructors given in the datatype definition: thus for all t, NegEternity < After t and Before t < Eternity. However, Begin and End are different types, so if you need to compare a Begin to an End you will need to deconstruct them and compare the Times inside each.

You will not need to add any additional cases, guards or if-then-else clauses: all necessary branches have been provided for you. Use min and max.

You may or may not need these functions:

flip :: (a -> b -> c) -> b -> a -> c
concat :: [[a]] -> [a]
concatMap :: (a -> [b]) -> [a] -> [b]
(++) :: [a] -> [a] -> [a].

Test Cases

If you want to maximize your happiness, test continuously as you write code.

We’ve provided a Tests.hs file which you should load into GHCi and use to inspect different cases as you fill them in.

$ ghci Tests.hs

The pieces of this lab build on each other, so you should test each piece as you build it.

For example, all output is normalized by normalizeDTR which depends on difference which will depend on differenceDTRCTR which will depend on differenceCTRCTR. Mess any of these up and all—yes actually all—of your output could be wrong!

Once you’ve finished, you should also test your Lab on the command line. You can compile and run your lab like so:

$ ghc Main.hs && ./Main

Here’s some sample input/output you might try. (These correspond to cases in Tests.hs.)

$ ./Main
intersection AllTime <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48 <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48
AllTime
intersection <2012-06-02T16:36:46,>=2013-01-04T05:36:49 <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,>=2014-11-18T16:03:48 <2011-04-05T15:45:30,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48
<2011-04-05T15:45:30,>=2014-11-18T16:03:48
intersection 2011-04-05T15:45:30-2012-06-02T16:36:46,2012-06-02T16:36:46-2014-11-18T16:03:48 <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49 2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48
2012-06-02T16:36:46-2013-01-04T05:36:49
intersection AllTime <2012-06-02T16:36:46,>=2013-01-04T05:36:49 2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48
2011-04-05T15:45:30-2012-06-02T16:36:46,2013-01-04T05:36:49-2014-11-18T16:03:48
intersection <2012-06-02T16:36:46,>=2013-01-04T05:36:49 <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48 NoTime
NoTime
intersection 2011-04-05T15:45:30-2012-06-02T16:36:46,2012-06-02T16:36:46-2014-11-18T16:03:48 NoTime <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48
NoTime
intersection <2012-06-02T16:36:46,>=2013-01-04T05:36:49 <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48 AllTime
<2012-06-02T16:36:46,>=2013-01-04T05:36:49
intersection 2011-04-05T15:45:30-2012-06-02T16:36:46,2012-06-02T16:36:46-2014-11-18T16:03:48 AllTime <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48
2011-04-05T15:45:30-2014-11-18T16:03:48
union AllTime <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49 <2011-04-05T15:45:30,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48
AllTime
difference <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48 <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48
NoTime
difference <2011-04-05T15:45:30,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48 <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,>=2014-11-18T16:03:48
2013-01-04T05:36:49-2014-11-18T16:03:48
difference 2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48 <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49
>=2013-01-04T05:36:49
difference NoTime <2011-04-05T15:45:30,2011-04-05T15:45:30-2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48,>=2014-11-18T16:03:48
NoTime
difference AllTime 2011-04-05T15:45:30-2012-06-02T16:36:46,2013-01-04T05:36:49-2014-11-18T16:03:48,>=2014-11-18T16:03:48
<2011-04-05T15:45:30,2012-06-02T16:36:46-2013-01-04T05:36:49
difference AllTime AllTime
NoTime
difference <2014-11-18T16:03:48 2012-06-02T16:36:46-2013-01-04T05:36:49 <2011-04-05T15:45:30
2011-04-05T15:45:30-2012-06-02T16:36:46,2013-01-04T05:36:49-2014-11-18T16:03:48
difference <2014-11-18T16:03:48 2012-06-02T16:36:46-2013-01-04T05:36:49,2013-01-04T05:36:49-2014-11-18T16:03:48 <2011-04-05T15:45:30
2011-04-05T15:45:30-2012-06-02T16:36:46
difference AllTime <2011-04-05T15:45:30 >=2014-11-18T16:03:48
2011-04-05T15:45:30-2014-11-18T16:03:48
difference AllTime >=2011-04-05T15:45:30 <2014-11-18T16:03:48
NoTime
difference AllTime NoTime NoTime
AllTime
disjoint AllTime NoTime NoTime
True
disjoint AllTime NoTime AllTime
False
disjoint <2011-04-05T15:45:30 2011-04-05T15:45:30-2012-06-02T16:36:46 2012-06-02T16:36:46-2013-01-04T05:36:49 2013-01-04T05:36:49-2014-11-18T16:03:48 >=2014-11-18T16:03:48
True
disjoint <2011-04-05T15:45:30 2011-04-05T15:45:30-2012-06-02T16:36:46 2012-06-02T16:36:46-2013-01-04T05:36:49 2013-01-04T05:36:49-2014-11-18T16:03:48 <2014-11-18T16:03:48
False
disjoint 2012-06-02T16:36:46-2013-01-04T05:36:49 2011-04-05T15:45:30-2012-06-02T16:36:46 2012-06-02T16:36:46-2014-11-18T16:03:48
False
disjoint 2011-04-05T15:45:30-2012-06-02T16:36:46 2012-06-02T16:36:46-2013-01-04T05:36:49 2012-06-02T16:36:46-2014-11-18T16:03:48
False
disjoint 2011-04-05T15:45:30-2012-06-02T16:36:46,2013-01-04T05:36:49-2014-11-18T16:03:48 <2011-04-05T15:45:30,2012-06-02T16:36:46-2013-01-04T05:36:49 >=2014-11-18T16:03:48
True
equal AllTime AllTime,AllTime NoTime
False
equal AllTime AllTime,AllTime AllTime
True
equal AllTime <2011-04-05T15:45:30,>=2011-04-05T15:45:30 <2012-06-02T16:36:46,2012-06-02T16:36:46-2013-01-04T05:36:49,>=2013-01-04T05:36:49
True
equal 2011-04-05T15:45:30-2014-11-18T16:03:48 2012-06-02T16:36:46-2014-11-18T16:03:48,2011-04-05T15:45:30-2012-06-02T16:36:46 2011-04-05T15:45:30-2012-06-02T16:36:46,2012-06-02T16:36:46-2013-01-04T05:36:49,2013-01-04T05:36:49-2014-11-18T16:03:48
True
equal 2011-04-05T15:45:30-2014-11-18T16:03:48 2012-06-02T16:36:46-2014-11-18T16:03:48,2011-04-05T15:45:30-2012-06-02T16:36:46 2011-04-05T15:45:30-2012-06-02T16:36:46,2012-06-02T16:36:46-2013-01-04T05:36:49
False
equal <2014-11-18T16:03:48 <2013-01-04T05:36:49,2012-06-02T16:36:46-2014-11-18T16:03:48 <2011-04-05T15:45:30,<2012-06-02T16:36:46,2012-06-02T16:36:46-2014-11-18T16:03:48
True
equal >=2011-04-05T15:45:30 >=2012-06-02T16:36:46 >=2011-04-05T15:45:30,>=2012-06-02T16:36:46
False
quit

Submitting

As usual, push before 11pm Thursday and check Gitlab to verify that you pushed everything. Email your lab TA if you would like to use one of your extensions.

Grading

Make sure your lab compiles (ghc Main.hs succeeds).

The vast majority of your grade will be automated tests for correctness.

~~Style will only be graded if we are able to return Lab 1 feedback in a timely manner (i.e. 36 hours or more before the Lab 2 deadline).~~ Lab 2 will not be graded on style. Regardless, do make a habit of cleanliness. In the real world, you may write a line of code once, but you will likely read it 5, 10, or 100 times later on.

Style Guidelines

Understandable names. Naming is one of the two hard problems in computer science. Short names are fine for common uses: i for index, x:xs for generic array elements, n for generic number, c for counter, etc. Abbreviations are fine too, but the rule is a reader should know the meaning of the thing just by reading its name.
Type definitions on all top-level functions.
No commented-out code.
Avoid too many long lines (>100 characters). A couple long lines are okay.
Parentheses in the correct place: sqrt (5 * 2) not sqrt(5 * 2).
Avoid unnecessary code, e.g. pattern match cases that could be combined, or deconstructing a value and then just putting it back together.
No long, hard-to-follow, or deeply nested functions that should be broken up. Take advantage of where and let.
Comments explaining any hard-to-understand logic, e.g. what does this helper function do?
Tasteful use of whitespace for vertical alignment.
η-reduction is not necessary, but can be tasteful.