IntervalAlgebra.Core

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 three typeclasses designed to separate concerns of constructing, relating, and combining types that contain Intervals:

1. Intervallic provides an interface to the data structures which contain an Interval.
2. IntervalCombinable provides an interface to methods of combining two Intervals.
3. IntervalSizeable provides methods for measuring and modifying the size of an interval.

Intervals

data Interval a

An Interval a is a pair \( (x, y) \text{ such that } x < y\). To create intervals use the parseInterval, beginerval, or enderval functions.

Instances

Functor Interval

Defined in IntervalAlgebra.Core

Methods

fmap :: (a -> b) -> Interval a -> Interval b

(<$) :: a -> Interval b -> Interval a

Ord a => IntervalCombinable Interval a

Defined in IntervalAlgebra.Core

Methods

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

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

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

Ord a => Intervallic Interval a

Defined in IntervalAlgebra.Core

Methods

getInterval :: Interval a -> Interval a

setInterval :: Interval a -> Interval a -> Interval a

Eq a => Eq (Interval a)

Defined in IntervalAlgebra.Core

Methods

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

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

Ord a => Ord (Interval a)

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

Defined in IntervalAlgebra.Core

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

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

Defined in IntervalAlgebra.Core

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

Defined in IntervalAlgebra.Arbitrary

Methods

arbitrary :: Gen (Interval UTCTime)

shrink :: Interval UTCTime -> [Interval UTCTime]

Arbitrary (Interval Day)

Defined in IntervalAlgebra.Arbitrary

Methods

arbitrary :: Gen (Interval Day)

shrink :: Interval Day -> [Interval Day]

class Ord a => Intervallic i a where

The Intervallic typeclass defines how to get and set the Interval content of a data structure. It also includes functions for getting the endpoints of the Interval via begin and end.

>>> getInterval (Interval (0, 10))
(0, 10)

>>> begin (Interval (0, 10))
0

>>> end (Interval (0, 10))
10

Methods

getInterval :: i a -> Interval a

Get the interval from an i a.

setInterval :: i a -> Interval a -> i a

Set the interval in an i a.

Instances

Ord a => Intervallic Interval a

Defined in IntervalAlgebra.Core

Methods

getInterval :: Interval a -> Interval a

setInterval :: Interval a -> Interval a -> Interval a

Ord a => Intervallic (PairedInterval b) a

Defined in IntervalAlgebra.PairedInterval

Methods

getInterval :: PairedInterval b a -> Interval a

setInterval :: PairedInterval b a -> Interval a -> PairedInterval b a

newtype ParseErrorInterval

A type identifying interval parsing errors.

Constructors

ParseErrorInterval String

Instances

Eq ParseErrorInterval

Defined in IntervalAlgebra.Core

Methods

(==) :: ParseErrorInterval -> ParseErrorInterval -> Bool

(/=) :: ParseErrorInterval -> ParseErrorInterval -> Bool

Show ParseErrorInterval

Defined in IntervalAlgebra.Core

Methods

showsPrec :: Int -> ParseErrorInterval -> ShowS

show :: ParseErrorInterval -> String

showList :: [ParseErrorInterval] -> ShowS

begin :: Intervallic i a => i a -> a

Access the endpoints of an i a .

end :: Intervallic i a => i a -> a

Access the endpoints of an i a .

Create new intervals

parseInterval :: (Show a, Ord a) => a -> a -> Either ParseErrorInterval (Interval a)

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

>>> parseInterval 0 1
Right (0, 1)

>>> parseInterval 1 0
Left "0<1"

beginerval

Arguments

:: IntervalSizeable a b

=> b

duration to add to the begin

-> a

the begin point of the Interval

-> Interval a

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

>>> beginerval (0::Int) (0::Int)
(0, 1)

>>> beginerval (1::Int) (0::Int)
(0, 1)

>>> beginerval (2::Int) (0::Int)
(0, 2)

enderval

Arguments

:: IntervalSizeable a b

=> b

duration to subtract from the end

-> a

the end point of the Interval

