An implementation of Allen's interval algebra for temporal logic.

Please see the README on GitHub at https://github.com/novisci/interval-algebra

interval-algebra

The interval-algebra package implements Allen's interval algebra in Haskell, for a canonical representation of intervals as a pair of points representing a begin and an end. The main 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 provides an Interval type wrapping the most basic type of interval needed for the relation algebra defined in the papers cited above. Interval a wraps (a, a), giving the interval's begin and end points.

However, the module provides typeclasses to generalize an Interval and the interval algebra for temporal logic:

1. Iv provides an abstract interface for defining the 13 relations of the interval algebra. Instances are provided for the canonical Interval a, when a is an instance of Ord, as described in Allen 1983. However, the interval algebra can be used for temporal logic on "intervals" that are qualitative and not represented as pairs of points in an ordered set, as provided in examples of that paper.
2. PointedIv is an interface for types that, in effect, be cast to the canonical Interval.
3. SizedIv provides a generic interface for creating and manipulating PointedIv intervals. In particular, when the interval type also is an instance of Iv, it specifies class properties to ensure intervals created or altered via its methods are valid for the purpose using the interval algebra.
4. Intervallic provides an interface for data structures which contain an Interval, allowing the relation algebra to be performed relative to the Interval within. The PairedInterval defined here is the prototypical case.

The module defines instances of the classes above for Interval a, and only provides SizedIv (Interval a) instances for a few common a. See class documentation for examples of other possible use-cases. It also defines a variety of ways to construct valid Interval a values for supported point types a.

The loose naming convention is: "Bare" names such as starts or contains are generalized over Intervallic and their Iv* class counterparts start with iv, for example ivStarts and ivContains.

Axiom tests

The package includes tests that the functions of the IntervalAlgebraic typeclass meets the axioms for intervals (not points) as laid out in Allen and Hayes (1987).

Comparisons

interval-algebra differs from data-interval mainly in that it is more general and has as its starting point the relation algebra from Allen 1983. The latter package provides an interval type that is tied to the notion of an interval as a connected convex subset of the integer or real lines, differentiating for example between closed and open endpoints. It provides a Relation type codifying the 13 temporal relations from Allen 1983.

For use-cases where that structure is meaningful, data-interval might be a more natural choice. interval-algebra might be used instead when more abstract concepts are needed or there is no need for the notion of connectedness between the starting and ending points.

An important difference is that data-interval supports empty intervals. interval-algebra does not, since Allen's interval relations cannot be defined for such intervals.