Safe Haskell	Safe
Language	Haskell2010

Data.Ranged.RangedSet

Contents

Ranged Set Type
Ranged Set construction functions and their preconditions
Predicates
Set Operations
Useful Sets
QuickCheck Properties

Synopsis

data DiscreteOrdered v => 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
rSetUnfold :: DiscreteOrdered a => Boundary a -> (Boundary a -> Boundary a) -> (Boundary a -> Maybe (Boundary a)) -> RSet a
rSetIsEmpty :: DiscreteOrdered v => RSet v -> Bool
rSetIsFull :: 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
prop_validNormalised :: DiscreteOrdered a => [Range a] -> Bool
prop_has :: DiscreteOrdered a => [Range a] -> a -> Bool
prop_unfold :: Integer -> Bool
prop_union :: DiscreteOrdered a => RSet a -> RSet a -> a -> Bool
prop_intersection :: DiscreteOrdered a => RSet a -> RSet a -> a -> Bool
prop_difference :: DiscreteOrdered a => RSet a -> RSet a -> a -> Bool
prop_negation :: DiscreteOrdered a => RSet a -> a -> Bool
prop_not_empty :: DiscreteOrdered a => RSet a -> a -> Property
prop_empty :: DiscreteOrdered a => a -> Bool
prop_full :: DiscreteOrdered a => a -> Bool
prop_empty_intersection :: DiscreteOrdered a => RSet a -> Bool
prop_full_union :: DiscreteOrdered a => RSet a -> Bool
prop_union_superset :: DiscreteOrdered a => RSet a -> RSet a -> Bool
prop_intersection_subset :: DiscreteOrdered a => RSet a -> RSet a -> Bool
prop_diff_intersect :: DiscreteOrdered a => RSet a -> RSet a -> Bool
prop_subset :: DiscreteOrdered a => RSet a -> Bool
prop_strict_subset :: DiscreteOrdered a => RSet a -> Bool
prop_union_strict_superset :: DiscreteOrdered a => RSet a -> RSet a -> Property
prop_intersection_commutes :: DiscreteOrdered a => RSet a -> RSet a -> Bool
prop_union_commutes :: DiscreteOrdered a => RSet a -> RSet a -> Bool
prop_intersection_associates :: DiscreteOrdered a => RSet a -> RSet a -> RSet a -> Bool
prop_union_associates :: DiscreteOrdered a => RSet a -> RSet a -> RSet a -> Bool
prop_de_morgan_intersection :: DiscreteOrdered a => RSet a -> RSet a -> Bool
prop_de_morgan_union :: DiscreteOrdered a => RSet a -> RSet a -> Bool

Ranged Set Type

data DiscreteOrdered v => RSet v Source #

An RSet (for Ranged Set) is a list of ranges. The ranges must be sorted and not overlap.

Instances

DiscreteOrdered v => Eq (RSet v) Source #
Instance details Defined in Data.Ranged.RangedSet Methods (==) :: RSet v -> RSet v -> Bool # (/=) :: RSet v -> RSet v -> Bool #
(DiscreteOrdered v, Show v) => Show (RSet v) Source #
Instance details Defined in Data.Ranged.RangedSet Methods showsPrec :: Int -> RSet v -> ShowS # show :: RSet v -> String # showList :: [RSet v] -> ShowS #
DiscreteOrdered a => Semigroup (RSet a) Source #
Instance details Defined in Data.Ranged.RangedSet Methods (<>) :: RSet a -> RSet a -> RSet a # sconcat :: NonEmpty (RSet a) -> RSet a # stimes :: Integral b => b -> RSet a -> RSet a #
DiscreteOrdered a => Monoid (RSet a) Source #
Instance details Defined in Data.Ranged.RangedSet Methods mempty :: RSet a # mappend :: RSet a -> RSet a -> RSet a # mconcat :: [RSet a] -> RSet a #
(Arbitrary v, DiscreteOrdered v, Show v) => Arbitrary (RSet v) Source #
Instance details Defined in Data.Ranged.RangedSet Methods arbitrary :: Gen (RSet v) # shrink :: RSet v -> [RSet v] #
(CoArbitrary v, DiscreteOrdered v, Show v) => CoArbitrary (RSet v) Source #
Instance details Defined in Data.Ranged.RangedSet Methods coarbitrary :: RSet v -> Gen b -> Gen b #

rSetRanges :: RSet v -> [Range v] Source #

Ranged Set construction functions and their preconditions

makeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v Source #

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 Source #

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 Source #

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] Source #

Rearrange and merge the ranges in the list so that they are in order and non-overlapping.

rSingleton :: DiscreteOrdered v => v -> RSet v Source #

Create a Ranged Set from a single element.

rSetUnfold Source #

Arguments

:: DiscreteOrdered a
=> Boundary a	A 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). If ranges overlap then they will be merged.
-> RSet a

Construct a range set.

Predicates

rSetIsEmpty :: DiscreteOrdered v => RSet v -> Bool Source #

True if the set has no members.

rSetIsFull :: DiscreteOrdered v => RSet v -> Bool Source #

True if the negation of the set has no members.

(-?-) :: DiscreteOrdered v => RSet v -> v -> Bool infixl 5 Source #

True if the value is within the ranged set. Infix precedence is left 5.

