intervalalgebra foundations
Introduction
Scope of this tutorial
This tutorial covers the IntervalAlgebra.Core
and IntervalAlgebra.PairedInterval
modules.
Theoretical background
The intervalalgebra
package implements Allen’s interval algebra as defined in
Allen (1983) and axiomatized in
Allen and Hayes (1987).
A good primer on Allen’s algebra can be
found here.
Imports used during examples
The following import declarations are used for the examples provided in this documentation.
import IntervalAlgebra
import IntervalAlgebra.IntervalDiagram
import Data.Bifunctor ( Bifunctor(..) )
import Data.List ( sort )
import Data.Time
( addDays, fromGregorian, secondsToDiffTime, Day, UTCTime(..) )
import Witch ( into )
import Data.Set ( fromList, difference, Set )
Intervals
The Interval type
An interval in time according to Allen’s interval algebra is defined by a starting point and an ending point such that the start occurs before the end.
In particular, the start and end cannot be the same moment in time.
Intervals in intervalalgebra are modeled using the Interval
type shown below.
Note that in order to ensure the starting point for an Interval
always occurs before the ending point,
intervalalgebra does not export the constructor for Interval
, and instead provides a collection of functions that can be used to create Interval
s that are guaranteed to maintain the invariant.
data Interval a
Displaying Intervals using 'show'
The show
method displays the interval endpoints using the form (<starting point>, <ending point>)
.
We haven’t actually described how the following intervals were created yet; these particular variables are created in the Creating Intervals using 'safeInterval' section.
 An example Interval Integer
print ivInteger
> (2, 6)
 An example Interval Day
print ivDay
> (19670118, 19670124)
 An example Interval UTCTime
print ivUTC
> (19670118 09:00:00 UTC, 19670118 09:13:20 UTC)
Basic Interval instances
The following are some of the basic instances implemented by Interval
.
Eq a => Eq (Interval a)
Ord a => Ord (Interval a)
instance (Show a, Ord a) => Show (Interval a)
print $ ivInteger == ivInteger
> True
print $ ivDay < ivDay
> False
print $ show ivInteger
> "(2, 6)"
Creating Intervals
The available functions are listed in the following table.
The function name is listed in the first column, a short alias name is listed in the second column,
and the return type is listed in the third column
(note that there may be constraints imposed on the type a
that are not shown here).
The parseInterval
construction function has the type constraint Ord a
for the type parameter a
in the return type.
This is required since in order to ensure that a valid interval is being created we need to ensure that the starting point is less than the ending point in the sense of the <
operator.
The other Interval
construction functions all implicitly require Ord a
as well as another constraint that we won’t describe at this time since we don’t introduce the relevant type class until the The IntervalSizeable class section.
For now, it suffices to know that the Int
, Integer
, Data.Time.Day
,
and Data.Time.UTCTime
types all implement the necessary classes in order to create an Interval
using any of the functions described in this section.
Name  Alias  Return Type 


















Creating Maybe Intervals using 'parseInterval'
For the parseInterval
function we provide a left endpoint and a right endpoint as inputs.
If the left endpoint is strictly less than the right endpoint then we get a Right (Interval a)
,
otherwise we get a Left ParseErrorInterval
.
rightIvInteger :: Either ParseErrorInterval (Interval Integer)
rightIvInteger = parseInterval 0 2
leftIvInteger :: Either ParseErrorInterval (Interval Integer)
leftIvInteger = parseInterval 2 2
rightIvDay :: Either ParseErrorInterval (Interval Day)
rightIvDay =
parseInterval (fromGregorian 1967 01 18) (fromGregorian 1967 01 22)
rightIvUTC :: Either ParseErrorInterval (Interval UTCTime)
rightIvUTC = parseInterval
(UTCTime (fromGregorian 1967 01 18) (secondsToDiffTime 32400))
(UTCTime (fromGregorian 1967 01 18) (secondsToDiffTime 33200))
print rightIvInteger
> Right (0, 2)
print leftIvInteger
> Left (ParseErrorInterval "2<=2")
print rightIvDay
> Right (19670118, 19670122)
print rightIvUTC
> Right (19670118 09:00:00 UTC, 19670118 09:13:20 UTC)
Creating Intervals using 'safeInterval'
For the safeInterval
function we provide a pair with a starting point and ending point as the input.
If the ending point is no greater than the starting point then the ending point is adjusted so that the duration is the minimal allowed amount for the endpoint type as defined by the moment
method for the IntervalSizeable class
(see The IntervalSizeable class section for details),
while the starting point is left unchanged.
This mechanism ensures that an Interval
is created where the starting point is strictly less than the ending point.
For example, the minimum duration allowed for an Interval Integer
is 1.
In one of the examples below, the duration provided for ivMinDurInteger
is less than 1 so consequently the ending point for the resulting Interval
is adjusted to be 1 more than the starting point.
ivInteger :: Interval Integer
ivInteger = safeInterval (2, 6)
ivMinDurInteger :: Interval Integer
ivMinDurInteger = safeInterval (2, 2)
ivDay :: Interval Day
ivDay = safeInterval (fromGregorian 1967 01 18, fromGregorian 1967 01 24)
ivUTC :: Interval UTCTime
ivUTC = safeInterval
( UTCTime (fromGregorian 1967 01 18) (secondsToDiffTime 32400)
, UTCTime (fromGregorian 1967 01 18) (secondsToDiffTime 33200)
)
print ivInteger
> (2, 6)
print ivMinDurInteger
> (2, 3)
print ivInteger
> (2, 6)
print ivDay
> (19670118, 19670124)
print ivUTC
> (19670118 09:00:00 UTC, 19670118 09:13:20 UTC)
Creating Intervals using 'beginerval' and 'enderval'
The beginerval
and enderval
functions offer alternatives to the safeInterval
function for creating Interval
s.
The beginerval
function takes a duration and a starting point as inputs,
while the enderval
function takes a duration and an ending point as inputs.
Similar to how the safeInterval
function operates,
if the duration is smaller than the minimal allowed amount for the endpoint type as defined by the moment
method for the IntervalSizeable
class,
then the duration is adjusted to take the value of the minimum duration.
In the following examples, we see two instances where the input duration is smaller than 1, which is the minimal allowed amount for an Interval Integer
. Note that the expression type signatures are needed to prevent an ambiguous type variable error.
print (beginerval 2 3 :: Interval Integer)
> (3, 5)
print (beginerval (2) 3 :: Interval Integer)
> (3, 4)
print (enderval 2 12 :: Interval Integer)
> (10, 12)
print (enderval (2) 12 :: Interval Integer)
> (11, 12)
Creating Intervals using 'beginervalMoment' and 'endervalMoment'
The beginervalMoment
and endervalMoment
functions create Interval
s with the minimum duration as defined by the corresponding IntervalSizeable
instance.
In the case of beginervalMoment
the starting point is specified by the function’s input value,
while for the case of endervalMoment
the ending point is specified by the function’s input value.
print (beginervalMoment 11 :: Interval Integer)
> (11, 12)
print (endervalMoment 11 :: Interval Integer)
> (10, 11)
Additional Interval data
The following data will be used in various places in the study.
The naming convention used for the variables is as follows:
each has type Interval Integer
,
and a given variable with a name like e.g. iv6to8
has a starting point of 6 and an ending point of 8.
iv0to2, iv2to4, iv2to5, iv4to5, iv5to8, iv6to8, iv3to6 :: Interval Integer
iv0to2 = safeInterval (0, 2)
iv2to4 = safeInterval (2, 4)
iv2to5 = safeInterval (2, 5)
iv3to6 = safeInterval (3, 6)
iv4to5 = safeInterval (4, 5)
iv5to8 = safeInterval (5, 8)
iv6to8 = safeInterval (6, 8)
PairedIntervals
Allen’s interval algebra provides the theoretical underpinnings of the intervalalgebra library, and is defined exclusively with regards to intervals. However, applications typically aren’t solely interested in the relationships between abstract intervals in time, and instead usually care about what happened as well as when it happened. For example:

