# interval-algebra
The `interval-algebra` package implements [Allen's interval
algebra](https://en.wikipedia.org/wiki/Allen%27s_interval_algebra) in
[Haskell](https://www.haskell.org), 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)](https://doi.org/10.1145/182.358434) and axiomatized in [Allen
and Hayes (1987)](https://doi.org/10.1111/j.1467-8640.1989.tb00329.x). A good
primer on Allen's algebra can be [found
here](https://thomasalspaugh.org/pub/fnd/allen.html).
## 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.
1. `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](test/IntervalAlgebraSpec.hs) that the functions of
the `IntervalAlgebraic` typeclass meets the axioms for _intervals_ (not points)
as laid out in [Allen and Hayes
(1987)](https://doi.org/10.1111/j.1467-8640.1989.tb00329.x).
## 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.