Ranged-sets

Ranged Sets for Haskell
=======================

Ranged sets allow programming with sets of values that are described
by a list of ranges. A value is a member of the set if it lies within
one of the ranges. The ranges in a set are ordered and
non-overlapping, so the standard set operations can be implemented by
merge algorithms in O(n) time.

License
-------

Currently the Ranged Set library is under the BSD 3 license. This is
a very permissive license. I am hoping that Ranged Sets will
eventually become part of the Base library, and at that point the
implementation will have to be issued under the same license as the
rest of the library (which in practice probably means different
licenses for different compiler versions). As I understand it the BSD
3 license will allow this without me having to get either assignment
of copyright or explicit permission from everyone who submits
contributions.


Boundaries
----------

Module Data.Ranged.Boundaries defines the Boundary type. A boundary
divides an ordered type into values above and below the boundary. No
value can ever sit on a boundary.

Two boundaries are equal if they divide the values at the same point.
This definition of equality causes an implementation problem because
some types are "discrete". For instance there is no value between the
characters 'a' and 'b', or between the integers 3 and 4. However
there are values between 3.0 and 4.0. Similarly for strings, there
are values between "a" and "b" such as "aa", "ab", and so on. This is
important because "BoundaryAbove 3" is equal to "BoundaryBelow 4". 3
is below both boundaries, and 4 is above both. Hence they divide the
integers at the same place. But on the other hand "BoundaryAbove 3.0"
and "BoundaryBelow 4.0" are not equal because 3.5 is above the first
and below the second.

To solve this the DiscreteOrdered class is defined, which provides a
function "adjacent". Two values x1 and x3 are adjacent if x1 < x3 and
there does not exist an x2 such that x1 < x2 < x3. This provides the
distinction necessary for boundary equality to be defined for all
ordered types. The ordered types from the prelude are instances of
DiscreteOrdered, and others can be added by defining "adjacent". The
functions "enumAdjacent" and "boundedAdjacent" are provided for
instances of Enum and Bounded. Lists and tuples of DiscreteOrdered
types are also instances of DiscreteOrdered.

This approach was suggested by Ben Rudiak-Gould on
comp.lang.functional.

In theory the Float and Double types should be treated as enumerated
because they are held in fixed-length data fields, and hence must have
pairs of values that are adjacent. However they are treated as
continuous here for two reasons:

* The Float and Double types are practical approximations to Real
numbers, which are continuous. Hence it makes sense for Float
and Double to pretend to share this property.

* There is no standard way to determine the adjacency of Float and
Double values in Haskell. "succ 3.0" returns 4.0, which is not
appropriate here.


Ranges
------

Module Data.Ranged.Ranges defines the Range type. A range has a lower and an
upper Boundary.

Set-like operations are defined on ranges, but they return variable
numbers of results, and hence return either Maybe Range or [Range].


RangedSet
---------

Module Data.Ranged.RangedSet defines the RSet type. This is the
actual ranged set type. It is constructed from a list of ranges.
There are two functions to do this:

* makeRangedSet takes a finite list of ranges that may overlap or be
out of order. It sorts them and merges overlapping ranges using
the normaliseRangeList function.

* unsafeRangedSet takes a list of ranges that must be in order and not
overlapping. The behaviour of the resulting set is not defined if this
precondition is not met.

In theory the standard QuickCheck generator for RSet could generate an
arbitrary list of ranges and then normalise them, but in practice this
tends to produce a very small number of ranges because of the high
probability of overlaps. So instead an arbitrary list of boundaries
is generated and these are then sorted and paired off into
non-overlapping ranges.


Infinite Sets
-------------

In theory, thanks to lazy evaluation ranged sets can handle infinite
lists of ranges. These are known as "infinite sets". Note that this
is not the same as a set with a final upper bound of "AboveAll".

Unfortunately there is no simple way to guarantee that computations on
infinite sets will terminate. So infinite sets are not supported.

QuickCheck and Tests
--------------------

All the types in the Ranged Set library are instances of Arbitrary from
the QuickCheck library, and the source code includes a number of
important properties for Ranges and RSets defined using QuickCheck. These
can be treated as a formal specification of the properties of these types.

The tests can be run by going into the "tests" directory and saying
"make all". A coverage report is generated, and detailed HTML coverage will
be found in "tests/Report". "make clean" to delete all the generated files.