What was the first event with starting point no earlier than January 1, 2000 at 00:00:00?

What were the events that occurred with starting point no earlier than 0 and ending point no later than 455?
To support these kinds of needs intervalalgebra provides the PairedInterval
type.
The PairedInterval type
The PairedInterval
type is defined as follows. The constructor is not exported.
data PairedInterval b a
You can create a PairedInterval
using the makePairedInterval
function which has the following type signature.
makePairedInterval :: b > Interval a > PairedInterval b a
The following are some examples of creating PairedInterval
s.
The show
method displays PairedInterval
s using the form {<interval>, <data>}
.
pairListstringInteger :: PairedInterval [String] Integer
pairListstringInteger =
makePairedInterval ["John", "Paul", "George", "Ringo"] ivInteger
pairStringDay :: PairedInterval String Day
pairStringDay = makePairedInterval "vacation" ivDay
print pairListstringInteger
> {(2, 6), ["John","Paul","George","Ringo"]}
print pairStringDay
> {(19670118, 19670124), "vacation"}
Basic PairedInterval instances
The following are some of the basic instances implemented by PairedInterval
.
(Eq a, Eq b) => Eq (PairedInterval b a)
(Eq a, Eq b, Ord a) => Ord (PairedInterval b a)
(Show b, Show a, Ord a) => Show (PairedInterval b a)
print $ pairStringDay == pairStringDay
> True
print $ pairListstringInteger < pairListstringInteger
> False
print $ show pairStringDay
> "{(19670118, 19670124), \"vacation\"}"
Getting and setting the elements of a PairedInterval
Getting and setting the interval portion of a PairedInterval
The ability to get and set the Interval
portion of a PairedInterval
is provided by getInterval
and setInterval
methods of the Intervallic
class along with the associated helper functions begin
and end
.
You can also use the intervals
convenience function for extracting the intervals out of a Functor
of PairedIntervals
.
See the The PairedInterval instance of Intervallic section for more details regarding the type class and instance.
print pairListstringInteger
> {(2, 6), ["John","Paul","George","Ringo"]}
print $ getInterval pairListstringInteger
> (2, 6)
print $ setInterval pairListstringInteger (safeInterval (4, 9) :: Interval Integer)
> {(4, 9), ["John","Paul","George","Ringo"]}
print $ intervals [pairListstringInteger, pairListstringInteger]
> [(2, 6),(2, 6)]
print $ begin pairListstringInteger
> 2
print $ end pairListstringInteger
> 6
Getting and setting the data portion of a PairedInterval
To get the data (i.e. the noninterval) portion out of a PairedInterval
value you can use the getPairData
function.
To set the data you have to create a new PairedInterval
with the updated data.
print pairStringDay
> {(19670118, 19670124), "vacation"}
print $ getPairData pairStringDay
> "vacation"
print $ makePairedInterval "ski trip" (getInterval pairStringDay)
> {(19670118, 19670124), "ski trip"}
Interfaces for embedding Intervals
intervalalgebra is built around three typeclasses designed to separate concerns of constructing,
relating, and combining types that contain Interval
s:

