Lab 2: Interval Arithmetic

Posted on October 14, 2019

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?”

Intervals

The building blocks for this task are several forms of simple, continuous intervals:

Range	Input Syntax
⌀	`Empty`
( − ∞, t₂)	`<t2`
[t₁, ∞)	`>=t1`
[t₁, t₂)	`t1<=_<t2`
( − ∞, ∞)	`All`

Interval Sets

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

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

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

free = {( − ∞, ∞)} \ schedule

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. The endpoints of the intervals will be times of day, according to type called Time that we have implemented for you in SimpleTime.hs.

$ ./Main
intersection <2016-05-07T03:22:53 >=2017-04-20T06:35:27
Empty
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 All <2016-05-07T03:22:53,>=2016-05-07T03:22:53
True

However, since we have just learned about type classes, we will implement our intervals so that they work for any instance of the Ord class. So we will be able to run tests using Ints.

intersection <0 >=1
Empty
intersection >=0 <1
0<=_<1
difference <0 >=1
<0
difference >=0 <1
>=1
difference >=0 <1 2<=_<3
1<=_<2,>=3
equal All <1,>=0
True

There are five kinds of queries, listed below.

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

Each query takes a list of interval sets. Interval sets are separated by spaces, while intervals within an interval set are separated by commas (no spaces).

Note. Even though we will think of interval sets as disjoint, they do not need to be presented as such. The following is valid:

All,Empty,Empty,All

Conceptually, an interval set is the union of all its intervals. You don’t worry about cleaning up interval sets when you are working on the lab. Overlapping and duplicate intervals are fine within an interval set: as long as the union represents the right thing. Just before display, there is a normalizeIS function that will elegantly consolidate overlapping and touching intervals.

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 lab02 folder you will find four files. You only need to modify Intervals.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 Intervals.hs. A few comments point out three places you must use foldr.
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 (this part should be very simple, but it will give you an opportunity to start working a bit with IO).

The SimpleTime.hs file should not be modified.

Hints

Endpoint derives 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, MIN < E t < 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].

Testing

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

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 normalizeIS which depends on difference which will depend on differenceIS which will depend on differenceIntervals, which—hint—will most likely depend on other previous defined functions. Mess any of these up and all—yes actually all—of your output could be wrong!

But because we are writing intervals for any instance of Ord we can test by using Ints! which will be significantly easier to work work with than Times. That said, note that if you load Intervals.hs into ghci and use read, you have to specify the type of the output. Otherwise, Haskell won’t know how to read the unspecified instance of Ord!

*Intervals> read "<2"
*** Exception: Prelude.read: no parse
*Intervals> read "<2" :: Interval Int
<2
*Intervals>

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

To simplify testing on the command line, there is a line near the top of Main.hs which defines the type used by Main for endpoints.

type EndpointType = Time

You can change this to Int to make checking the output easier. Make sure to change this back to Time when you submit! After you have tested on Ints, here are some sample input/output you might try for the final version of the program.

$ ./Main
intersection All <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
All
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 All <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 Empty
Empty
intersection 2011-04-05T15:45:30<=_<2012-06-02T16:36:46,2012-06-02T16:36:46<=_<2014-11-18T16:03:48 Empty <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
Empty
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 All
<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 All <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 All <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
All
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
Empty
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 Empty <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
Empty
difference All 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 All All
Empty
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 All <2011-04-05T15:45:30 >=2014-11-18T16:03:48
2011-04-05T15:45:30<=_<2014-11-18T16:03:48
difference All >=2011-04-05T15:45:30 <2014-11-18T16:03:48
Empty
difference All Empty Empty
All
disjoint All Empty Empty
True
disjoint All Empty All
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 All All,All Empty
False
equal All All,All All
True
equal All <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 11:59pm Thursday and check Gitlab to verify that you pushed everything. Again, if you changed EndpointType in Main.hs for testing, make sure to change it back to Time for your submission!

Grading

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

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

Lab 2 will not be graded on style (though Lab 3 will). Regardless, do make a habit of cleanliness. Readability matters: 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.