-> Interval a

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

>>> enderval (0::Int) (0::Int)
(-1, 0)

>>> enderval (1::Int) (0::Int)
(-1, 0)

>>> enderval (2::Int) (0::Int)
(-2, 0)

Modify intervals

expand

Arguments

:: (IntervalSizeable a b, Intervallic i a)

=> b

duration to subtract from the begin

-> b

duration to add to the end

-> i a

-> i a

Resize an i 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.

>>> expand 0 0 (Interval (0::Int, 2::Int))
(0, 2)

>>> expand 1 1 (Interval (0::Int, 2::Int))
(-1, 3)

expandl :: (IntervalSizeable a b, Intervallic i a) => b -> i a -> i a

Expands an i a to "left".

>>> expandl 2 (Interval (0::Int, 2::Int))
(-2, 2)

expandr :: (IntervalSizeable a b, Intervallic i a) => b -> i a -> i a

Expands an i a to "right".

>>> expandr 2 (Interval (0::Int, 2::Int))
(0, 4)

Interval Algebra

Interval Relations and Predicates

data IntervalRelation

The IntervalRelation type and the associated predicate functions enumerate the thirteen possible ways that two Interval objects may relate according to Allen's interval algebra. Constructors are shown with their corresponding predicate function.

Constructors

Before

before

Meets

meets

Overlaps

overlaps

FinishedBy

finishedBy

Contains

contains

Starts

starts

Equals

equals

StartedBy

startedBy

During

during

Finishes

finishes

OverlappedBy

overlappedBy

MetBy

metBy

After

after

Instances

Bounded IntervalRelation

Defined in IntervalAlgebra.Core

Methods

minBound :: IntervalRelation

maxBound :: IntervalRelation

Enum IntervalRelation

Defined in IntervalAlgebra.Core

Methods

succ :: IntervalRelation -> IntervalRelation

pred :: IntervalRelation -> IntervalRelation

toEnum :: Int -> IntervalRelation

fromEnum :: IntervalRelation -> Int

enumFrom :: IntervalRelation -> [IntervalRelation]

enumFromThen :: IntervalRelation -> IntervalRelation -> [IntervalRelation]

enumFromTo :: IntervalRelation -> IntervalRelation -> [IntervalRelation]

enumFromThenTo :: IntervalRelation -> IntervalRelation -> IntervalRelation -> [IntervalRelation]

Eq IntervalRelation

Defined in IntervalAlgebra.Core

Methods

(==) :: IntervalRelation -> IntervalRelation -> Bool

(/=) :: IntervalRelation -> IntervalRelation -> Bool

Ord IntervalRelation

Defined in IntervalAlgebra.Core

Methods

compare :: IntervalRelation -> IntervalRelation -> Ordering

(<) :: IntervalRelation -> IntervalRelation -> Bool

(<=) :: IntervalRelation -> IntervalRelation -> Bool

(>) :: IntervalRelation -> IntervalRelation -> Bool

(>=) :: IntervalRelation -> IntervalRelation -> Bool

max :: IntervalRelation -> IntervalRelation -> IntervalRelation

min :: IntervalRelation -> IntervalRelation -> IntervalRelation

Show IntervalRelation

Defined in IntervalAlgebra.Core

Methods

showsPrec :: Int -> IntervalRelation -> ShowS

show :: IntervalRelation -> String

showList :: [IntervalRelation] -> ShowS

Meets, Metby

x `meets` y
y `metBy` x

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

meets :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x meets y? Is x metBy y?

metBy :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x meets y? Is x metBy y?

Before, After

x `before` y
y `after` x

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

before :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Is x before y? Is x after y?

after :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Is x before y? Is x after y?

Overlaps, OverlappedBy

x `overlaps` y
y `overlappedBy` x

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

overlaps :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x overlap y? Is x overlapped by y?

overlappedBy :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x overlap y? Is x overlapped by y?

Finishes, FinishedBy

x `finishes` y
y `finishedBy` x

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

finishedBy :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x finish y? Is x finished by y?

