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


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

Range Input Syntax
( − ∞, t2) <t2
[t1, ∞) >=t1
[t1, t2) t1<=_<t2
( − ∞, ∞) All

Interval Sets

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

schedule = {( − ∞, t1), [t2, t3), [t4, t5), [t6, ∞)}

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 = free1 ∩ free2 ∩ free3 ∩ free4

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
intersection >=2016-05-07T03:22:53 <2017-04-20T06:35:27
difference <2016-05-07T03:22:53 >=2017-04-20T06:35:27
difference >=2016-05-07T03:22:53 <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
equal All <2016-05-07T03:22:53,>=2016-05-07T03:22:53

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
intersection >=0 <1
difference <0 >=1
difference >=0 <1
difference >=0 <1 2<=_<3
equal All <1,>=0

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:


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.


  1. Fill in occurrences of undefined in Intervals.hs. A few comments point out three places you must use foldr.
  2. Fill in occurrences of undefined in Main.hs.
  3. 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.


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:


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: no parse
*Intervals> read "<2" :: Interval Int

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
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
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
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
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
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
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
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
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
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
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
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
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
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
difference All All
difference <2014-11-18T16:03:48 2012-06-02T16:36:46<=_<2013-01-04T05:36:49 <2011-04-05T15:45:30
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
difference All <2011-04-05T15:45:30 >=2014-11-18T16:03:48
difference All >=2011-04-05T15:45:30 <2014-11-18T16:03:48
difference All Empty Empty
disjoint All Empty Empty
disjoint All Empty All
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
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
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
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
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
equal All All,All Empty
equal All All,All All
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
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
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
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
equal >=2011-04-05T15:45:30 >=2012-06-02T16:36:46 >=2011-04-05T15:45:30,>=2012-06-02T16:36:46


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!


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