Intervallic
provides an interface to the data structures which contain anInterval
. 
IntervalCombinable
provides an interface to methods of combining twoInterval
s. 
IntervalSizeable
provides methods for measuring and modifying the size of an interval.
An advantage of nested typeclass design is that users can define a types with embedded Interval
s with just the amount of structure that they need.
The Intervallic class
The Intervallic
class is defined as
class Intervallic i where
with methods
getInterval :: i a > Interval a
setInterval :: i a > Interval b > i b
and accompanying helper functions for getting the starting point and ending point out of an Interallic
value:
begin :: Intervallic i => i a > a
end :: Intervallic i => i a > a
These methods provide an interface for classes to define a way to get an Interval a
out of an i a
,
and to change the value of an Interval a
contained in an i a
.
The Interval instance of Intervallic
The following instance is provided for Intervallic
:
instance Intervallic Interval
and the methods specialize to
getInterval :: Interval a > Interval a
setInterval :: Interval a > Interval b > Interval b
For the case of getInterval
the Interval
provided as the input is returned unchanged,
while for the case of setInterval
the replacement Interval
(i.e. the second input) is returned unchanged.
print ivInteger
> (2, 6)
print $ getInterval ivInteger
> (2, 6)
print $ setInterval ivInteger (beginerval 3 12 :: Interval Integer)
> (12, 15)
print $ begin ivInteger
> 2
print $ end ivInteger
> 6
Obviously this is not very useful for Interval
values.
Where Intervallic
comes in handy is for embedding Interval
s in other types — as long as we know how to extract and to replace the embedded interval we can do all of the usual intervalalgebra operations that we would do to regular Interval
s.
The PairedInterval instance of Intervallic
The following instance is provided for Intervallic
:
instance Intervallic (PairedInterval b)
and the methods specialize to
getInterval :: PairedInterval b a > Interval a
setInterval :: PairedInterval b a > Interval c > PairedInterval b c
See the Getting and setting the interval portion of a PairedInterval section for example usages of Intervallic
methods.
The IntervalSizeable class
The IntervalSizeable
class is defined as
class (Ord a, Num b, Ord b) => IntervalSizeable a b  a > b
with methods
moment :: forall a . b
duration :: Intervallic i => i a > b
add :: b > a > a
diff :: a > a > b
In general, for a pair of types a
and b
, the IntervalSizeable
class provides an interface for operations related to calculating the duration of an existing Intervallic
and other sizerelated concerns.
For the important special case of the Interval
instance of Intervallic
, the a
type represents the type used for the starting and ending points of the Interval
,
while the b
type for the intervalalgebra defined instances of IntervalSizeable
represents the type obtained by calculating the "difference" between the starting and ending points,
as defined by diff
.
Userdefined instances of Intervallic
need not maintain this interpretation.
IntervalSizeable instances
The following instances are provided for IntervalSizeable
.
IntervalSizeable Int Int
IntervalSizeable Integer Integer
IntervalSizeable Day Integer
IntervalSizeable UTCTime NominalDiffTime
As an example, consider the IntervalSizeable Day Integer
instance with the following methods.
moment :: forall a. Integer
duration :: Intervallic i Day => i Day > Integer
add :: Integer > Day > Day
diff :: Day > Day > Integer
In the event that we apply duration
to an Interval Day
then we get a further specialization of duration
to the following type.
duration :: Interval Day > Integer
The following are some example uses of IntervalSizeable
methods.
print ivDay
> (19670118, 19670124)
print $ moment @Day
> 1
print $ duration ivDay
> 6
print $ add 15 (begin ivDay)
> 19670202
print $ diff (add 15 (begin ivDay)) (begin ivDay)
> 15
The IntervalCombinable class
The IntervalCombinable
class is defined as
class Intervallic i => IntervalCombinable i a
with methods
(.+.) :: i a > i a > Maybe (i a)
(><) :: i a > i a > Maybe (i a)
(<+>) :: (Semigroup (f (i a)), Applicative f) => i a > i a > f (i a)
The Interval instance of IntervalCombinable
Method types
The following instance (among others) is provided for IntervalCombinable
:
Ord a => IntervalCombinable Interval a
and the methods specialize to
(.+.) :: Ord a => Interval a > Interval a > Maybe (Interval a)
(><) :: Ord a => Interval a > Interval a > Maybe (Interval a)
(<+>) :: (Ord a, Semigroup (f (Interval a)), Applicative f) =>
Interval a > Interval a > f (Interval a)
A brief introduction to 'meets' and 'before'
We don’t properly introduce the meets
and before
functions that are used by the IntervalCombinable
methods until the upcoming The IntervalRelation type and associated predicates section.
But for now it suffices to know that for two Interval
s x
and y
:

The result of evaluating
x `meets` y
isTrue
if the ending point ofx
is equal to the starting point ofy
, andFalse
otherwise. 
The result of evaluating
x `before` y
isTrue
if the ending point ofx
is less than the starting point ofy
, andFalse
otherwise.
IntervalCombinable methods for Interval

The
.+.
method returns aJust
value if the first inputmeets
the second, andNothing
otherwise. In the case that the value is aJust
then it contains theInterval
created by combining the two inputs, or more precisely stated it contains theInterval
with the starting point given by the starting point of the first input, and the ending point given by the ending point of the second input. 
The
><
method returns aJust
value if the first input isbefore
the second, andNothing
otherwise. In the case that the value is aJust
then it contains theInterval
created by spanning the two inputs, or more precisely stated it contains theInterval
with the starting point given by the ending point of the first input, and the ending point given by the starting point of the second input. 
The
<+>
method is a little bit more complicated to reason about since its behavior differs depending on the return type.
If we have two inputs where the first input is
before
the second, then it lifts the inputs to the return type and combines them by using the<>
method. 
If we have two inputs where the first input is not
before
the second, then it creates a lifted version of anInterval
with regards to the output type, and where the starting point is the earlier of the two starting points and the ending point is the later of the two ending points.

The following are some example usages of these methods.
Recall from the Additional Interval data section that a variable with a name like e.g. iv2to5
has a starting point of 2 and an ending point of 5.
 The Just Interval formed from combining the Intervals, since iv0to2 `meets` iv2to5
print $ iv0to2 .+. iv2to5
> Just (0, 5)
 A Nothing since iv0to2 doesn't `meets` iv5to8
