Lab 2: Interval Algebra

Posted on October 7, 2021

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 at 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 half-open intervals:

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

In actuality, all intervals we will use are of the from [t₁, t₂), and we will have implicit lower and upper bounds playing the roles of − ∞ and ∞. Likewise, the empty interval ⌀ is equivalent to the case that t₁ ≥ t₂.

Interval Sets

Your schedule isn’t a simple block of time, however. It’s a set of blocks of time, which we will call an interval set.

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 responses 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 just learned about type classes, we will implement our intervals so that they work for any instance of the Ord and Bounded classes (more on the Bounded class below). So we will be able to test 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 have to worry about cleaning up interval sets when you are working on the lab (except in one particular case, noted in the code). 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 three files. You only need to modify Intervals.hs and Main.hs, but 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. Also note the comment for differenceIntervals, which says that there can be no occurrences of empty intervals in the output of that function.
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

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].

The `Bounded` Type Class

An instance of the Bounded type class has access to two values minBound and maxBound, which you can think of as − ∞ and ∞ above. As it pertains to this lab, we use minBound and maxBound for the “unbounded” sides of the intervals, .e.g., All is represented by the interval Range minBound maxBound.

Int is an instance of this class, and these values correspond to the smallest and largest integer values that you can use in a Haskell program (and whose size corresponds to the amount of space used to store Ints). Time is also an instance of this class, which is why we can use the functions written in Interval.hs for this lab. To be clear, there is nothing in Haskell which guarantees that these values are in fact the smallest or largest values of a given type. They are just named instances. It is up to the programmer to choose reasonable values for minBound and maxBound.

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 with than Times. That said, 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

We have also included two files test_inputs.txt and test_expectation.txt which include the above tests separated by input and output. You can simultaneously test all of them by running

$ ghc Main.hs && ./Main < test_inputs.txt

and you can check all the outputs against their expected values by running

$ ghc Main.hs && ./Main < test_inputs.txt | diff -y test_expectation.txt -

Submitting

As usual, push before 4:59pm Tuesday 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.