IntervalAlgebra

The IntervalAlgebra module provides data types and related classes for the interval-based temporal logic described in Allen (1983) and axiomatized in Allen and Hayes (1987).

A good primer on Allen's algebra can be found here.

Design

The module is built around five typeclasses designed to separate concerns of constructing, relating, and combining Intervals:

1. Intervallic provides an interface to the data structure of an Interval, defining how an Interval a is constructed.
2. IntervalAlgebraic provides an interface to the IntervalRelations, the workhorse of Allen's temporal logic.
3. IntervalCombinable provides an interface to methods of combining two Intervals.
4. IntervalSizeable and the related Moment provides methods for measuring and modifying the size of an interval.
5. IntervalFilterable provides methods for filtering Filterable collections of intervals.

An advantage of nested typeclass design is that developers can define an Interval of type a with just the amount of structure that they need.

Total Ordering of Intervals

The modules makes the (opinionated) choice of a total ordering for Intervallic Intervals. Namely, the ordering is based on first ordering the begins then the ends.

Development

This module is under development and the API may change in the future.

Classes

class (Ord a, Show a) => Intervallic a where

The Intervallic typeclass specifies how an Interval as is constructed. It also includes functions for getting the begin and end of an Interval a.

Minimal complete definition

Nothing

Methods

parseInterval :: a -> a -> Either String (Interval a)

Safely parse a pair of as to create an Interval a.

unsafeInterval :: a -> a -> Interval a

Create a new Interval a. This function is not safe as it does not enforce that \(x < y\). Use with caution. It is meant to be helper function in early prototyping of this package. This function may be deprecated in future releases.

begin :: Interval a -> a

Access the ends of an Interval a .

end :: Interval a -> a

Access the ends of an Interval a .

Instances

Intervallic Int

Defined in IntervalAlgebra

Methods

parseInterval :: Int -> Int -> Either String (Interval Int)

unsafeInterval :: Int -> Int -> Interval Int

begin :: Interval Int -> Int

end :: Interval Int -> Int

Intervallic Integer

Defined in IntervalAlgebra

Methods

parseInterval :: Integer -> Integer -> Either String (Interval Integer)

unsafeInterval :: Integer -> Integer -> Interval Integer

begin :: Interval Integer -> Integer

end :: Interval Integer -> Integer

Intervallic Day

Defined in IntervalAlgebra

Methods

parseInterval :: Day -> Day -> Either String (Interval Day)

unsafeInterval :: Day -> Day -> Interval Day

begin :: Interval Day -> Day

end :: Interval Day -> Day

class (Eq a, Intervallic a) => IntervalAlgebraic a where

The IntervalAlgebraic typeclass specifies the functions and relational operators for interval-based temporal logic. The typeclass defines the relational operators for intervals, plus other useful utilities such as disjoint, in', and composeRelations.

Minimal complete definition

Nothing

Methods

relate :: Interval a -> Interval a -> IntervalRelation

Compare two intervals to determine their IntervalRelation.

equals :: ComparativePredicateOf (Interval a)

Does x equal y?

meets :: ComparativePredicateOf (Interval a)

Does x meet y? Is y metBy x?

metBy :: ComparativePredicateOf (Interval a)

Does x meet y? Is y metBy x?

before :: ComparativePredicateOf (Interval a)

Is x before y? Is x after y?

after :: ComparativePredicateOf (Interval a)

Is x before y? Is x after y?

overlaps :: ComparativePredicateOf (Interval a)

Does x overlap y? Is x overlapped by y?

overlappedBy :: ComparativePredicateOf (Interval a)

Does x overlap y? Is x overlapped by y?

starts :: ComparativePredicateOf (Interval a)

Does x start y? Is x started by y?

startedBy :: ComparativePredicateOf (Interval a)

Does x start y? Is x started by y?

finishes :: ComparativePredicateOf (Interval a)

Does x finish y? Is x finished by y?

finishedBy :: ComparativePredicateOf (Interval a)

Does x finish y? Is x finished by y?

during :: ComparativePredicateOf (Interval a)

Is x during y? Does x contain y?

contains :: ComparativePredicateOf (Interval a)

Is x during y? Does x contain y?