print $ iv0to2 .+. iv5to8
> Nothing
 The Just Interval formed from the end of the first and the beginning of the
 second, since iv0to2 is `before` iv5to8
print $ iv0to2 >< iv5to8
> Just (2, 5)
 A Nothing since iv0to2 isn't `before` iv2to5
print $ iv0to2 >< iv2to5
> Nothing
The PairedInterval instance of IntervalCombinable
The following instance (among others) is provided for IntervalCombinable
:
instance (Ord a, Eq b, Monoid b) => IntervalCombinable (PairedInterval b) a
and the methods specialize to
(.+.) :: (Ord a, Eq b, Monoid b) =>
PairedInterval b a > PairedInterval b a > Maybe (PairedInterval b a)
(><) :: (Ord a, Eq b, Monoid b) =>
PairedInterval b a > PairedInterval b a > Maybe (PairedInterval b a)
(<+>) :: ((Ord a, Eq b, Monoid b), Semigroup (f (PairedInterval b a)), Applicative f) =>
PairedInterval b a > PairedInterval b a > f (PairedInterval b a)
In what follows we describe the IntervalCombinable
methods for PairedInterval
and provide some examples.
Note that we don’t properly introduce the meets
and before
functions that are used by the IntervalCombinable
methods until the upcoming The IntervalRelation type and associated predicates section,
but for a short introduction see the A brief introduction to 'meets' and 'before' section.

The
.+.
method returns aJust
value if the first inputmeets
the second, andNothing
otherwise. In the case that the value is aJust
then it contains aPairedInterval
with the data portion given by the data in the second argument to.+.
, and theInterval
portion obtained by combining the two inputs (more precisely stated it contains theInterval
with the starting point given by the starting point of the first input, and the ending point given by the ending point of the second input). 
The
><
method returns aJust
value if the first input isbefore
the second, andNothing
otherwise. In the case that the value is aJust
then it contains thePairedInterval
with the data portion given by themempty
method for theMonoid
instance of the data type ofPairedInterval
s, and theInterval
portion obtained by spanning the two inputs (or more precisely stated it contains theInterval
with the starting point given by the ending point of the first input, and the ending point given by the starting point of the second input). 
The
<+>
method is a little bit more complicated to reason about since its behavior differs depending on the return type.
If we have two inputs where the first input is
before
the second, then it lifts the inputs to the return type and combines them by using the<>
method. 
If we have two inputs where the first input is not
before
the second, then it creates a lifted version of aPairedInterval
with regards to the output type, where the data is the result of applying<>
to the data portions of the two inputs, and where theInterval
is such that the starting point is the earlier of the two starting points of the embeddedInterval
s and the ending point is the later of the two ending points of the embeddedInterval
s.

The following are some example usages of these methods.
Recall from the Additional Interval data section that a variable with a name like e.g. iv2to5
has a starting point of 2 and an ending point of 5.
 The Just Interval formed from combining the Intervals and taking the data
 portion from the second argument, since iv0to2 `meets` iv2to5
print $ makePairedInterval "a" iv0to2 .+. makePairedInterval "b" iv2to5
> Just {(0, 5), "b"}
 A Nothing since iv0to2 doesn't `meets` iv5to8
print $ makePairedInterval "a" iv0to2 .+. makePairedInterval "b" iv5to8
> Nothing
 The Just Interval formed from spanning the Intervals and taking the data
 portion from the `mempty` method of the Monoid String instance, since
 iv0to2 is `before` iv5to8
print $ makePairedInterval "a" iv0to2 >< makePairedInterval "b" iv5to8
> Just {(2, 5), ""}
 A Nothing since iv0to2 isn't `before` iv2to5
print $ makePairedInterval "a" iv0to2 >< makePairedInterval "b" iv2to5
> Nothing
Updating intervals
Expanding Intervallic endpoints
Intervalalgebra provides a collection of functions for expanding one or more Intervallic
endpoints,
and where in this context "expanding" means that the endpoints can only be updated in a direction that makes the duration of the Intervallic
larger.

expandl
moves anIntervallic
's starting point "to the left." The inputs are a duration and anIntervallic
value. 
expandr
moves anIntervallic
's ending point "to the right." The inputs are a duration and anIntervallic
value. 
expand
moves anIntervallic
's starting point "to the left" and ending point "to the right." The inputs are two durations and anIntervallic
value.
If the provided value by which to move either the starting or ending points is less than the minimal amount,
as defined by the moment
method for the corresponding IntervalSizeable
class,
then the corresponding point is left unchanged.
This has the effect of ensuring that these methods cannot decrease the duration of the Interval
,
as all sensible IntervalSizeable
instances will have a positive moment
.
print ivInteger
> (2, 6)
print $ expandl 4 ivInteger
> (2, 6)
print $ expandl 0 ivInteger
> (2, 6)
print $ expandr 5 ivInteger
> (2, 11)
print $ expandr (3) ivInteger
> (2, 6)
print $ expand 4 5 ivInteger
> (2, 11)
print $ expand 0 (3) ivInteger
> (2, 6)
Creating intervals that share an endpoint with an Intervallic
The following functions can be used to create an Interval
that shares an endpoint with an Intervallic
.