finishes :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x finish y? Is x finished by y?

During, Contains

x `during` y
y `contains` x

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

contains :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Is x during y? Does x contain y?

during :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Is x during y? Does x contain y?

Starts, StartedBy

x `starts` y
y `startedBy` x

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

starts :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x start y? Is x started by y?

startedBy :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x start y? Is x started by y?

Equal

x `equal` y
y `equal` x

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

equals :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x equal y?

Additional predicates and utilities

precedes :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Is x before y? Is x after y?

precededBy :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Is x before y? Is x after y?

disjoint :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

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

notDisjoint :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Are x and y not disjoint (concur); i.e. do they share any support? This is the complement of disjoint.

concur :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Are x and y not disjoint (concur); i.e. do they share any support? This is the complement of disjoint.

within :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Is x entirely *within* (enclosed by) the endpoints of y? That is, during, starts, finishes, or equals?

enclose :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Does x enclose y? That is, is y within x?

enclosedBy :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a)

Is x entirely *within* (enclosed by) the endpoints of y? That is, during, starts, finishes, or equals?

(<|>) :: (Intervallic i0 a, Intervallic i1 a) => ComparativePredicateOf2 (i0 a) (i1 a) -> ComparativePredicateOf2 (i0 a) (i1 a) -> ComparativePredicateOf2 (i0 a) (i1 a)

Operator for composing the union of two predicates

predicate :: (Intervallic i0 a, Intervallic i1 a) => Set IntervalRelation -> ComparativePredicateOf2 (i0 a) (i1 a)

Forms a predicate function from the union of a set of IntervalRelations.

unionPredicates :: [ComparativePredicateOf2 a b] -> ComparativePredicateOf2 a b

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

disjointRelations :: Set IntervalRelation

The set of IntervalRelation meaning two intervals are disjoint.

withinRelations :: Set IntervalRelation

The set of IntervalRelation meaning one interval is within the other.

type ComparativePredicateOf1 a = a -> a -> Bool

Defines a predicate of two objects of type a.

type ComparativePredicateOf2 a b = a -> b -> Bool

Defines a predicate of two object of different types.

beginervalFromEnd

Arguments

:: (IntervalSizeable a b, Intervallic i a)

=> b

duration to add to the end

-> i a

the i a from which to get the end

-> Interval a

Creates a new Interval from the end of an i a.

endervalFromBegin

Arguments

:: (IntervalSizeable a b, Intervallic i a)

=> b

duration to subtract from the begin

-> i a

the i a from which to get the begin

-> Interval a

Creates a new Interval from the begin of an i a.

beginervalMoment :: IntervalSizeable a b => a -> Interval a

Safely creates a new Interval with moment length with begin at x

>>> beginervalMoment (10 :: Int)
(10, 11)

endervalMoment :: IntervalSizeable a b => a -> Interval a

Safely creates a new Interval with moment length with end at x

>>> endervalMoment (10 :: Int)
(9, 10)

diffFromBegin :: (IntervalSizeable a b, Functor i1, Intervallic i0 a) => i0 a -> i1 a -> i1 b

Modifies the endpoints of second argument's interval by taking the difference from the first's input's begin. >>> diffFromBegin (Interval ((5::Int), 6)) (Interval (10, 15)) (5, 10)

>>> diffFromBegin (Interval ((1::Int), 2)) (Interval (3, 15))
(2, 14)

diffFromEnd :: (IntervalSizeable a b, Functor i1, Intervallic i0 a) => i0 a -> i1 a -> i1 b

Modifies the endpoints of second argument's interval by taking the difference from the first's input's end. >>> diffFromEnd (Interval ((5::Int), 6)) (Interval (10, 15)) (4, 9)

>>> diffFromEnd (Interval ((1::Int), 2)) (Interval (3, 15))
(1, 13)

momentize :: (IntervalSizeable a b, Intervallic i a) => i a -> i a

Changes the duration of an Intervallic value to a moment starting at the begin of the interval.

>>> momentize (Interval (6, 10))
(6, 7)

Algebraic operations

