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

Methods

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

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

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

Defined in IntervalAlgebra

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, Show a) => Intervallic Interval a

Defined in IntervalAlgebra

Methods

getInterval :: Interval a -> Interval a

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

begin :: Interval a -> a

end :: Interval a -> a

Eq a => Eq (Interval a)

Defined in IntervalAlgebra

Methods

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

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

(Eq (Interval a), Intervallic Interval 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 Interval 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]

class (Ord a, Show 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

Minimal complete definition

getInterval, setInterval

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.

begin :: i a -> a

Access the endpoints of an i a .

end :: i a -> a

Access the endpoints of an i a .

Instances

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

Defined in IntervalAlgebra

Methods

getInterval :: Interval a -> Interval a

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

begin :: Interval a -> a

end :: Interval a -> a

(Ord a, Show 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

begin :: PairedInterval b a -> a

end :: PairedInterval b a -> a

Create new intervals

parseInterval :: (Show a, Ord a) => a -> a -> Either String (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

Meets

meets

MetBy

metBy

Before

before

After

after

Overlaps

overlaps

OverlappedBy

overlappedBy

Starts

starts

StartedBy

startedBy

Finishes

finishes

FinishedBy

finishedBy

During

during

Contains

contains

Equals

equals

Instances

Bounded IntervalRelation

Defined in IntervalAlgebra

Methods

minBound :: IntervalRelation

maxBound :: IntervalRelation

Enum IntervalRelation

Defined in IntervalAlgebra

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

Methods

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

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

Ord IntervalRelation

Defined in IntervalAlgebra

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

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

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

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

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.

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.

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 an Interval.

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, Show a) => IntervalCombinable Interval a

Defined in IntervalAlgebra

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, Show 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 (Show a, 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

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

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

Defined in IntervalAlgebra

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