interval-algebra foundations

Introduction

Scope of this tutorial

This tutorial covers the IntervalAlgebra.Core and IntervalAlgebra.PairedInterval modules.

Theoretical background

The interval-algebra 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.Set                       ( Set
                                                , difference
                                                , fromList
                                                )
import           Data.Time                      ( Day
                                                , UTCTime(..)
                                                , addDays
                                                , fromGregorian
                                                , secondsToDiffTime
                                                )
import           Witch                          ( into )

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 interval-algebra 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, interval-algebra does not export the constructor for Interval, and instead provides a collection of functions that can be used to create Intervals 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
---> (1967-01-18, 1967-01-24)

-- An example Interval UTCTime
print ivUTC
---> (1967-01-18 09:00:00 UTC, 1967-01-18 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.

Table 1. Constructing new intervals
Name	Alias	Return Type
`parseInterval`	`prsi`	`Either ParseErrorInterval (Interval a)`
`beginerval`	`bi`	`Interval a`
`enderval`	`ei`	`Interval a`
`safeInterval`	`si`	`Interval a`
`beginervalMoment`		`Interval a`
`endervalMoment`		`Interval a`

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 (1967-01-18, 1967-01-22)

print rightIvUTC
---> Right (1967-01-18 09:00:00 UTC, 1967-01-18 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
---> (1967-01-18, 1967-01-24)

print ivUTC
---> (1967-01-18 09:00:00 UTC, 1967-01-18 09:13:20 UTC)

Creating Intervals using 'beginerval' and 'enderval'

The beginerval and enderval functions offer alternatives to the safeInterval function for creating Intervals. 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 Intervals 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 interval-algebra 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 interval-algebra 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 PairedIntervals. The show method displays PairedIntervals 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
---> {(1967-01-18, 1967-01-24), "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
---> "{(1967-01-18, 1967-01-24), \"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 non-interval) 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
---> {(1967-01-18, 1967-01-24), "vacation"}

print $ getPairData pairStringDay
---> "vacation"

print $ makePairedInterval "ski trip" (getInterval pairStringDay)
---> {(1967-01-18, 1967-01-24), "ski trip"}

Interfaces for embedding Intervals

interval-algebra is built around three typeclasses designed to separate concerns of constructing, relating, and combining types that contain Intervals:

Intervallic provides an interface to the data structures which contain an Interval.
IntervalCombinable provides an interface to methods of combining two Intervals.
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 Intervals 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 Intervals in other types — as long as we know how to extract and to replace the embedded interval we can do all of the usual interval-algebra operations that we would do to regular Intervals.

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 size-related 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 interval-algebra defined instances of IntervalSizeable represents the type obtained by calculating the "difference" between the starting and ending points, as defined by diff. User-defined 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
---> (1967-01-18, 1967-01-24)

print $ moment @Day
---> 1

print $ duration ivDay
---> 6

print $ add 15 (begin ivDay)
---> 1967-02-02

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 Intervals x and y:

The result of evaluating x `meets` y is True if the ending point of x is equal to the starting point of y, and False otherwise.
The result of evaluating x `before` y is True if the ending point of x is less than the starting point of y, and False otherwise.

IntervalCombinable methods for Interval

The .+. method returns a Just value if the first input meets the second, and Nothing otherwise. In the case that the value is a Just then it contains the Interval created by combining the two inputs, or more precisely stated it contains the Interval 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 a Just value if the first input is before the second, and Nothing otherwise. In the case that the value is a Just then it contains the Interval created by spanning the two inputs, or more precisely stated it contains the Interval 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 an Interval 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 a Just value if the first input meets the second, and Nothing otherwise. In the case that the value is a Just then it contains a PairedInterval with the data portion given by the data in the second argument to .+., and the Interval portion obtained by combining the two inputs (more precisely stated it contains the Interval 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 a Just value if the first input is before the second, and Nothing otherwise. In the case that the value is a Just then it contains the PairedInterval with the data portion given by the mempty method for the Monoid instance of the data type of PairedIntervals, and the Interval portion obtained by spanning the two inputs (or more precisely stated it contains the Interval 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 a PairedInterval with regards to the output type, where the data is the result of applying <> to the data portions of the two inputs, and where the Interval is such that the starting point is the earlier of the two starting points of the embedded Intervals and the ending point is the later of the two ending points of the embedded Intervals.

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

Interval-algebra 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 an Intervallic's starting point "to the left." The inputs are a duration and an Intervallic value.
expandr moves an Intervallic's ending point "to the right." The inputs are a duration and an Intervallic value.
expand moves an Intervallic's starting point "to the left" and ending point "to the right." The inputs are two durations and an Intervallic 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 input Intervallic value. The inputs are a duration and an Intervallic value.
endervalFromBegin creates an interval that has the same ending point as the starting point of an input Intervallic value. The inputs are a duration and an Intervallic value.
momentize creates an interval with the minimum duration for the corresponding IntervalSizeable instance that has the same starting point as the starting point of an input Intervallic value. The input is an Intervallic 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 diffs the starting point from the first input from both the starting and ending point of the second input.
shiftfromEnd is similar to shiftfromBegin except that it applies the diff 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 Days.

print [iv2to4, iv5to8]
---> [(2, 4),(5, 8)]

print ivDay
---> (1967-01-18, 1967-01-24)

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 right-hand 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)

Table 2. Predicates of interval relations
Name	Definition	Example
`meets`	`end x == begin y`	iv0to2 `meets` iv2to5
`metBy`	`end y == begin x`	iv2to5 `metBy` iv0to2
`precedes`	`end x < begin y`	iv0to2 `precedes` iv5to8
`precededBy`	`end y < begin x`	iv5to8 `precededBy` iv0to2
`overlaps`	`begin x < begin y && end x < end y && end x > begin y`	iv3to6 `overlaps` iv5to8
`overlappedBy`	`begin y < begin x && end y < end x && end y > begin x`	iv5to8 `overlaps` iv3to6
`finishes`	`begin x > begin y && end x == end y`	iv6to8 `finishes` iv5to8
`finishedBy`	`begin y > begin x && end y == end x`	iv5to8 `finishedBy` iv6to8
`contains`	`begin y > begin x && end y < end x`	iv3to6 `contains` iv4to5
`during`	`begin x > begin y && end x < end y`	iv4to5 `during` iv3to6
`starts`	`begin x == begin y && end x < end y`	iv2to4 `starts` iv2to5
`startedBy`	`begin y == begin x && end y < end x`	iv2to5 `startedBy` iv2to4

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 fine-grained, and often the relationships we would like to use to describe pairs of intervals are compositions of the fundamental relations. For this reason, interval-algebra provides some built-in relations composed of multiple fundamental relations, as well as facilities for defining your own composite relations.

Built-in composite relations

The variables in the following table each have the type Set IntervalRelation.

Table 3. Built-in composite relations
Name	Relations
`disjointRelations`	`Before`, `After`, `Meets`, `MetBy`
`withinRelations`	`Starts`, `During`, `Finishes`, `Equals`
`StrictWithinRelations`	`Starts`, `During`, `Finishes`
`intervalRelations`	Every fundamental relation

Additional points of note:

disjointRelations corresponds to the disjoint predicate
withinRelations corresponds to the enclosedBy/within predicates
strictWithinRelations doesn’t currently correspond to any built-in predicates
intervalRelations is useful if you want to create a large composite relation by removing a few relations (but also see complement)

Built-in composite predicates

Table 4. Built-in composite predicates
Name	Definition
`disjoint`	Does one of the relations hold: `Before`, `After`, `Meets`, `MetBy`?
`notDisjoint` (a synonym of `concur`)	Do none of the relations hold: `Before`, `After`, `Meets`, `MetBy`?
`concur` (a synonym of `notDisjoint`)	Do none of the relations hold: `Before`, `After`, `Meets`, `MetBy`?
`encloses`	Does one of the relations hold: `StartedBy`, `Contains`, `FinishedBy`, `Equals`?
`enclosedby` (a synonym of `within`)	Does one of the relations hold: `Starts`, `During`, `Finishes`, `Equals`?
`within` (a synonym of `enclosedby`)	Does one of the relations hold: `Starts`, `During`, `Finishes`, `Equals`?

Additional points of note:

The disjoint and notDisjoint/concur predicates are complements of each other in the sense that x `disjoint` y and not (x `notDisjoint` y) evalute to the same value for any pair of x and y.
The encloses and enclosedBy/within predicates are duals of each other in the sense that x `encloses` y and y `enclosedBy` x evalute to the same value for any pair of x and y.

Constructing custom composite relations

The following examples demonstrate some approaches for constructing Set IntervalRelations.

-- 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 interval-algebra 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 new-to-market 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 re-enters 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 Integers (and hence the corresponding durations are also Integers), 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 of StudyEvents that are assumed to all correspond to a given subject, and to be complete in the sense that there are no other StudyEvents 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 and Diagnosis 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 and Diagnosis 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 at-a-time. 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}