beginervalFromEnd
creates an interval that has the same starting endpoint as the ending point of an inputIntervallic
value. The inputs are a duration and anIntervallic
value. 
endervalFromBegin
creates an interval that has the same ending point as the starting point of an inputIntervallic
value. The inputs are a duration and anIntervallic
value. 
momentize
creates an interval with the minimum duration for the correspondingIntervalSizeable
instance that has the same starting point as the starting point of an inputIntervallic
value. The input is anIntervallic
value.
In the event that any of the provided durations are less than the minimal allowed amount for the endpoint type as defined by the moment
method for the corresponding IntervalSizeable
class then the duration is adjusted to be the mimimum duration.
print ivInteger
> (2, 6)
beginervalFromEnd 5 ivInteger
> (6, 11)
beginervalFromEnd (2) ivInteger
> (6, 7)
endervalFromBegin 12 ivInteger
> (10, 2)
endervalFromBegin (6) ivInteger
> (1, 2)
print $ momentize ivInteger
> (2, 3)
Shifting intervals
The shiftFromBegin
and shiftFromEnd
functions have the following type signatures.
shiftFromBegin
:: (IntervalSizeable a b, Intervallic i0 a)
=> i0 a > i1 a > i1 b
shiftFromEnd
:: (IntervalSizeable a b, Intervallic i0 a)
=> i0 a > i1 a > i1 b
For each function, you’re creating a new interval with starting and ending points given in units relative to the starting point (in the case of ShiftFromBegin
) or ending point (in the case of ShiftFromEnd
) of another Intervallic.
This can be useful when you don’t care about the abolute time of when something happened, but rather when it happened relative to some other event.
In more detail, shiftFromBegin
and shiftFromEnd
have the following behavior:

shiftfromBegin
diff
s the starting point from the first input from both the starting and ending point of the second input. 
shiftfromEnd
is similar toshiftfromBegin
except that it applies thediff
to the ending point of its first input.
In the examples below we see various combinations of types that can be provided as inputs for shiftFromBegin
and shiftFromEnd
.
Recall from the Additional Interval data section that a variable with a name like e.g. iv2to4
has a starting point of 2 and an ending point of 4.
Also note that the return type need not be the same as the input types, as is the case when the inputs are Interval Day
s.
print [iv2to4, iv5to8]
> [(2, 4),(5, 8)]
print ivDay
> (19670118, 19670124)
print $ shiftFromBegin iv2to4 iv5to8
> (3, 6)
print $ shiftFromBegin ivDay ivDay
> (0, 6)
print $ shiftFromEnd iv2to4 iv5to8
> (1, 4)
print $ shiftFromEnd ivDay ivDay
> (6, 0)
Interval relations
The ComparativePredicateOf1 and ComparativePredicateOf2 types
The following are the type declarations for ComparativePredicateOf1
and ComparativePredicateOf2
;
these will be needed for the upcoming The IntervalRelation type and associated predicates section.
type ComparativePredicateOf1 a = (a > a > Bool)
type ComparativePredicateOf2 a b = (a > b > Bool)
The IntervalRelation type and associated predicates
See Thirteen basic relations for a figure corresponding to each of the possible interval relations.
The following type enumerates each of the possible relationships that a pair of Intervallic
values can have.
The name in the comment to the right of each type is a predicate function corresponding to the particular variant through the relate
function,
in the sense that if the value returned by x `relate` y
is e.g. Starts
,
then x `starts` y
evaluates to True
.
data IntervalRelation =
Before  before/precedes
 Meets  meets
 Overlaps  overlaps
 FinishedBy  finishedBy
 Contains  contains
 Starts  starts
 Equals  equals
 StartedBy  startedBy
 During  during
 Finishes  finishes
 OverlappedBy  overlappedBy
 MetBy  metBy
 After  after/precededBy
Next, consider the following diagram providing a visual representation of some example data.
This diagram is created using the parseIntervalDiagram
,
however in order to save space we do not provide the definition used to create the diagram.
Each row shows an interval represented using hyphens and corresponding to a variable with the name displayed on the righthand side of the row.
Recall from the Additional Interval data section that a variable with a name like e.g. iv2to5
has a starting point of 2 and an ending point of 5.
The hyphens in the diagram corresponding to e.g. iv2to5
start after the second character and end after the fifth character.
 < [iv0to2]
 < [iv2to4]
 < [iv2to5]
 < [iv3to6]
 < [iv4to5]
 < [iv6to8]
 < [iv5to8]
============
The following table describes the 13 predicates corresponding to the 13 Interval Algebra relations. Each of the predicates has the following type signature.
(Ord a, Intervallic i0, Intervallic i1) => ComparativePredicateOf2 (i0 a) (i1 a)
Name  Definition  Example 





































Also note that there are functions before
and after
which are synonyms for precedes
and precededBy
,
respectively.
Composite relations and predicates
The fundamental interval algebra relations are rather finegrained, and often the relationships we would like to use to describe pairs of intervals are compositions of the fundamental relations. For this reason, intervalalgebra provides some builtin relations composed of multiple fundamental relations, as well as facilities for defining your own composite relations.
Builtin composite relations
The variables in the following table each have the type Set IntervalRelation
.
Name  Relations 








Every fundamental relation 
Additional points of note:

disjointRelations
corresponds to thedisjoint
predicate 
withinRelations
corresponds to theenclosedBy
/within
predicates 
strictWithinRelations
doesn’t currently correspond to any builtin predicates 
intervalRelations
is useful if you want to create a large composite relation by removing a few relations (but also seecomplement
)
Builtin composite predicates
Name  Definition 


Does one of the relations hold: 

Do none of the relations hold: 

Do none of the relations hold: 

Does one of the relations hold: 

Does one of the relations hold: 

Does one of the relations hold: 
Additional points of note:

The
disjoint
andnotDisjoint
/concur
predicates are complements of each other in the sense thatx `disjoint` y
andnot (x `notDisjoint` y)
evalute to the same value for any pair ofx
andy
. 
The
encloses
andenclosedBy
/within
predicates are duals of each other in the sense thatx `encloses` y
andy `enclosedBy` x
evalute to the same value for any pair ofx
andy
.
Constructing custom composite relations
The following examples demonstrate some approaches for constructing Set IntervalRelation
s.
 Set, `fromList`, and in a later example `difference` are imported from
 Data.Set
