Interval Algebra

PA 3 — Due: Fri Oct 20 11pm CT

Recall the academic integrity policy: turn in your own work and cite all sources.
The following is adapted from an assignment originally written by Brian Hempel.

Imagine you and your friends want to set times to work on problem sets 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 you’re a programmer, equipped to wreak havoc on the world!

In this assignment, you will implement 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`

Internally, we will represent all intervals in the form [t₁, t₂), with 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.

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

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

freeTimes = {(−∞,∞)} \ busyTimes

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

possibleHappyTimes = freeTime₁ ∩ freeTime₂ ∩ freeTime₃ ∩ freeTime₄

What is Time Anyway?

Normally, time is represented as something like the number of milliseconds since the dawn of time, often agreed to be midnight on January 1, 1970. For the purposes of our programming assignment, it doesn’t matter what time representation we use. In fact, we don’t even need to work with times at all!

Making use of type classes, we will implement intervals to work for any type that is Ordered and Bounded (more on the Bounded class below). Then, to make development and testing easier, we will simply use Ints for the rest of this assignment.

If you hope to use your program to schedule those happy problem-set group sessions, after you finish the assignment go on and connect your implementation to some particular representation of time — which will need instances for Ord, Bounded, Read, and Show… and a nice GUI to rival all those “when is good” apps.

Queries

Your program will accept queries line-by-line and output responses to those queries. For example:

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, each of which takes a list of interval sets.

Input Query	Meaning (and name of the function that implements it)
`intersection`	Intersection of given interval sets. Where do they overlap? (`intersectionAll`)
`union`	Union of given interval sets. (`unionAll`)
`difference`	Start with the first interval set, remove the others from it. (`differenceAll`)
`disjoint`	Are the interval sets disjoint? Do none of them overlap? (`areAllDisjoint`)
`equal`	Are the interval sets equivalent to each other? (`areAllEqual`)

String Representations

In the string representations, interval sets are separated by spaces, whereas intervals within an interval set are separated by commas (no spaces).

(Lack of) Canonical Representations

Even though we will think of interval sets as disjoint, they do not need to be represented (internally) or presented (externally) as such. For example, the following interval set 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, except in one particular case, noted in the code. Overlapping and duplicate intervals are fine, as long as the union represents the right thing. Just before display, there is a normalizeIS function that will elegantly consolidate overlapping and adjacent intervals.

Starter Code

See Ed for the GitHub Classroom assignment link, which will create a UChicago-PL repository like

https://github.com/UChicago-PL/cs223-fa23-pa-3-interval-algebra-USERNAME

Tasks

Your repository is set up with skeleton code factored across several files. Pay heed to the comments in these files, which may contain additional information or requirements.

Fill in occurrences of undefined in Interval.hs.
Fill in occurrences of undefined and TODO in Main.hs.

Do not change the type signature of any function that is provided.

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

Bounded types define two values minBound and maxBound, which you can think of as − ∞ and ∞ above. As it pertains to this assignment, we use minBound and maxBound for the “unbounded” sides of the intervals — for example, 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).

As a reminder, 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.

The `Read` Type Class

The Read class defines a funny-looking function…

readsPrec :: Read a => Int -> String -> [(a, String)]

that is used to implement:

read :: Read a => a -> String

You do not have to worry too much about readsPrec; the starter code leaves just a few undefined base cases to fill in with appropriate Interval a values.

Testing

If you want to maximize happy times, test continuously as you code.

The pieces of this assignment build on each other, so you should test each piece as you go. 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 previously defined functions. Mess any of these up and all—yes actually all—of your output could be wrong!

So, test individual helper functions. For example:

> intersectIntervals (read "<0") (read ">=1") :: Interval Int
Empty

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!

> read "<2"
*** Exception: Prelude.read: no parse
> read "<2" :: Interval Int
<2
> read @(Interval Int) "<2"
<2
>

Once you’ve finished, you should also test on the command line:

$ ghc Main.hs && ./Main

Sample Interactions

Here are additional sample I/O interactions to test for the final version of the program.

$ ./Main
intersection All <1,1<=_<3,2<=_<4,>=4 <1,1<=_<3,2<=_<4,>=4
All
intersection <2,>=3 <1,1<=_<3,>=4 <1,2<=_<4,>=4
<1,>=4
intersection 1<=_<2,2<=_<4 <1,1<=_<3 2<=_<4,>=4
2<=_<3
intersection All <2,>=3 1<=_<3,2<=_<4
1<=_<2,3<=_<4
intersection <2,>=3 <1,1<=_<3,2<=_<4,>=4 Empty
Empty
intersection 1<=_<2,2<=_<4 Empty <1,1<=_<3,2<=_<4,>=4
Empty
intersection <2,>=3 <1,1<=_<3,2<=_<4,>=4 All
<2,>=3
intersection 1<=_<2,2<=_<4 All <1,1<=_<3,2<=_<4,>=4
1<=_<4
union All <1,1<=_<3 <1,2<=_<4,>=4
All
difference <1,1<=_<3,2<=_<4,>=4 <1,1<=_<3,2<=_<4,>=4
Empty
difference <1,2<=_<4,>=4 <1,1<=_<3,>=4
3<=_<4
difference 2<=_<4,>=4 <1,1<=_<3
>=3
difference Empty <1,1<=_<3,2<=_<4,>=4
Empty
difference All 1<=_<2,3<=_<4,>=4
<1,2<=_<3
difference All All
Empty
difference <4 2<=_<3 <1
1<=_<2,3<=_<4
difference <4 2<=_<3,3<=_<4 <1
1<=_<2
difference All <1 >=4
1<=_<4
difference All >=1 <4
Empty
difference All Empty Empty
All
disjoint All Empty Empty
True
disjoint All Empty All
False
disjoint <1 1<=_<2 2<=_<3 3<=_<4 >=4
True
disjoint <1 1<=_<2 2<=_<3 3<=_<4 <4
False
disjoint 2<=_<3 1<=_<2 2<=_<4
False
disjoint 1<=_<2 2<=_<3 2<=_<4
False
disjoint 1<=_<2,3<=_<4 <1,2<=_<3 >=4
True
equal All All,All Empty
False
equal All All,All All
True
equal All <1,>=1 <2,2<=_<3,>=3
True
equal 1<=_<4 2<=_<4,1<=_<2 1<=_<2,2<=_<3,3<=_<4
True
equal 1<=_<4 2<=_<4,1<=_<2 1<=_<2,2<=_<3
False
equal <4 <3,2<=_<4 <1,<2,2<=_<4
True
equal >=1 >=2 >=1,>=2
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 -

These commands are also defined as make test and make test-diff by the provided Makefile.

Grading

Here is an outline of the grading rubric (10 points total):

1 Code compiles (ghc Main.hs does not error)
1 Clean code (based on the style guidelines)
8 Correctness via I/O testing
- 4 Sample interactions above
- 4 Additional tests

Sanity Check

Once you are finished, check that you added, committed, and pushed everything to your repository before the deadline (or within an eligible late period):

https://github.com/UChicago-PL/cs223-fa23-pa-3-interval-algebra-USERNAME

Misc

If you are really interested in time and have the time, dig into ISO 8601.