rSetHas :: DiscreteOrdered v => RSet v -> v -> Bool Source #

True if the value is within the ranged set. Infix precedence is left 5.

(-<=-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool infixl 5 Source #

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

Infix precedence is left 5.

rSetIsSubset :: DiscreteOrdered v => RSet v -> RSet v -> Bool Source #

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 infixl 5 Source #

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

Infix precedence is left 5.

rSetIsSubsetStrict :: DiscreteOrdered v => RSet v -> RSet v -> Bool Source #

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 infixl 6 Source #

Set union for ranged sets. Infix precedence is left 6.

rSetUnion :: DiscreteOrdered v => RSet v -> RSet v -> RSet v Source #

Set union for ranged sets. Infix precedence is left 6.

(-/\-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v infixl 7 Source #

Set intersection for ranged sets. Infix precedence is left 7.

rSetIntersection :: DiscreteOrdered v => RSet v -> RSet v -> RSet v Source #

Set intersection for ranged sets. Infix precedence is left 7.

(-!-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v infixl 6 Source #

Set difference. Infix precedence is left 6.

rSetDifference :: DiscreteOrdered v => RSet v -> RSet v -> RSet v Source #

Set difference. Infix precedence is left 6.

rSetNegation :: DiscreteOrdered a => RSet a -> RSet a Source #

Set negation.

Useful Sets

rSetEmpty :: DiscreteOrdered a => RSet a Source #

The empty set.

rSetFull :: DiscreteOrdered a => RSet a Source #

The set that contains everything.

QuickCheck Properties

Construction

prop_validNormalised :: DiscreteOrdered a => [Range a] -> Bool Source #

A normalised range list is valid for unsafeRangedSet

prop_validNormalised ls = validRangeList $ normaliseRangeList ls

prop_has :: DiscreteOrdered a => [Range a] -> a -> Bool Source #

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) == makeRangedSet ls -?- v

prop_unfold :: Integer -> Bool Source #

Verifies the correct membership of a set containing all integers starting with the digit "1" up to 19999.

prop_unfold = (v <= 99999 && head (show v) == '1') == (initial1 -?- v)
   where
      initial1 = rSetUnfold (BoundaryBelow 1) addNines times10
      addNines (BoundaryBelow n) = BoundaryAbove $ n * 2 - 1
      times10 (BoundaryBelow n) =
         if n <= 1000 then Just $ BoundaryBelow $ n * 10 else Nothing

Basic Operations

prop_union :: DiscreteOrdered a => RSet a -> RSet a -> a -> Bool Source #

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)

prop_intersection :: DiscreteOrdered a => RSet a -> RSet a -> a -> Bool Source #

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

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

prop_difference :: DiscreteOrdered a => RSet a -> RSet a -> a -> Bool Source #

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)

prop_negation :: DiscreteOrdered a => RSet a -> a -> Bool Source #

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)

prop_not_empty :: DiscreteOrdered a => RSet a -> a -> Property Source #

A set that contains a value is not empty

prop_not_empty rs v = (rs -?- v) ==> not (rSetIsEmpty rs)

Some Identities and Inequalities

prop_empty :: DiscreteOrdered a => a -> Bool Source #

The empty set has no members.

prop_empty v = not (rSetEmpty -?- v)

prop_full :: DiscreteOrdered a => a -> Bool Source #

The full set has every member.

prop_full v = rSetFull -?- v

prop_empty_intersection :: DiscreteOrdered a => RSet a -> Bool Source #

The intersection of a set with its negation is empty.

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

prop_full_union :: DiscreteOrdered a => RSet a -> Bool Source #

The union of a set with its negation is full.

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

prop_union_superset :: DiscreteOrdered a => RSet a -> RSet a -> Bool Source #

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

prop_intersection_subset :: DiscreteOrdered a => RSet a -> RSet a -> Bool Source #

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

prop_diff_intersect :: DiscreteOrdered a => RSet a -> RSet a -> Bool Source #

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

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

prop_subset :: DiscreteOrdered a => RSet a -> Bool Source #

A set is the non-strict subset of itself.

prop_subset rs = rs -<=- rs

prop_strict_subset :: DiscreteOrdered a => RSet a -> Bool Source #

A set is not the strict subset of itself.

prop_strict_subset rs = not (rs -<- rs)

prop_union_strict_superset :: DiscreteOrdered a => RSet a -> RSet a -> Property Source #

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))

prop_intersection_commutes :: DiscreteOrdered a => RSet a -> RSet a -> Bool Source #

Intersection commutes.

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

prop_union_commutes :: DiscreteOrdered a => RSet a -> RSet a -> Bool Source #

Union commutes.

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

prop_intersection_associates :: DiscreteOrdered a => RSet a -> RSet a -> RSet a -> Bool Source #

Intersection associates.

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

prop_union_associates :: DiscreteOrdered a => RSet a -> RSet a -> RSet a -> Bool Source #

Union associates.

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

prop_de_morgan_intersection :: DiscreteOrdered a => RSet a -> RSet a -> Bool Source #

De Morgan's Law for Intersection.

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

prop_de_morgan_union :: DiscreteOrdered a => RSet a -> RSet a -> Bool Source #

De Morgan's Law for Union.

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