Ranged-sets-0.1.0: Ranged sets for HaskellContentsIndex
Data.Ranged.RangedSet
Contents
Ranged Set Type
Ranged Set construction functions and their Preconditions
Predicates
Set Operations
Useful Sets
QuickCheck Properties
Construction
Basic Operations
Some Identities and Inequalities
Synopsis
data RSet v
rSetRanges :: RSet v -> [Range v]
makeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v
unsafeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v
validRangeList :: DiscreteOrdered v => [Range v] -> Bool
normaliseRangeList :: DiscreteOrdered v => [Range v] -> [Range v]
rSingleton :: DiscreteOrdered v => v -> RSet v
rSetIsEmpty :: DiscreteOrdered v => RSet v -> Bool
(-?-) :: DiscreteOrdered v => RSet v -> v -> Bool
rSetHas :: DiscreteOrdered v => RSet v -> v -> Bool
(-<=-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubset :: DiscreteOrdered v => RSet v -> RSet v -> Bool
(-<-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubsetStrict :: DiscreteOrdered v => RSet v -> RSet v -> Bool
(-\/-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetUnion :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
(-/\-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetIntersection :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
(-!-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetDifference :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetNegation :: DiscreteOrdered a => RSet a -> RSet a
rSetEmpty :: DiscreteOrdered a => RSet a
rSetFull :: DiscreteOrdered a => RSet a
rSetUnfold :: DiscreteOrdered a => Boundary a -> (Boundary a -> Boundary a) -> (Boundary a -> Maybe (Boundary a)) -> RSet a
Ranged Set Type
data RSet v
An RSet (for Ranged Set) is a list of ranges. The ranges must be sorted and not overlap.
show/hide Instances
(Arbitrary v, DiscreteOrdered v, Show v) => Arbitrary (RSet v)
(DiscreteOrdered v, ??? v) => Eq (RSet v)
DiscreteOrdered a => Monoid (RSet a)
(DiscreteOrdered v, ??? v) => Show (RSet v)
rSetRanges :: RSet v -> [Range v]
Ranged Set construction functions and their Preconditions
makeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v
Create a new Ranged Set from a list of ranges. The list may contain ranges that overlap or are not in ascending order.
unsafeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v
Create a new Ranged Set from a list of ranges. validRangeList ranges must return True. This precondition is not checked.
validRangeList :: DiscreteOrdered v => [Range v] -> Bool
Determine if the ranges in the list are both in order and non-overlapping. If so then they are suitable input for the unsafeRangedSet function.
normaliseRangeList :: DiscreteOrdered v => [Range v] -> [Range v]
Rearrange and merge the ranges in the list so that they are in order and non-overlapping.
rSingleton :: DiscreteOrdered v => v -> RSet v
Create a Ranged Set from a single element.
Predicates
rSetIsEmpty :: DiscreteOrdered v => RSet v -> Bool
True if the set has no members.
(-?-) :: DiscreteOrdered v => RSet v -> v -> Bool
rSetHas :: DiscreteOrdered v => RSet v -> v -> Bool
True if the value is within the ranged set. Infix precedence is left 5.
(-<=-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubset :: DiscreteOrdered v => RSet v -> RSet v -> Bool

True if the first argument is a subset of the second argument, or is equal.

Infix precedence is left 5.

(-<-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool
rSetIsSubsetStrict :: DiscreteOrdered v => RSet v -> RSet v -> Bool

True if the first argument is a strict subset of the second argument.

Infix precedence is left 5.

Set Operations
(-\/-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetUnion :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
Set union for ranged sets. Infix precedence is left 6.
(-/\-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetIntersection :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
Set intersection for ranged sets. Infix precedence is left 7.
(-!-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
rSetDifference :: DiscreteOrdered v => RSet v -> RSet v -> RSet v
Set difference. Infix precedence is left 6.
rSetNegation :: DiscreteOrdered a => RSet a -> RSet a
Set negation.
Useful Sets
rSetEmpty :: DiscreteOrdered a => RSet a
The empty set.
rSetFull :: DiscreteOrdered a => RSet a
The set that contains everything.
rSetUnfold
:: DiscreteOrdered a
=> Boundary aA first lower boundary.
-> (Boundary a -> Boundary a)A function from a lower boundary to an upper boundary, which must return a result greater than the argument (not checked).
-> (Boundary a -> Maybe (Boundary a))A function from a lower boundary to Maybe the successor lower boundary, which must return a result greater than the argument (not checked).
-> RSet a
Construct a range set.
QuickCheck Properties
Construction

A normalised range list is valid for unsafeRangedSet 

 prop_validNormalised ls = validRangeList $ normaliseRangeList ls
    where types = ls :: [Range Double]

Iff a value is in a range list then it is in a ranged set constructed from that list. 

 prop_has ls v = (ls `rangeListHas` v) == rangedSet ls -?- v
Basic Operations

Iff a value is in either of two ranged sets then it is in the union of those two sets. 

 prop_union rs1 rs2 v =
    (rs1 -?- v || rs2 -?- v) == ((rs1 -\/- rs2) -?- v)

Iff a value is in both of two ranged sets then it is in the intersection of those two sets. 

 prop_intersection rs1 rs2 v =
    (rs1 -?- v && rs2 -?- v) == ((rs1 -/\- rs2) -?- v)

Iff a value is in ranged set 1 and not in ranged set 2 then it is in the difference of the two. 

 prop_difference rs1 rs2 v = 
    (rs1 -?- v && not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v)

Iff a value is not in a ranged set then it is in its negation. 

 prop_negation rs v = rs -?- v == not (rSetNegation rs -?- v)

A set that contains a value is not empty 

 prop_not_empty rs v = (rs -?- v) ==> not (rSetIsEmpty rs)
Some Identities and Inequalities

The empty set has no members. 

 prop_empty v = not (rSetEmpty -?- v)

The full set has every member. 

 prop_full v = rSetFull -?- v

The intersection of a set with its negation is empty. 

 prop_empty_intersection rs =
    rSetIsEmpty (rs -/\- rSetNegation rs)

The union of a set with its negation is full. 

 prop_full_union rs v =
    rSetIsFull (rs -\/- rSetNegation rs)

The union of two sets is the non-strict superset of both. 

 prop_union_superset rs1 rs2 =
    rs1 -<=- u && rs2 -<=- u 
    where
       u = rs1 -\/- rs2

The intersection of two sets is the non-strict subset of both. 

 prop_intersection_subset rs1 rs2 =
    i -<=- rs1 && i -<=- rs2
    where
       i = rs1 -/\- rs2

The difference of two sets intersected with the subtractand is empty. 

 prop_diff_intersect rs1 rs2 =
    rSetIsEmpty ((rs1 -!- rs2) -/\- rs2)

A set is the non-strict subset of itself. 

 prop_subset rs = rs -<=- rs

A set is not the strict subset of itself. 

 prop_strict_subset rs = not (rs -<- rs)

If rs1 - rs2 is not empty then the union of rs1 and rs2 will be a strict superset of rs2. 

 prop_union_strict_superset rs1 rs2 =
    (not $ rSetIsEmpty (rs1 -!- rs2))
    ==> (rs2 -<- (rs1 -\/- rs2))

Intersection commutes 

 prop_intersection_commutes rs1 rs2 =
    (rs1 -/\- rs2) == (rs2 -/\- rs1)

Union commutes 

 prop_union_commutes rs1 rs2 =
    (rs1 -\/- rs2) == (rs2 -\/- rs1)

Intersection associates 

 prop_intersection_associates rs1 rs2 rs3 =
    ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3))

Union associates 

 prop_union_associates rs1 rs2 rs3 =
    ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3))

De Morgan's Law for Intersection 

 prop_de_morgan_intersection rs1 rs2 =
    rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2)

De Morgan's Law for Union 

 prop_de_morgan_union rs1 rs2 =
    rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2)
Produced by Haddock version 0.8