endedPriorRelations :: Set IntervalRelation
endedPriorRelations = fromList [Before, Meets]
 We can in general create a new Set by taking the set Difference of one Set
 and another Set
notEndedPriorRelations :: Set IntervalRelation
notEndedPriorRelations = intervalRelations `difference` endedPriorRelations
 However, the `complement` function is provided for the common case of taking
 the Set Difference of the `intervalRelations` Set and another Set
notEndedPriorRelations' :: Set IntervalRelation
notEndedPriorRelations' = complement endedPriorRelations
 IntervalAlgebra exports versions of `Data.Set`s `intersection` and `union`
 functions where the types are specialized to `Set IntervalRelation`s
intervalRelations' :: Set IntervalRelation
intervalRelations' = endedPriorRelations `union` notEndedPriorRelations
 The intersection of two disjoint sets
empty :: Set IntervalRelation
empty = endedPriorRelations `intersection` notEndedPriorRelations
print endedPriorRelations
> fromList [Before,Meets]
print notEndedPriorRelations
> fromList [Overlaps,FinishedBy,Contains,Starts,Equals,StartedBy,During,Finishes,OverlappedBy,MetBy,After]
print notEndedPriorRelations'
> fromList [Overlaps,FinishedBy,Contains,Starts,Equals,StartedBy,During,Finishes,OverlappedBy,MetBy,After]
print intervalRelations'
> fromList [Before,Meets,Overlaps,FinishedBy,Contains,Starts,Equals,StartedBy,During,Finishes,OverlappedBy,MetBy,After]
print empty
> fromList []
Constructing custom composite predicates
The following examples demonstrate some approaches for constructing predicate functions.
 We can construct a predicate function from a 'Set IntervalRelation'
endedPrior
:: (Ord a, Intervallic i0, Intervallic i1)
=> ComparativePredicateOf2 (i0 a) (i1 a)
endedPrior = predicate (fromList [Before, Meets])
 We can also construct a predicate function directly from a list of predicate
 functions
endedPrior'
:: (Ord a, Intervallic i0, Intervallic i1)
=> ComparativePredicateOf2 (i0 a) (i1 a)
endedPrior' = unionPredicates [before, meets]
 As an alternative to `unionPredicates` we can compose predicate functions
 using the <> operator. If we had multiple predicates we could use e.g.:
 p1 <> p2 <> p3
endedPrior''
:: (Ord a, Intervallic i0, Intervallic i1)
=> ComparativePredicateOf2 (i0 a) (i1 a)
endedPrior'' = before <> meets
print $ iv0to2 `precedes` iv3to6
print $ iv0to2 `meets` iv3to6
print $ iv0to2 `endedPrior` iv3to6
> True
> False
> True
print $ iv0to2 `precedes` iv2to4
print $ iv0to2 `meets` iv2to4
print $ iv0to2 `endedPrior` iv2to4
> False
> True
> True
print $ iv5to8 `precedes` iv2to4
print $ iv5to8 `meets` iv2to4
print $ iv5to8 `endedPrior` iv2to4
> False
> False
> False
An example intervalalgebra application
Problem description
In this section we present an example application taken from the domain of epidemiological studies. For this example, we want to compare the difference, if any, between an industry standard vaccine and a newtomarket vaccine in preventing a person from contracting influenza (flu). The primary information that we wish to obtain is how long it takes people to contract flu after taking a vaccine; however we only observe a given person for a finite amount of time and they might not get a vaccine or they might not contract flu (or neither) during the time while they are under observation.
Input data
In order to study our research question, we collect data for multiple subjects. For a given subject, we can have data that includes the following types of health care events and subject metadata. Our interest is in a flu diagnosis.

Enrollment: a period in time when a subject was under observation for the study. Subjects may drop out of the study at any time, and may have gaps of time where they were not observed in the study. If there are gaps between enrollment periods, there is an allowed grace period during which if the subject reenters observation then they will still be considered eligible for the study. If however, the grace period expires and the subject comes back under observation then any data after that will be considered inadmissible. For this example, we will consider the grace period to be 8 (see the note below about the unit of time).

Treatment: Either the standard vaccine or the alternative vaccine.

Diagnosis: One of several possible diagnoses.
For simplicity the Interval
endpoints are provided as Integer
s (and hence the corresponding durations are also Integer
s),
however in a more realistic setting the endpoints would more likely be something like a Data.Time.Day
.
Target processed data results
The information that we would like to extract from the input data is the following. We will see in the upcoming Data model section that additional information is included in the output data type, but this is only supplemental data included for the reader’s understanding.

The treatment type of the first vaccination treatment, if applicable.

The amount of time between the end of the treatment vaccination period and the start of the first flu diagnosis period, if applicable.

The amount of time between the end of the treatment vaccination period and the end of the overall eligibility period, if applicable.
Data model
The types that we will use to model our problem domain are the following:

StudyEvent
is the basic unit of observation. 
SubjEvents
is a list ofStudyEvent
s that are assumed to all correspond to a given subject, and to be complete in the sense that there are no otherStudyEvent
s for that particular subject that are not included in the list. 
ProcessedSubj
is the type of the target output information for a given subject.
data DataType = Enrollment  Treatment TreatmentType  Diagnosis DiagnosisType
deriving (Eq, Ord, Show)
data TreatmentType = StandardVaccine  NewVaccine
deriving (Eq, Ord, Show)
data DiagnosisType = RightAsRain  UpsetTummy  CommonCold  Flu
deriving (Eq, Ord, Show)
type StudyEvent = PairedInterval DataType Integer
type SubjEvents = [StudyEvent]
data ProcessedSubj = ProcessedSubj
{ getEnrollment :: Maybe (Interval Integer)
, getFirstTrt :: Maybe StudyEvent
, getFirstFlu :: Maybe StudyEvent
, getTrtType :: Maybe TreatmentType
, getTimeToFlu :: Maybe Integer
, getTimeToEndEnr :: Maybe Integer
}
deriving Show
maxEnrGap :: Integer
maxEnrGap = 8
Example data
Some example data is constructed below.
In all, there are four subjects, with data collected in the variables id1Events
,
id2Events
, id3Events
, and id4Events
.
To skip ahead and see the results produced by our data processing functions (introduced later) see the Calculate results section.
It is important to note that the data is sorted chronologically within a given subject; some of the routines that we will see later depend on this being the case.
Example data subject 1