intervalRelations :: Set IntervalRelation

The Set of all IntervalRelations.

relate :: (Intervallic i0 a, Intervallic i1 a) => i0 a -> i1 a -> IntervalRelation

Compare two i a to determine their IntervalRelation.

>>> relate (Interval (0::Int, 1)) (Interval (1, 2))
Meets

>>> relate (Interval (1::Int, 2)) (Interval (0, 1))
MetBy

compose :: IntervalRelation -> IntervalRelation -> Set IntervalRelation

Compose two interval relations according to the rules of the algebra. The rules are enumerated according to this table.

complement :: Set IntervalRelation -> Set IntervalRelation

Finds the complement of a Set IntervalRelation.

union :: Set IntervalRelation -> Set IntervalRelation -> Set IntervalRelation

Find the union of two Sets of IntervalRelations.

intersection :: Set IntervalRelation -> Set IntervalRelation -> Set IntervalRelation

Find the intersection of two Sets of IntervalRelations.

converse :: Set IntervalRelation -> Set IntervalRelation

Find the converse of a Set IntervalRelation.

Combine two intervals

class Intervallic i a => IntervalCombinable i a where

The IntervalCombinable typeclass provides methods for (possibly) combining two i as to form a Maybe i a, or in case of ><, a possibly different Intervallic type.

Minimal complete definition

(><), (<+>)

Methods

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

Maybe form a new i a by the union of two i as that meets.

(><) :: i a -> i a -> Maybe (i 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 (i a)), Applicative f) => i a -> i a -> f (i 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 (left) folding over an *ordered* container of Intervals and combining intervals when x is *not* before y.

Instances

Ord a => IntervalCombinable Interval a

Defined in IntervalAlgebra.Core

Methods

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

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

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

(Ord a, Eq b, Monoid b) => IntervalCombinable (PairedInterval b) a

Defined in IntervalAlgebra.PairedInterval

Methods

(.+.) :: PairedInterval b a -> PairedInterval b a -> Maybe (PairedInterval b a)

(><) :: PairedInterval b a -> PairedInterval b a -> Maybe (PairedInterval b a)

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

extenterval :: Intervallic i a => i a -> i a -> Interval a

Creates a new Interval spanning the extent x and y.

>>> extenterval (Interval (0, 1)) (Interval (9, 10))
(0, 10)

Measure an interval

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

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

Minimal complete definition

add, diff

Methods

moment :: b

The smallest duration for an 'Interval a'.

moment' :: Intervallic i a => i a -> b

Gives back a moment based on the input's type.

duration :: Intervallic i a => i a -> b

Determine the duration of an 'i 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.

Instances

IntervalSizeable Int Int

Defined in IntervalAlgebra.Core

Methods

moment :: Int

moment' :: Intervallic i Int => i Int -> Int

duration :: Intervallic i Int => i Int -> Int

add :: Int -> Int -> Int

diff :: Int -> Int -> Int

IntervalSizeable Integer Integer

Defined in IntervalAlgebra.Core

Methods

moment :: Integer

moment' :: Intervallic i Integer => i Integer -> Integer

duration :: Intervallic i Integer => i Integer -> Integer

add :: Integer -> Integer -> Integer

diff :: Integer -> Integer -> Integer

IntervalSizeable UTCTime NominalDiffTime

Note that the moment of this instance is a Pico

Defined in IntervalAlgebra.Core

Methods

moment :: NominalDiffTime

moment' :: Intervallic i UTCTime => i UTCTime -> NominalDiffTime

duration :: Intervallic i UTCTime => i UTCTime -> NominalDiffTime

add :: NominalDiffTime -> UTCTime -> UTCTime

diff :: UTCTime -> UTCTime -> NominalDiffTime

IntervalSizeable Day Integer

Defined in IntervalAlgebra.Core

Methods

moment :: Integer

moment' :: Intervallic i Day => i Day -> Integer

duration :: Intervallic i Day => i Day -> Integer

add :: Integer -> Day -> Day

diff :: Day -> Day -> Integer