# Ranged-sets

Ranged sets for Haskell http://code.haskell.org/ranged-sets

Latest on Hackage: | 0.3.0 |

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

BSD3 licensed by

**Paul Johnson**Maintained by

**paul@cogito.org.uk**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.

=======================

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.

## Changes

Version 0.0.2

-------------

Fixed the infinite loop with infinite sets, at least as far as possible.

Added lots more QuickCheck properties.

Added subset predicates.

Added infix operators.

Version 0.0.3

-------------

Removed support for infinite sets. They sometimes still work, but generally

are more trouble than they are worth. There is no simple set of rules for

client applications to guarantee termination.

Replaced the "deriving" clause for the Range type with instance declarations.

Empty ranges created with different bounds will now test as equal. All

empty ranges now compare as less than all non-empty ranges. "show" returns

a string such as "3.5 < x <= 4.6", or "x < 23".

Removed "maybeRange".

Changed "rangeIntersection" to return a "Range" instead of a "Maybe Range".

If the intersection is empty then it returns an empty range instead of

Nothing.

Renamed "rangeEmpty" to "rangeIsEmpty" for consistency with "rSetIsEmpty"

Added "emptyRange" and "fullRange"

Version 0.0.4

-------------

Added Monoid instances and singleton ranges, courtesy of Jean-Philippe

Bernardy.

Version 0.2.0

-------------

Reorganised and extended tests.

Added "rangeIsFull" predicate.

Version 0.2.1

-------------

Require QuickCheck < 2.

Version 0.3.0

-------------

Require QuickCheck >= 2.4. This changes the API for the Arbitrary and CoArbitrary

instances, so it gets a version number bump.

-------------

Fixed the infinite loop with infinite sets, at least as far as possible.

Added lots more QuickCheck properties.

Added subset predicates.

Added infix operators.

Version 0.0.3

-------------

Removed support for infinite sets. They sometimes still work, but generally

are more trouble than they are worth. There is no simple set of rules for

client applications to guarantee termination.

Replaced the "deriving" clause for the Range type with instance declarations.

Empty ranges created with different bounds will now test as equal. All

empty ranges now compare as less than all non-empty ranges. "show" returns

a string such as "3.5 < x <= 4.6", or "x < 23".

Removed "maybeRange".

Changed "rangeIntersection" to return a "Range" instead of a "Maybe Range".

If the intersection is empty then it returns an empty range instead of

Nothing.

Renamed "rangeEmpty" to "rangeIsEmpty" for consistency with "rSetIsEmpty"

Added "emptyRange" and "fullRange"

Version 0.0.4

-------------

Added Monoid instances and singleton ranges, courtesy of Jean-Philippe

Bernardy.

Version 0.2.0

-------------

Reorganised and extended tests.

Added "rangeIsFull" predicate.

Version 0.2.1

-------------

Require QuickCheck < 2.

Version 0.3.0

-------------

Require QuickCheck >= 2.4. This changes the API for the Arbitrary and CoArbitrary

instances, so it gets a version number bump.

Depends on:

comments powered byDisqus

A service provided by
FP Complete