For the "id1" subject we see an example where all of the enrollment periods fall within the allotted grace period of 8 days, so the overall study period has a starting point of 6 and an ending point of 430 (i.e. 8 days after the ending point of the last enrollment period).

The
Diagnosis RightAsRain
andDiagnosis CommonCold
entries are not relevant to the study definition and should effectively be ignored. 
The treatment type is
NewVaccine
with an ending point of 23, and we don’t see any flu occurrence. 
The time to the end of enrollment is the difference between the end of the first treatment period and the end of the overall study period, which for this example is 407 (i.e. 430  23).
id1Event1, id1Event2, id1Event3, id1Event4, id1Event5, id1Event6, id1Event7
:: StudyEvent
id1Event1 = makePairedInterval Enrollment (safeInterval (6, 191))
id1Event2 = makePairedInterval Enrollment (safeInterval (199, 345))
id1Event3 = makePairedInterval Enrollment (safeInterval (347, 422))
id1Event4 = makePairedInterval (Diagnosis RightAsRain) (safeInterval (12, 13))
id1Event5 = makePairedInterval (Treatment NewVaccine) (safeInterval (22, 23))
id1Event6 = makePairedInterval (Diagnosis RightAsRain) (safeInterval (131, 132))
id1Event7 = makePairedInterval (Diagnosis CommonCold) (safeInterval (161, 162))
id1Events :: SubjEvents
id1Events = sort
[id1Event1, id1Event2, id1Event3, id1Event4, id1Event5, id1Event6, id1Event7]
Example data subject 2

For the "id2" subject we see an example where the start of the second enrollment period does not fall within the allotted grace period of 8 days after the first enrollment period, so the overall study period has a starting point of 2 and an ending point of 214 (i.e. 8 days after the ending point of the first enrollment period).

The
Diagnosis RightAsRain
,Diagnosis CommonCold
andDiagnosis UpsetTummy
entries are not relevant to the study definition and should effectively be ignored. 
The treatment type is
StandardVaccine
with an ending point of 99, and although we do see a flu occurrence, it happens outside of the overall study period and should effectively be ignored. 
The time to the end of enrollment is the difference between the end of the first treatment period and the end of the overall study period, which for this example is 115 (i.e. 214  99).
id2Event1, id2Event2, id2Event3, id2Event4, id2Event5, id2Event6, id2Event7, id2Event8
:: StudyEvent
id2Event1 = makePairedInterval Enrollment (safeInterval (2, 206))
id2Event2 = makePairedInterval Enrollment (safeInterval (222, 299))
id2Event3 = makePairedInterval Enrollment (safeInterval (304, 486))
id2Event4 = makePairedInterval (Diagnosis RightAsRain) (safeInterval (4, 5))
id2Event5 =
makePairedInterval (Treatment StandardVaccine) (safeInterval (98, 99))
id2Event6 = makePairedInterval (Diagnosis CommonCold) (safeInterval (161, 162))
id2Event7 = makePairedInterval (Diagnosis UpsetTummy) (safeInterval (191, 192))
id2Event8 = makePairedInterval (Diagnosis Flu) (safeInterval (255, 256))
id2Events :: SubjEvents
id2Events = sort
[ id2Event1, id2Event2, id2Event3, id2Event4, id2Event5 , id2Event6
, id2Event7, id2Event8 ]
Example data subject 3

For the "id3" subject we see an example where we have just one enrollment period, so the overall study period has a starting point of 7 and an ending point of 205 (i.e. 8 days after the ending point of the enrollment period).

The treatment type is
StandardVaccine
with an ending point of 20, and we see a flu occurrence with a starting point of 180. Thus, the time to first (and only) flu diagnosis is 160 (i.e. 180  20) 
The time to the end of enrollment is the difference between the end of the first treatment period and the end of the overall study period, which for this example is 185 (i.e. 205  20).
id3Event1, id3Event2, id3Event3 :: StudyEvent
id3Event1 = makePairedInterval Enrollment (safeInterval (7, 197))
id3Event2 = makePairedInterval (Treatment StandardVaccine) (safeInterval (19, 20))
id3Event3 = makePairedInterval (Diagnosis Flu) (safeInterval (180, 181))
id3Events :: SubjEvents
id3Events = sort [id3Event1, id3Event2, id3Event3]
Example data subject 4

For the "id4" subject we see an example where we have just one enrollment period, so the overall study period has a starting point of 3 and an ending point of 97 (i.e. 8 days after the ending point of the enrollment period).

The
Diagnosis RightAsRain
entry is not relevant to the study definition and should effectively be ignored. 
Since there is no treatment event and no flu event there is no time to flu occurrence and no time to the end of enrollment.
id4Event1, id4Event2 :: StudyEvent
id4Event1 = makePairedInterval Enrollment (safeInterval (3, 89))
id4Event2 = makePairedInterval (Diagnosis RightAsRain) (safeInterval (47, 48))
id4Events :: SubjEvents
id4Events = sort [id4Event1, id4Event2]
Data processing functions
In this section we provide the data processing functions that we can use to calculate the desired output as described in the previous sections.
 Construct the elements of a `ProcessedSubj` one step atatime. Most of the
 actual work is done by the helper functions defined below
