The Range Data structure; it is capable of representing any type of range. This is the primary data structure in this library. Everything should be possible to convert back into this datatype. All ranges in this structure are inclusively bound.

Represents a bound at a particular value with a BoundType. There is no implicit understanding if this is a lower or upper bound, it could be either.

Represents a type of boundary.

A set of ranges represented as a merged, canonical list of non-overlapping Range values, with pre-built O(log n) membership, O(1) above, and O(1) below predicates.

Construct values with the operators (+=+, lbi, etc.) or with mergeRanges. Combine with (<>) or mconcat.

Semigroup: (<>) computes the set union and merges the result into canonical form.

>>> (1 +=+ 5 :: Ranges Integer) <> (3 +=+ 8)
Ranges [1 +=+ 8]

Monoid: mempty is the empty set. mconcat merges an entire list in a single pass, more efficiently than repeated (<>):

>>> mconcat [1 +=+ 5, 10 +=+ 15, 12 +=+ 20 :: Ranges Integer]
Ranges [1 +=+ 5,10 +=+ 20]

Use unRanges to extract the underlying list.

Mathematically equivalent to [x, y]. See SpanRange for the underlying constructor.

>>> 1 +=+ 5 :: Ranges Integer
Ranges [1 +=+ 5]

Mathematically equivalent to [x, y).

>>> 1 +=* 5 :: Ranges Integer
Ranges [1 +=* 5]

Mathematically equivalent to (x, y].

>>> 1 *=+ 5 :: Ranges Integer
Ranges [1 *=+ 5]

Mathematically equivalent to (x, y).

>>> 1 *=* 5 :: Ranges Integer
Ranges [1 *=* 5]

Mathematically equivalent to [x, ∞).

>>> lbi 5 :: Ranges Integer
Ranges [lbi 5]

Mathematically equivalent to (x, ∞).

Mathematically equivalent to (−∞, x].

Mathematically equivalent to (−∞, x).

The infinite range, covering all values.

Returns True if the value falls within the single range. Respects Inclusive and Exclusive bounds.

See inRanges for testing against a Ranges collection.

>>> inRange (SpanRange (Bound 1 Inclusive) (Bound 10 Inclusive)) (5 :: Integer)
True
>>> inRange (SpanRange (Bound 1 Inclusive) (Bound 10 Exclusive)) (10 :: Integer)
False

Returns True if the value is strictly above (greater than the upper bound of) the given range.

>>> aboveRange (SpanRange (Bound 1 Inclusive) (Bound 5 Inclusive)) (6 :: Integer)
True
>>> aboveRange (LowerBoundRange (Bound 0 Inclusive)) (6 :: Integer)
False

Returns True if the value is strictly below (less than the lower bound of) the given range.

>>> belowRange (SpanRange (Bound 1 Inclusive) (Bound 5 Inclusive)) (0 :: Integer)
True
>>> belowRange (UpperBoundRange (Bound 6 Inclusive)) (0 :: Integer)
False

Returns True if two ranges share at least one value.

>>> rangesOverlap (SpanRange (Bound 1 Inclusive) (Bound 5 Inclusive)) (SpanRange (Bound 3 Inclusive) (Bound 7 Inclusive) :: Range Integer)
True
>>> rangesOverlap (SpanRange (Bound 1 Inclusive) (Bound 5 Exclusive)) (SpanRange (Bound 5 Inclusive) (Bound 7 Inclusive) :: Range Integer)
False

Returns True if two ranges touch at a single exclusive boundary but share no values.

>>> rangesAdjoin (SpanRange (Bound 1 Inclusive) (Bound 5 Exclusive)) (SpanRange (Bound 5 Inclusive) (Bound 7 Inclusive) :: Range Integer)
True
>>> rangesAdjoin (SpanRange (Bound 1 Inclusive) (Bound 5 Inclusive)) (SpanRange (Bound 3 Inclusive) (Bound 7 Inclusive) :: Range Integer)
False

Returns True if the value falls within any of the given ranges.

The membership predicate is pre-built when the Ranges value is constructed, so each call is O(log n) in the number of spans. Partial application is idiomatic:

let memberOf = inRanges myRanges
filter memberOf largeList

>>> inRanges (1 +=+ 10 <> 20 +=+ 30 :: Ranges Integer) 5
True
>>> inRanges (1 +=+ 10 <> 20 +=+ 30 :: Ranges Integer) 15
False

Returns True if the value is strictly above all of the given ranges.

This predicate is O(1): the answer is determined by the last element of the canonical range list (which has the largest upper bound), cached at construction time.

>>> aboveRanges (1 +=+ 5 <> 10 +=+ 15 :: Ranges Integer) 20
True
>>> aboveRanges (1 +=+ 5 <> lbi 10 :: Ranges Integer) 20
False

Returns True if the value is strictly below all of the given ranges.

This predicate is O(1): the answer is determined by the first element of the canonical range list (which has the smallest lower bound), cached at construction time.

>>> belowRanges (5 +=+ 10 <> 20 +=+ 30 :: Ranges Integer) 1
True
>>> belowRanges (ubi 10 <> 20 +=+ 30 :: Ranges Integer) 1
False

Canonicalise a raw list of Range values into a Ranges. Overlapping ranges are merged; the result is sorted and non-overlapping.

>>> mergeRanges [LowerBoundRange (Bound 12 Inclusive), SpanRange (Bound 1 Inclusive) (Bound 10 Inclusive), SpanRange (Bound 5 Inclusive) (Bound 15 Inclusive) :: Range Integer]
Ranges [lbi 1]

Set union. Equivalent to (<>).

>>> union (1 +=+ 10) (5 +=+ 15 :: Ranges Integer)
Ranges [1 +=+ 15]

Set intersection. Returns only values present in both.

>>> intersection (1 +=+ 10) (5 +=+ 15 :: Ranges Integer)
Ranges [5 +=+ 10]

Set difference: values in the first Ranges not in the second.

>>> difference (1 +=+ 10) (5 +=+ 15 :: Ranges Integer)
Ranges [1 +=* 5]

Complement: all values not covered by the given Ranges. invert . invert == id.

>>> invert (1 +=* 10 <> 15 *=+ 20 :: Ranges Integer)
Ranges [ube 1,10 +=+ 15,lbe 20]

Instantiate all values covered by the ranges as a list. Warning: not efficient. Prefer inRanges for membership tests. Combine with take to avoid evaluating infinite ranges.

>>> take 5 . fromRanges $ (1 +=+ 10 :: Ranges Integer)
[1,2,3,4,5]

>>> take 6 . fromRanges $ (1 +=+ 3 :: Ranges Integer) <> (10 +=+ 12)
[1,10,2,11,3,12]

Join adjacent ranges that are contiguous for Enum types. For example, [1 +=+ 5, 6 +=+ 10] collapses to [1 +=+ 10] for Integer because there is no integer between 5 and 6.

>>> joinRanges (mconcat [1 +=+ 5, 6 +=+ 10] :: Ranges Integer)
Ranges [1 +=+ 10]