composeRelations :: [ComparativePredicateOf (Interval a)] -> ComparativePredicateOf (Interval a)

Compose a list of interval relations with _or_ to create a new ComparativePredicateOf Interval a. For example, composeRelations [before, meets] creates a predicate function determining if one interval is either before or meets another interval.

disjoint :: ComparativePredicateOf (Interval a)

Are x and y disjoint (before, after, meets, or metBy)?

notDisjoint :: ComparativePredicateOf (Interval a)

Are x and y not disjoint; i.e. do they share any support?

in' :: ComparativePredicateOf (Interval a)

Is x contained in y in any sense (during, starts, finishes or equals?

Instances

IntervalAlgebraic Int

Defined in IntervalAlgebra

Methods

relate :: Interval Int -> Interval Int -> IntervalRelation

equals :: ComparativePredicateOf (Interval Int)

meets :: ComparativePredicateOf (Interval Int)

metBy :: ComparativePredicateOf (Interval Int)

before :: ComparativePredicateOf (Interval Int)

after :: ComparativePredicateOf (Interval Int)

overlaps :: ComparativePredicateOf (Interval Int)

overlappedBy :: ComparativePredicateOf (Interval Int)

starts :: ComparativePredicateOf (Interval Int)

startedBy :: ComparativePredicateOf (Interval Int)

finishes :: ComparativePredicateOf (Interval Int)

finishedBy :: ComparativePredicateOf (Interval Int)

during :: ComparativePredicateOf (Interval Int)

contains :: ComparativePredicateOf (Interval Int)

composeRelations :: [ComparativePredicateOf (Interval Int)] -> ComparativePredicateOf (Interval Int)

disjoint :: ComparativePredicateOf (Interval Int)

notDisjoint :: ComparativePredicateOf (Interval Int)

in' :: ComparativePredicateOf (Interval Int)

IntervalAlgebraic Integer

Defined in IntervalAlgebra

Methods

relate :: Interval Integer -> Interval Integer -> IntervalRelation

equals :: ComparativePredicateOf (Interval Integer)

meets :: ComparativePredicateOf (Interval Integer)

metBy :: ComparativePredicateOf (Interval Integer)

before :: ComparativePredicateOf (Interval Integer)

after :: ComparativePredicateOf (Interval Integer)

overlaps :: ComparativePredicateOf (Interval Integer)

overlappedBy :: ComparativePredicateOf (Interval Integer)

starts :: ComparativePredicateOf (Interval Integer)

startedBy :: ComparativePredicateOf (Interval Integer)

finishes :: ComparativePredicateOf (Interval Integer)

finishedBy :: ComparativePredicateOf (Interval Integer)

during :: ComparativePredicateOf (Interval Integer)

contains :: ComparativePredicateOf (Interval Integer)

composeRelations :: [ComparativePredicateOf (Interval Integer)] -> ComparativePredicateOf (Interval Integer)

disjoint :: ComparativePredicateOf (Interval Integer)

notDisjoint :: ComparativePredicateOf (Interval Integer)

in' :: ComparativePredicateOf (Interval Integer)

IntervalAlgebraic Day

Defined in IntervalAlgebra

Methods

relate :: Interval Day -> Interval Day -> IntervalRelation

equals :: ComparativePredicateOf (Interval Day)

meets :: ComparativePredicateOf (Interval Day)

metBy :: ComparativePredicateOf (Interval Day)

before :: ComparativePredicateOf (Interval Day)

after :: ComparativePredicateOf (Interval Day)

overlaps :: ComparativePredicateOf (Interval Day)

overlappedBy :: ComparativePredicateOf (Interval Day)

starts :: ComparativePredicateOf (Interval Day)

startedBy :: ComparativePredicateOf (Interval Day)

finishes :: ComparativePredicateOf (Interval Day)

finishedBy :: ComparativePredicateOf (Interval Day)

during :: ComparativePredicateOf (Interval Day)

contains :: ComparativePredicateOf (Interval Day)

composeRelations :: [ComparativePredicateOf (Interval Day)] -> ComparativePredicateOf (Interval Day)

disjoint :: ComparativePredicateOf (Interval Day)

notDisjoint :: ComparativePredicateOf (Interval Day)

in' :: ComparativePredicateOf (Interval Day)

class IntervalAlgebraic a => IntervalCombinable a where

The IntervalCombinable typeclass provides methods for (possibly) combining two Intervals.

Minimal complete definition

Nothing

Methods

(.+.) :: Interval a -> Interval a -> Maybe (Interval a)

Maybe form a new Interval by the union of two Intervals that meets.

extenterval :: Interval a -> Interval a -> Interval a

Creates a new Interval spanning the extent x and y

(><) :: Interval a -> Interval a -> Maybe (Interval a)

If x is before y, then form a new Just Interval a from the interval in the "gap" between x and y from the end of x to the begin of y. Otherwise, Nothing.

(<+>) :: (Semigroup (f (Interval a)), Applicative f) => Interval a -> Interval a -> f (Interval a)

If x is before y, return f x appended to f y. Otherwise, return extenterval of x and y (wrapped in f). This is useful for folding over an *ordered* container of Intervals and combining intervals when x is *not* before y.

Instances

IntervalCombinable Int

Defined in IntervalAlgebra

Methods

(.+.) :: Interval Int -> Interval Int -> Maybe (Interval Int)

extenterval :: Interval Int -> Interval Int -> Interval Int

(><) :: Interval Int -> Interval Int -> Maybe (Interval Int)

(<+>) :: (Semigroup (f (Interval Int)), Applicative f) => Interval Int -> Interval Int -> f (Interval Int)

IntervalCombinable Integer

Defined in IntervalAlgebra

Methods

(.+.) :: Interval Integer -> Interval Integer -> Maybe (Interval Integer)

extenterval :: Interval Integer -> Interval Integer -> Interval Integer

(><) :: Interval Integer -> Interval Integer -> Maybe (Interval Integer)

(<+>) :: (Semigroup (f (Interval Integer)), Applicative f) => Interval Integer -> Interval Integer -> f (Interval Integer)

IntervalCombinable Day

Defined in IntervalAlgebra

Methods

(.+.) :: Interval Day -> Interval Day -> Maybe (Interval Day)

extenterval :: Interval Day -> Interval Day -> Interval Day

(><) :: Interval Day -> Interval Day -> Maybe (Interval Day)

(<+>) :: (Semigroup (f (Interval Day)), Applicative f) => Interval Day -> Interval Day -> f (Interval Day)

class (Intervallic a, Num b, Ord b) => Moment a b | a -> b where

The Moment class fixes the smallest duration of an 'Intervallic a'.

Minimal complete definition

Nothing

Methods

moment :: b

Instances

Moment Int Int

Defined in IntervalAlgebra

Methods

moment :: Int

Moment Integer Integer

Defined in IntervalAlgebra

Methods

moment :: Integer

Moment Day Integer

Defined in IntervalAlgebra

Methods

moment :: Integer

class (Intervallic a, Moment a b, Num b, Ord b) => IntervalSizeable a b | a -> b where

The IntervalSizeable typeclass provides functions to determine the size of and to resize an 'Interval a'.

Minimal complete definition

add, diff

Methods

duration :: Interval a -> b

Determine the duration of an 'Interval a'.

add :: b -> a -> a

Shifts an a. Most often, the b will be the same type as a. But for example, if a is Day then b could be Int.

diff :: a -> a -> b

Takes the difference between two a to return a b.

expand :: b -> b -> Interval a -> Interval a

Resize an 'Interval a' to by expanding to "left" by l and to the "right" by r. In the case that l or r are less than a moment the respective endpoints are unchanged.

expandl :: b -> Interval a -> Interval a

Expands an 'Interval a' to left by i.

expandr :: b -> Interval a -> Interval a

Expands an 'Interval a' to right by i.

beginerval :: b -> a -> Interval a

Safely creates an 'Interval a' using x as the begin and adding max moment dur to x as the end.

enderval :: b -> a -> Interval a

Safely creates an 'Interval a' using x as the end and adding negate max moment dur to x as the begin.

Instances

IntervalSizeable Int Int

Defined in IntervalAlgebra

Methods

duration :: Interval Int -> Int

add :: Int -> Int -> Int

diff :: Int -> Int -> Int

expand :: Int -> Int -> Interval Int -> Interval Int

expandl :: Int -> Interval Int -> Interval Int

expandr :: Int -> Interval Int -> Interval Int

beginerval :: Int -> Int -> Interval Int

enderval :: Int -> Int -> Interval Int

IntervalSizeable Integer Integer

Defined in IntervalAlgebra

Methods

duration :: Interval Integer -> Integer

add :: Integer -> Integer -> Integer

diff :: Integer -> Integer -> Integer

expand :: Integer -> Integer -> Interval Integer -> Interval Integer

expandl :: Integer -> Interval Integer -> Interval Integer

expandr :: Integer -> Interval Integer -> Interval Integer

beginerval :: Integer -> Integer -> Interval Integer

enderval :: Integer -> Integer -> Interval Integer

IntervalSizeable Day Integer

Defined in IntervalAlgebra

Methods

duration :: Interval Day -> Integer

add :: Integer -> Day -> Day

diff :: Day -> Day -> Integer

expand :: Integer -> Integer -> Interval Day -> Interval Day

expandl :: Integer -> Interval Day -> Interval Day

expandr :: Integer -> Interval Day -> Interval Day

beginerval :: Integer -> Day -> Interval Day

enderval :: Integer -> Day -> Interval Day

class (Filterable f, IntervalAlgebraic a) => IntervalFilterable f a where

The IntervalFilterable class provides functions for filtering Filterables of Intervals based on IntervalAlgebraic relations.

Minimal complete definition

Nothing

Methods

filterMaker :: ComparativePredicateOf (Interval a) -> Interval a -> f (Interval a) -> f (Interval a)

Creates a function for filtering a Filterable of Interval as based on a predicate

filterOverlaps :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those that overlaps the Interval a in the first argument.

filterOverlappedBy :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those overlappedBy the Interval a in the first argument.

filterBefore :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those before the Interval a in the first argument.

filterAfter :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those after the Interval a in the first argument.

filterMeets :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those that meets the Interval a in the first argument.

filterMetBy :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those metBy the Interval a in the first argument.

filterDuring :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those during the Interval a in the first argument.

filterContains :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those that contains the Interval a in the first argument.

filterDisjoint :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those that are disjoint from the Interval a in the first argument.

filterNotDisjoint :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those that are notDisjoint from the Interval a in the first argument.

filterIn' :: Interval a -> f (Interval a) -> f (Interval a)

Filter a Filterable of Interval as to those that are in' the Interval a in the first argument.

Instances

IntervalFilterable [] Int

Defined in IntervalAlgebra

Methods

filterMaker :: ComparativePredicateOf (Interval Int) -> Interval Int -> [Interval Int] -> [Interval Int]

filterOverlaps :: Interval Int -> [Interval Int] -> [Interval Int]

filterOverlappedBy :: Interval Int -> [Interval Int] -> [Interval Int]

filterBefore :: Interval Int -> [Interval Int] -> [Interval Int]

filterAfter :: Interval Int -> [Interval Int] -> [Interval Int]

filterMeets :: Interval Int -> [Interval Int] -> [Interval Int]

filterMetBy :: Interval Int -> [Interval Int] -> [Interval Int]

filterDuring :: Interval Int -> [Interval Int] -> [Interval Int]

filterContains :: Interval Int -> [Interval Int] -> [Interval Int]

filterDisjoint :: Interval Int -> [Interval Int] -> [Interval Int]

filterNotDisjoint :: Interval Int -> [Interval Int] -> [Interval Int]

filterIn' :: Interval Int -> [Interval Int] -> [Interval Int]

IntervalFilterable [] Integer

Defined in IntervalAlgebra

Methods

filterMaker :: ComparativePredicateOf (Interval Integer) -> Interval Integer -> [Interval Integer] -> [Interval Integer]

filterOverlaps :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterOverlappedBy :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterBefore :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterAfter :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterMeets :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterMetBy :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterDuring :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterContains :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterDisjoint :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterNotDisjoint :: Interval Integer -> [Interval Integer] -> [Interval Integer]

filterIn' :: Interval Integer -> [Interval Integer] -> [Interval Integer]

IntervalFilterable [] Day

Defined in IntervalAlgebra

Methods

filterMaker :: ComparativePredicateOf (Interval Day) -> Interval Day -> [Interval Day] -> [Interval Day]

filterOverlaps :: Interval Day -> [Interval Day] -> [Interval Day]

filterOverlappedBy :: Interval Day -> [Interval Day] -> [Interval Day]

filterBefore :: Interval Day -> [Interval Day] -> [Interval Day]

filterAfter :: Interval Day -> [Interval Day] -> [Interval Day]

filterMeets :: Interval Day -> [Interval Day] -> [Interval Day]

filterMetBy :: Interval Day -> [Interval Day] -> [Interval Day]

filterDuring :: Interval Day -> [Interval Day] -> [Interval Day]

filterContains :: Interval Day -> [Interval Day] -> [Interval Day]

filterDisjoint :: Interval Day -> [Interval Day] -> [Interval Day]

filterNotDisjoint :: Interval Day -> [Interval Day] -> [Interval Day]

filterIn' :: Interval Day -> [Interval Day] -> [Interval Day]

Types

data Interval a

An Interval a is a pair of as \( (x, y) \text{ where } x < y\). The Intervallic class provides a safe parseInterval function that returns a Left error if \(y < x\) and unsafeInterval as constructor for creating an interval that may not be valid.

Instances

Eq a => Eq (Interval a)

Defined in IntervalAlgebra

Methods

(==) :: Interval a -> Interval a -> Bool

(/=) :: Interval a -> Interval a -> Bool

Intervallic a => Ord (Interval a)

Imposes a total ordering on Interval a based on first ordering the begins then the ends.

Defined in IntervalAlgebra

Methods

compare :: Interval a -> Interval a -> Ordering

(<) :: Interval a -> Interval a -> Bool

(<=) :: Interval a -> Interval a -> Bool

(>) :: Interval a -> Interval a -> Bool

(>=) :: Interval a -> Interval a -> Bool

max :: Interval a -> Interval a -> Interval a

min :: Interval a -> Interval a -> Interval a

(Intervallic a, Show a) => Show (Interval a)

Defined in IntervalAlgebra

Methods

showsPrec :: Int -> Interval a -> ShowS

show :: Interval a -> String

showList :: [Interval a] -> ShowS

Arbitrary (Interval Int)

Defined in IntervalAlgebra.Arbitrary

Methods

arbitrary :: Gen (Interval Int)

shrink :: Interval Int -> [Interval Int]

Arbitrary (Interval Day)

Defined in IntervalAlgebra.Arbitrary

Methods

arbitrary :: Gen (Interval Day)

shrink :: Interval Day -> [Interval Day]

data IntervalRelation

The IntervalRelation type enumerates the thirteen possible ways that two Interval a objects can relate according to the interval algebra.

Meets, Metby

x `meets` y
y `metBy` x

x: |-----|
y:       |-----| 

Before, After

x `before` y
y `after` x

x: |-----|  
y:          |-----|

Overlaps, OverlappedBy

x `overlaps` y
y `overlappedBy` x

x: |-----|
y:     |-----|

Starts, StartedBy

x `starts` y
y `startedBy` x

x: |---| 
y: |-----|

Finishes, FinishedBy

x `finishes` y
y `finishedBy` x

x:   |---| 
y: |-----|

During, Contains

x `during` y
y `contains` x

x:   |-| 
y: |-----|

Equal

x `equal` y
y `equal` x

x: |-----| 
y: |-----|

Instances

Read IntervalRelation

Defined in IntervalAlgebra

Methods

readsPrec :: Int -> ReadS IntervalRelation

readList :: ReadS [IntervalRelation]

readPrec :: ReadPrec IntervalRelation

readListPrec :: ReadPrec [IntervalRelation]

Show IntervalRelation

Defined in IntervalAlgebra

Methods

showsPrec :: Int -> IntervalRelation -> ShowS

show :: IntervalRelation -> String

showList :: [IntervalRelation] -> ShowS

type ComparativePredicateOf a = a -> a -> Bool

Defines a predicate of two objects of type a.