processSubj :: SubjEvents > ProcessedSubj
processSubj xs =
let enrPeriod = calcEnrPeriod xs  enrollment period
enrEvents = calcEnrEvents enrPeriod xs  events within enrollment
firstTrt = findFirstTrt enrPeriod xs  first treatment in enr
firstTrtType = extractTrtType firstTrt  first trt type
firstTrtIv = fmap getInterval firstTrt  first trt interval
firstFlu = findFirstFlu firstTrtIv enrEvents  first flu in enr
ttFlu = calcDiff firstFlu firstTrt  time to first flu
ttEndEnr = calcAtRisk enrPeriod firstTrt  time to end of enr
in ProcessedSubj enrPeriod firstTrt firstFlu firstTrtType ttFlu ttEndEnr
 Construct the "enrollment period", which is defined at the period of time
 with the start endpoint given by their earliest enrollment period and end
 endpoint given by the first time that they fall out of the grace period. In
 the event that a subject did not have any enrollment periods then the return
 value is a Nothing.

 Note that this function uses the `combineIntervals` function which was not
 covered in this tutorial, but is exported from IntervalAlgebra via
 IntervalAlgebra.IntervalUtilities.
calcEnrPeriod :: SubjEvents > Maybe (Interval Integer)
calcEnrPeriod xs  null combinedPeriods = Nothing
 otherwise = Just (head combinedPeriods)
where combinedPeriods = (combineIntervals . addMaxEnrGap . extractEnrIvs) xs
 Filter the enrollment events in the SubjEvents and extract the Interval
 from each one
extractEnrIvs :: SubjEvents > [Interval Integer]
extractEnrIvs = intervals . filter (checkEnr . getPairData)
where
checkEnr Enrollment = True
checkEnr _ = False
 Extend the end endpoint for each Interval by `maxEnrGap`
addMaxEnrGap :: [Interval Integer] > [Interval Integer]
addMaxEnrGap = map (expandr maxEnrGap)
 Filter the SubjEvents to those with endpoints that do not extend past the
 enrollment period's endpoints
calcEnrEvents :: Maybe (Interval Integer) > SubjEvents > SubjEvents
calcEnrEvents mayIv xs = case mayIv of
Nothing > []
Just y > filter (\x > getInterval x `enclosedBy` y) xs
 Find the first flu vaccine administrations occuring within the enrollment
 period
findFirstTrt :: Maybe (Interval Integer) > SubjEvents > Maybe StudyEvent
findFirstTrt Nothing _ = Nothing
findFirstTrt (Just iv) xs  null filteredIntakes = Nothing
 otherwise = Just (head filteredIntakes)
where
p x = checkTrt (getPairData x) && (getInterval x `enclosedBy` iv)
checkTrt (Treatment _) = True
checkTrt _ = False
filteredIntakes = filter p xs
 Extract the treatment type out of a StudyEvent. If there is no event or the
 StudyEvent type isn't TreatmentType then return Nothing
extractTrtType :: Maybe StudyEvent > Maybe TreatmentType
extractTrtType Nothing = Nothing
extractTrtType (Just x) = case getPairData x of
Treatment StandardVaccine > Just StandardVaccine
Treatment NewVaccine > Just NewVaccine
_ > Nothing
 Find the first flu diagnosis occuring within the enrollment period
findFirstFlu :: Maybe (Interval Integer) > SubjEvents > Maybe StudyEvent
findFirstFlu Nothing _ = Nothing
findFirstFlu (Just iv) xs  null filteredFlus = Nothing
 otherwise = Just (head filteredFlus)
where
endedPrior = before <> meets
p x = checkDiagFlu (getPairData x) && (iv `endedPrior` getInterval x)
checkDiagFlu (Diagnosis Flu) = True
checkDiagFlu _ = False
filteredFlus = filter p xs
 Calculate the difference between the start endpoint of the first Intervallic
 and the start endpoint of the second Intervallic
calcDiff
:: (IntervalSizeable a b, Intervallic i0, Intervallic i1)
=> Maybe (i0 a)
> Maybe (i1 a)
> Maybe b
calcDiff (Just y) (Just x) = Just $ diff (begin y) (end x)
calcDiff _ _ = Nothing
 Calculate the difference between the end endpoint of the first Intervallic
 and the start endpoint of the second Intervallic
calcAtRisk
:: (IntervalSizeable a b, Intervallic i0, Intervallic i1)
=> Maybe (i0 a)
> Maybe (i1 a)
> Maybe b
calcAtRisk (Just y) (Just x) = Just $ diff (end y) (end x)
calcAtRisk _ _ = Nothing
Calculate results
Here we calculate and print the results of the data processing.
results :: [ProcessedSubj]
results = map processSubj [id1Events, id2Events, id3Events, id4Events]
print $ head results
> ProcessedSubj {getEnrollment = Just (6, 430), getFirstTrt = Just {(22, 23), Treatment NewVaccine}, getFirstFlu = Nothing, getTrtType = Just NewVaccine, getTimeToFlu = Nothing, getTimeToEndEnr = Just 407}
print $ results !! 1
> ProcessedSubj {getEnrollment = Just (2, 214), getFirstTrt = Just {(98, 99), Treatment StandardVaccine}, getFirstFlu = Nothing, getTrtType = Just StandardVaccine, getTimeToFlu = Nothing, getTimeToEndEnr = Just 115}
print $ results !! 2
> ProcessedSubj {getEnrollment = Just (7, 205), getFirstTrt = Just {(19, 20), Treatment StandardVaccine}, getFirstFlu = Just {(180, 181), Diagnosis Flu}, getTrtType = Just StandardVaccine, getTimeToFlu = Just 160, getTimeToEndEnr = Just 185}
print $ results !! 3
> ProcessedSubj {getEnrollment = Just (3, 97), getFirstTrt = Nothing, getFirstFlu = Nothing, getTrtType = Nothing, getTimeToFlu = Nothing, getTimeToEndEnr = Nothing}