Ranged-sets 0.1.1 → 0.2.0
raw patch · 15 files changed
+731/−4109 lines, 15 filesdep +HUnitPVP ok
version bump matches the API change (PVP)
Dependencies added: HUnit
API changes (from Hackage documentation)
+ Data.Ranged.Boundaries: adjacentBelow :: (DiscreteOrdered a) => a -> Maybe a
+ Data.Ranged.Boundaries: boundedBelow :: (Eq a, Enum a, Bounded a) => a -> Maybe a
+ Data.Ranged.RangedSet: prop_de_morgan_intersection :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool
+ Data.Ranged.RangedSet: prop_de_morgan_union :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool
+ Data.Ranged.RangedSet: prop_diff_intersect :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool
+ Data.Ranged.RangedSet: prop_difference :: (DiscreteOrdered a) => RSet a -> RSet a -> a -> Bool
+ Data.Ranged.RangedSet: prop_empty :: (DiscreteOrdered a) => a -> Bool
+ Data.Ranged.RangedSet: prop_empty_intersection :: (DiscreteOrdered a) => RSet a -> Bool
+ Data.Ranged.RangedSet: prop_full :: (DiscreteOrdered a) => a -> Bool
+ Data.Ranged.RangedSet: prop_full_union :: (DiscreteOrdered a) => RSet a -> Bool
+ Data.Ranged.RangedSet: prop_has :: (DiscreteOrdered a) => [Range a] -> a -> Bool
+ Data.Ranged.RangedSet: prop_intersection :: (DiscreteOrdered a) => RSet a -> RSet a -> a -> Bool
+ Data.Ranged.RangedSet: prop_intersection_associates :: (DiscreteOrdered a) => RSet a -> RSet a -> RSet a -> Bool
+ Data.Ranged.RangedSet: prop_intersection_commutes :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool
+ Data.Ranged.RangedSet: prop_intersection_subset :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool
+ Data.Ranged.RangedSet: prop_negation :: (DiscreteOrdered a) => RSet a -> a -> Bool
+ Data.Ranged.RangedSet: prop_not_empty :: (DiscreteOrdered a) => RSet a -> a -> Property
+ Data.Ranged.RangedSet: prop_strict_subset :: (DiscreteOrdered a) => RSet a -> Bool
+ Data.Ranged.RangedSet: prop_subset :: (DiscreteOrdered a) => RSet a -> Bool
+ Data.Ranged.RangedSet: prop_unfold :: Integer -> Bool
+ Data.Ranged.RangedSet: prop_union :: (DiscreteOrdered a) => RSet a -> RSet a -> a -> Bool
+ Data.Ranged.RangedSet: prop_union_associates :: (DiscreteOrdered a) => RSet a -> RSet a -> RSet a -> Bool
+ Data.Ranged.RangedSet: prop_union_commutes :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool
+ Data.Ranged.RangedSet: prop_union_strict_superset :: (DiscreteOrdered a) => RSet a -> RSet a -> Property
+ Data.Ranged.RangedSet: prop_union_superset :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool
+ Data.Ranged.RangedSet: prop_validNormalised :: (DiscreteOrdered a) => [Range a] -> Bool
+ Data.Ranged.RangedSet: rSetIsFull :: (DiscreteOrdered v) => RSet v -> Bool
+ Data.Ranged.Ranges: prop_differenceRange :: (DiscreteOrdered a) => Range a -> Range a -> a -> Bool
+ Data.Ranged.Ranges: prop_emptyNonSingleton :: Bool
+ Data.Ranged.Ranges: prop_enclosureUnion :: (DiscreteOrdered a) => Range a -> Range a -> Bool
+ Data.Ranged.Ranges: prop_fullNonSingleton :: Bool
+ Data.Ranged.Ranges: prop_intSingleton :: Integer -> Integer -> Property
+ Data.Ranged.Ranges: prop_intersectionOverlap :: (DiscreteOrdered a) => Range a -> Range a -> Bool
+ Data.Ranged.Ranges: prop_intersectionRange :: (DiscreteOrdered a) => Range a -> Range a -> a -> Bool
+ Data.Ranged.Ranges: prop_nonSingleton :: Double -> Double -> Property
+ Data.Ranged.Ranges: prop_singletonRangeConverse :: (DiscreteOrdered a) => a -> Bool
+ Data.Ranged.Ranges: prop_singletonRangeHas :: (DiscreteOrdered a) => a -> Bool
+ Data.Ranged.Ranges: prop_singletonRangeHasOnly :: (DiscreteOrdered a) => a -> a -> Bool
+ Data.Ranged.Ranges: prop_unionRange :: (DiscreteOrdered a) => Range a -> Range a -> a -> Bool
+ Data.Ranged.Ranges: prop_unionRangeLength :: (DiscreteOrdered a) => Range a -> Range a -> Bool
+ Data.Ranged.Ranges: rangeIsFull :: (DiscreteOrdered v) => Range v -> Bool
Files
- CHANGES.txt +6/−0
- Data/Ranged.hs +0/−1
- Data/Ranged/Boundaries.hs +109/−52
- Data/Ranged/RangedSet.hs +224/−279
- Data/Ranged/Ranges.hs +173/−111
- Doc/Data-Ranged-Boundaries.html +0/−681
- Doc/Data-Ranged-RangedSet.html +0/−1456
- Doc/Data-Ranged-Ranges.html +0/−838
- Doc/Data-Ranged.html +0/−106
- Doc/doc-index.html +0/−454
- Doc/index.html +0/−120
- README.txt +6/−2
- Ranged-sets.cabal +13/−9
- tests/Main.hs +184/−0
- tests/Makefile +16/−0
CHANGES.txt view
@@ -35,3 +35,9 @@ Added lots more QuickCheck properties. Added subset predicates. Added infix operators.++Version 0.2.0+-------------++Reorganised and extended tests.+Added "rangeIsFull" predicate.
Data/Ranged.hs view
@@ -1,4 +1,3 @@- module Data.Ranged ( module Data.Ranged.Boundaries, module Data.Ranged.Ranges,
Data/Ranged/Boundaries.hs view
@@ -9,13 +9,11 @@ -- ----------------------------------------------------------------------------- -- module Data.Ranged.Boundaries (- DiscreteOrdered,- adjacent,+ DiscreteOrdered (..), enumAdjacent, boundedAdjacent,+ boundedBelow, Boundary (..), above, (/>/)@@ -26,9 +24,9 @@ infix 4 />/ -{- | -Distinguish between dense and sparse ordered types. A dense type is -one in which any two values @v1 < v2@ have a third value @v3@ such that +{- |+Distinguish between dense and sparse ordered types. A dense type is+one in which any two values @v1 < v2@ have a third value @v3@ such that @v1 < v3 < v2@. In theory the floating types are dense, although in practice they can only have@@ -37,68 +35,127 @@ Tuples up to 4 members are declared as instances. Larger tuples may be added if necessary. +Most values of sparse types have an @adjacentBelow@, such that, for all x:++> case adjacentBelow x of+> Just x1 -> adjacent x1 x+> Nothing -> True++The exception is for bounded types when @x == lowerBound@. For dense types+@adjacentBelow@ always returns 'Nothing'.+ This approach was suggested by Ben Rudiak-Gould on comp.lang.functional. -}+ class Ord a => DiscreteOrdered a where- -- | Two values @x@ and @y@ are adjacent if @x < y@ and there does not + -- | Two values @x@ and @y@ are adjacent if @x < y@ and there does not -- exist a third value between them. Always @False@ for dense types. adjacent :: a -> a -> Bool+ -- | The value immediately below the argument, if it can be determined.+ adjacentBelow :: a -> Maybe a -instance DiscreteOrdered Bool where adjacent = boundedAdjacent-instance DiscreteOrdered Ordering where adjacent = boundedAdjacent-instance DiscreteOrdered Char where adjacent = boundedAdjacent-instance DiscreteOrdered Int where adjacent = boundedAdjacent-instance DiscreteOrdered Integer where adjacent = enumAdjacent-instance Integral a => DiscreteOrdered (Ratio a)- where adjacent _ _ = False-instance DiscreteOrdered Float where adjacent _ _ = False-instance DiscreteOrdered Double where adjacent _ _ = False-instance Ord a => DiscreteOrdered [a] where adjacent _ _ = False++-- Implementation note: the precise rules about unbounded enumerated vs +-- bounded enumerated types are difficult to express using Haskell 98, so+-- the prelude types are listed individually here.++instance DiscreteOrdered Bool where + adjacent = boundedAdjacent+ adjacentBelow = boundedBelow++instance DiscreteOrdered Ordering where + adjacent = boundedAdjacent+ adjacentBelow = boundedBelow++instance DiscreteOrdered Char where + adjacent = boundedAdjacent+ adjacentBelow = boundedBelow++instance DiscreteOrdered Int where + adjacent = boundedAdjacent+ adjacentBelow = boundedBelow++instance DiscreteOrdered Integer where + adjacent = enumAdjacent+ adjacentBelow = Just . pred++instance DiscreteOrdered Double where+ adjacent _ _ = False+ adjacentBelow = const Nothing++instance DiscreteOrdered Float where+ adjacent _ _ = False+ adjacentBelow = const Nothing++instance (Integral a) => DiscreteOrdered (Ratio a) where+ adjacent _ _ = False+ adjacentBelow = const Nothing++instance Ord a => DiscreteOrdered [a] where+ adjacent _ _ = False+ adjacentBelow = const Nothing+ instance (Ord a, DiscreteOrdered b) => DiscreteOrdered (a, b)- where adjacent (x1, x2) (y1, y2) = (x1 == y1) && adjacent x2 y2+ where+ adjacent (x1, x2) (y1, y2) = (x1 == y1) && adjacent x2 y2+ adjacentBelow (x1, x2) = do -- Maybe monad+ x2' <- adjacentBelow x2+ return (x1, x2')+ instance (Ord a, Ord b, DiscreteOrdered c) => DiscreteOrdered (a, b, c)- where + where adjacent (x1, x2, x3) (y1, y2, y3) = (x1 == y1) && (x2 == y2) && adjacent x3 y3-instance (Ord a, Ord b, Ord c, DiscreteOrdered d) => + adjacentBelow (x1, x2, x3) = do -- Maybe monad+ x3' <- adjacentBelow x3+ return (x1, x2, x3')++instance (Ord a, Ord b, Ord c, DiscreteOrdered d) => DiscreteOrdered (a, b, c, d)- where + where adjacent (x1, x2, x3, x4) (y1, y2, y3, y4) = (x1 == y1) && (x2 == y2) && (x3 == y3) && adjacent x4 y4- + adjacentBelow (x1, x2, x3, x4) = do -- Maybe monad+ x4' <- adjacentBelow x4+ return (x1, x2, x3, x4')++ -- | Check adjacency for sparse enumerated types (i.e. where there--- is no value between @x@ and @succ x@). Use as the definition of--- "adjacent" for most enumerated types.+-- is no value between @x@ and @succ x@). enumAdjacent :: (Ord a, Enum a) => a -> a -> Bool-enumAdjacent x y = (succ x == y) - +enumAdjacent x y = (succ x == y)+ -- | Check adjacency, allowing for case where x = maxBound. Use as the -- definition of "adjacent" for bounded enumerated types such as Int and Char. boundedAdjacent :: (Ord a, Enum a) => a -> a -> Bool boundedAdjacent x y = if x < y then succ x == y else False- - +++-- | The usual implementation of 'adjacentBelow' for bounded enumerated types.+boundedBelow :: (Eq a, Enum a, Bounded a) => a -> Maybe a+boundedBelow x = if x == minBound then Nothing else Just $ pred x+ {- |-A Boundary is a division of an ordered type into values above +A Boundary is a division of an ordered type into values above and below the boundary. No value can sit on a boundary. -Known bug: for Bounded types +Known bug: for Bounded types * @BoundaryAbove maxBound < BoundaryAboveAll@ * @BoundaryBelow minBound > BoundaryBelowAll@- -This is incorrect because there are no possible values in -between the left and right sides of these inequalities. ++This is incorrect because there are no possible values in+between the left and right sides of these inequalities. -} data Boundary a = -- | The argument is the highest value below the boundary.- BoundaryAbove a | + BoundaryAbove a | -- | The argument is the lowest value above the boundary. BoundaryBelow a | -- | The boundary above all values.- BoundaryAboveAll | + BoundaryAboveAll | -- | The boundary below all values. BoundaryBelowAll deriving (Show)@@ -109,37 +166,37 @@ above (BoundaryBelow b) v = v >= b above BoundaryAboveAll _ = False above BoundaryBelowAll _ = True- + -- | Same as 'above', but with the arguments reversed for more intuitive infix--- usage. +-- usage. (/>/) :: Ord v => v -> Boundary v -> Bool (/>/) = flip above- + instance (DiscreteOrdered a) => Eq (Boundary a) where b1 == b2 = compare b1 b2 == EQ instance (DiscreteOrdered a) => Ord (Boundary a) where- -- Comparison alogrithm based on brute force and ignorance: + -- Comparison alogrithm based on brute force and ignorance: -- enumerate all combinations.- + compare boundary1 boundary2 = case boundary1 of BoundaryAbove b1 -> case boundary2 of BoundaryAbove b2 -> compare b1 b2- BoundaryBelow b2 -> - if b1 < b2 - then - if adjacent b1 b2 then EQ else LT + BoundaryBelow b2 ->+ if b1 < b2+ then+ if adjacent b1 b2 then EQ else LT else GT BoundaryAboveAll -> LT BoundaryBelowAll -> GT BoundaryBelow b1 -> case boundary2 of- BoundaryAbove b2 -> - if b1 > b2 - then - if adjacent b2 b1 then EQ else GT + BoundaryAbove b2 ->+ if b1 > b2+ then+ if adjacent b2 b1 then EQ else GT else LT BoundaryBelow b2 -> compare b1 b2 BoundaryAboveAll -> LT@@ -147,11 +204,11 @@ BoundaryAboveAll -> case boundary2 of BoundaryAboveAll -> EQ- otherwise -> GT+ _ -> GT BoundaryBelowAll -> case boundary2 of BoundaryBelowAll -> EQ- otherwise -> LT+ _ -> LT -- QuickCheck Generator @@ -163,7 +220,7 @@ v <- arbitrary oneof [return $ BoundaryAbove v, return $ BoundaryBelow v] )]- coarbitrary BoundaryBelowAll = variant 0 + coarbitrary BoundaryBelowAll = variant 0 coarbitrary BoundaryAboveAll = variant 1 coarbitrary (BoundaryBelow v) = variant 2 . coarbitrary v coarbitrary (BoundaryAbove v) = variant 3 . coarbitrary v
Data/Ranged/RangedSet.hs view
@@ -1,38 +1,59 @@-module Data.Ranged.RangedSet ( +module Data.Ranged.RangedSet ( -- ** Ranged Set Type RSet, rSetRanges,- -- ** Ranged Set construction functions and their Preconditions+ -- ** Ranged Set construction functions and their preconditions makeRangedSet, unsafeRangedSet, validRangeList, normaliseRangeList, rSingleton,+ rSetUnfold, -- ** Predicates rSetIsEmpty,- (-?-), rSetHas, + rSetIsFull,+ (-?-), rSetHas, (-<=-), rSetIsSubset, (-<-), rSetIsSubsetStrict, -- ** Set Operations- (-\/-), rSetUnion, - (-/\-), rSetIntersection, + (-\/-), rSetUnion,+ (-/\-), rSetIntersection, (-!-), rSetDifference, rSetNegation, -- ** Useful Sets rSetEmpty, rSetFull,- rSetUnfold- -- ** QuickCheck Properties- -- *** Construction- -- $ConstructionProperties- + prop_validNormalised,+ prop_has,+ prop_unfold, -- *** Basic Operations- -- $BasicOperationProperties- + prop_union,+ prop_intersection,+ prop_difference,+ prop_negation,+ prop_not_empty, -- *** Some Identities and Inequalities+ -- $ConstructionProperties+ -- $BasicOperationProperties -- $SomeIdentitiesAndInequalities+ prop_empty,+ prop_full,+ prop_empty_intersection,+ prop_full_union,+ prop_union_superset,+ prop_intersection_subset,+ prop_diff_intersect,+ prop_subset,+ prop_strict_subset,+ prop_union_strict_superset,+ prop_intersection_commutes,+ prop_union_commutes,+ prop_intersection_associates,+ prop_union_associates,+ prop_de_morgan_intersection,+ prop_de_morgan_union, ) where import Data.Ranged.Boundaries@@ -48,7 +69,6 @@ -- | An RSet (for Ranged Set) is a list of ranges. The ranges must be sorted -- and not overlap.- newtype DiscreteOrdered v => RSet v = RSet {rSetRanges :: [Range v]} deriving (Eq, Show) @@ -71,24 +91,23 @@ -- | Rearrange and merge the ranges in the list so that they are in order and -- non-overlapping. normaliseRangeList :: DiscreteOrdered v => [Range v] -> [Range v]- -normaliseRangeList ranges = +normaliseRangeList ranges = normalise $ sort $ filter (not . rangeIsEmpty) ranges- + -- Private routine: normalise a range list that is known to be already sorted. -- This precondition is not checked. normalise :: DiscreteOrdered v => [Range v] -> [Range v] normalise (r1:r2:rs) =- if overlap r1 r2 + if overlap r1 r2 then normalise $- Range (rangeLower r1) + Range (rangeLower r1) (max (rangeUpper r1) (rangeUpper r2)) : rs else r1 : (normalise $ r2 : rs) where overlap (Range _ upper1) (Range lower2 _) = upper1 >= lower2- + normalise rs = rs @@ -98,7 +117,7 @@ makeRangedSet = RSet . normaliseRangeList --- | Create a new Ranged Set from a list of ranges. @validRangeList ranges@ +-- | Create a new Ranged Set from a list of ranges. @validRangeList ranges@ -- must return @True@. This precondition is not checked. unsafeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v unsafeRangedSet = RSet@@ -128,9 +147,9 @@ (-?-) = rSetHas --- | True if the first argument is a subset of the second argument, or is --- equal. --- +-- | 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 rSetIsSubset rs1 rs2 = rSetIsEmpty (rs1 -!- rs2)@@ -138,13 +157,13 @@ -- | 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-rSetIsSubsetStrict rs1 rs2 = - rSetIsEmpty (rs1 -!- rs2) +rSetIsSubsetStrict rs1 rs2 =+ rSetIsEmpty (rs1 -!- rs2) && not (rSetIsEmpty (rs2 -!- rs1))- + (-<-) = rSetIsSubsetStrict -- | Set union for ranged sets. Infix precedence is left 6.@@ -153,25 +172,25 @@ -- sorted list and then calls normalise to combine overlapping ranges. rSetUnion (RSet ls1) (RSet ls2) = RSet $ normalise $ merge ls1 ls2 where- merge ls1 [] = ls1- merge [] ls2 = ls2- merge ls1@(h1:t1) ls2@(h2:t2) =+ merge ms1 [] = ms1+ merge [] ms2 = ms2+ merge ms1@(h1:t1) ms2@(h2:t2) = if h1 < h2- then h1 : merge t1 ls2- else h2 : merge ls1 t2+ then h1 : merge t1 ms2+ else h2 : merge ms1 t2 (-\/-) = rSetUnion -- | Set intersection for ranged sets. Infix precedence is left 7. rSetIntersection, (-/\-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v-rSetIntersection (RSet ls1) (RSet ls2) = +rSetIntersection (RSet ls1) (RSet ls2) = RSet $ filter (not . rangeIsEmpty) $ merge ls1 ls2 where- merge ls1@(h1:t1) ls2@(h2:t2) =- rangeIntersection h1 h2 + merge ms1@(h1:t1) ms2@(h2:t2) =+ rangeIntersection h1 h2 : if rangeUpper h1 < rangeUpper h2- then merge t1 ls2- else merge ls1 t2+ then merge t1 ms2+ else merge ms1 t2 merge _ _ = [] (-/\-) = rSetIntersection@@ -194,11 +213,10 @@ setBounds1 = case setBounds of (BoundaryBelowAll : bs) -> bs _ -> BoundaryBelowAll : setBounds- setBounds = bounds $ rSetRanges set + setBounds = bounds $ rSetRanges set bounds (r:rs) = rangeLower r : rangeUpper r : bounds rs bounds _ = [] - -- | The empty set. rSetEmpty :: DiscreteOrdered a => RSet a rSetEmpty = RSet []@@ -207,32 +225,31 @@ rSetFull :: DiscreteOrdered a => RSet a rSetFull = RSet [Range BoundaryBelowAll BoundaryAboveAll] - -- | Construct a range set.-rSetUnfold :: DiscreteOrdered a => +rSetUnfold :: DiscreteOrdered a => Boundary a -- ^ A first lower boundary.- -> (Boundary a -> Boundary a) + -> (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).+ -- ^ 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 rSetUnfold bound upperFunc succFunc = RSet $ normalise $ ranges bound where- ranges b = - Range b (upperFunc bound)+ ranges b =+ Range b (upperFunc b) : case succFunc b of Just b2 -> ranges b2 Nothing -> []- - ++ -- QuickCheck Generators -instance (Arbitrary v, DiscreteOrdered v, Show v) => - Arbitrary (RSet v) +instance (Arbitrary v, DiscreteOrdered v, Show v) =>+ Arbitrary (RSet v) where arbitrary = frequency [ (1, return rSetEmpty),@@ -247,293 +264,221 @@ -- and pair them off. Odd boundaries are dropped. rangeList (b1:b2:bs) = Range b1 b2 : rangeList bs rangeList _ = []- + coarbitrary (RSet ls) = variant 0 . coarbitrary ls --- ================================================================== +-- ================================================================== -- QuickCheck Properties -- ================================================================== --- Note for maintenance: Haddock does not include QuickCheck properties,--- so they have to be copied into documentation blocks manually. This--- process must be repeated for new or modified properties.-- --------------------------------------------------------------------- -- Construction properties --------------------------------------------------------------------- -{- $ConstructionProperties+-- | A normalised range list is valid for unsafeRangedSet+--+-- > prop_validNormalised ls = validRangeList $ normaliseRangeList ls+prop_validNormalised :: (DiscreteOrdered a) => [Range a] -> Bool+prop_validNormalised ls = validRangeList $ normaliseRangeList ls -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) == makeRangedSet ls -?- v+prop_has :: (DiscreteOrdered a) => [Range a] -> a -> Bool+prop_has ls v = (ls `rangeListHas` v) == makeRangedSet ls -?- v -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---}---- A normalised range list is valid for unsafeRangedSet-prop_validNormalised ls = validRangeList $ normaliseRangeList ls- where types = ls :: [Range Integer]+-- | 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 --- 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- where types = v :: Integer+prop_unfold :: Integer -> Bool+prop_unfold v = (v <= 99999 && head (show v) == '1') == (initial1 -?- v)+ where+ initial1 = rSetUnfold (BoundaryBelow 1) addNines times10+ addNines (BoundaryBelow n) = BoundaryAbove $ n * 2 - 1+ addNines _ = error "Can't happen"+ times10 (BoundaryBelow n) = + if n <= 10000 then Just $ BoundaryBelow $ n * 10 else Nothing+ times10 _ = error "Can't happen" --------------------------------------------------------------------- -- Basic operation properties --------------------------------------------------------------------- -{- $BasicOperationProperties-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)---} - --- Iff a value is in either of two ranged sets then it is in the union of+-- | 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_union :: (DiscreteOrdered a ) => RSet a -> RSet a -> a -> Bool prop_union rs1 rs2 v = (rs1 -?- v || rs2 -?- v) == ((rs1 -\/- rs2) -?- v)- where types = v :: Integer --- Iff a value is in both of two ranged sets then it is in the intersection+-- | 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 `rSetIntersection` rs2) -?- v)- where types = v :: Integer+--+-- > prop_intersection rs1 rs2 v =+-- > (rs1 -?- v && rs2 -?- v) == ((rs1 -/\- rs2) -?- v)+prop_intersection :: (DiscreteOrdered a) => RSet a -> RSet a -> a -> Bool+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+-- | 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 = +--+-- > prop_difference rs1 rs2 v =+-- > (rs1 -?- v && not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v)+prop_difference :: (DiscreteOrdered a) => RSet a -> RSet a -> a -> Bool+prop_difference rs1 rs2 v = (rs1 -?- v && not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v)- where types = v :: Integer ---- Iff a value is not in a ranged set then it is in its negation. +-- | 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_negation :: (DiscreteOrdered a) => RSet a -> a -> Bool prop_negation rs v = rs -?- v == not (rSetNegation rs -?- v)- where types = v :: Integer ---- A set that contains a value is not empty+-- | A set that contains a value is not empty+--+-- > prop_not_empty rs v = (rs -?- v) ==> not (rSetIsEmpty rs)+prop_not_empty :: (DiscreteOrdered a) => RSet a -> a -> Property prop_not_empty rs v = (rs -?- v) ==> not (rSetIsEmpty rs)- where types = v :: Integer- --------------------------------------------------------------------- -- Some identities and inequalities of sets --------------------------------------------------------------------- -{- $SomeIdentitiesAndInequalities--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)---}---- The empty set has no members.+-- | The empty set has no members.+--+-- > prop_empty v = not (rSetEmpty -?- v)+prop_empty :: (DiscreteOrdered a) => a -> Bool prop_empty v = not (rSetEmpty -?- v)- where types = v :: Integer ---- The full set has every member.+-- | The full set has every member.+--+-- > prop_full v = rSetFull -?- v+prop_full :: (DiscreteOrdered a) => a -> Bool prop_full v = rSetFull -?- v- where types = v :: Integer ---- The intersection of a set with its negation is empty.+-- | The intersection of a set with its negation is empty.+--+-- > prop_empty_intersection rs =+-- > rSetIsEmpty (rs -/\- rSetNegation rs)+prop_empty_intersection :: (DiscreteOrdered a) => RSet a -> Bool prop_empty_intersection rs =- rSetIsEmpty (rs -/\- rSetNegation rs) - where types = rs :: RSet Integer- - --- The union of a set with its negation is full.+ rSetIsEmpty (rs -/\- rSetNegation rs)++-- | The union of a set with its negation is full.+--+-- > prop_full_union rs v =+-- > rSetIsFull (rs -\/- rSetNegation rs)+prop_full_union :: (DiscreteOrdered a) => RSet a -> Bool prop_full_union rs = rSetIsFull (rs -\/- rSetNegation rs)- where types = rs :: RSet Integer ---- The union of two sets is the non-strict superset of both.+-- | 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_union_superset :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool prop_union_superset rs1 rs2 =- rs1 -<=- u && rs2 -<=- u + rs1 -<=- u && rs2 -<=- u where- u :: RSet Integer u = rs1 -\/- rs2- --- The intersection of two sets is the non-strict subset of both.-prop_intersection_subset rs1 rs2 =- i -<=- rs1 && i -<=- 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+prop_intersection_subset :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool+prop_intersection_subset rs1 rs2 = i -<=- rs1 && i -<=- rs2 where- i :: RSet Integer i = rs1 -/\- rs2 --- The difference of two sets intersected with the subtractand is empty.-prop_diff_intersect rs1 rs2 =- rSetIsEmpty ((rs1 -!- rs2) -/\- rs2)- where types = rs1 :: RSet Integer- - --- A set is the non-strict subset of itself.-prop_subset rs =- rs -<=- rs- where types = rs :: RSet Integer- --- A set is not the strict subset of itself.-prop_strict_subset rs =- not (rs -<- rs)- where types = rs :: RSet Integer- +-- | The difference of two sets intersected with the subtractand is empty.+--+-- > prop_diff_intersect rs1 rs2 =+-- > rSetIsEmpty ((rs1 -!- rs2) -/\- rs2)+prop_diff_intersect :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool+prop_diff_intersect rs1 rs2 = rSetIsEmpty ((rs1 -!- rs2) -/\- rs2) --- If rs1 - rs2 is not empty then the union of rs1 and rs2 will be a strict +-- | A set is the non-strict subset of itself.+--+-- > prop_subset rs = rs -<=- rs+prop_subset :: (DiscreteOrdered a) => RSet a -> Bool+prop_subset rs = rs -<=- rs++-- | A set is not the strict subset of itself.+--+-- > prop_strict_subset rs = not (rs -<- rs)+prop_strict_subset :: (DiscreteOrdered a) => RSet a -> Bool+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))+prop_union_strict_superset :: (DiscreteOrdered a) => RSet a -> RSet a -> Property prop_union_strict_superset rs1 rs2 =- (not $ rSetIsEmpty (rs1 -!- rs2))- ==> (rs2 -<- (rs1 -\/- rs2))- where types = rs1 :: RSet Integer+ (not $ rSetIsEmpty (rs1 -!- rs2)) ==> (rs2 -<- (rs1 -\/- rs2)) --- Intersection commutes-prop_intersection_commutes :: RSet Integer -> RSet Integer -> Bool-prop_intersection_commutes rs1 rs2 =- (rs1 -/\- rs2) == (rs2 -/\- rs1)- where types = rs1 :: RSet Integer- --- Union commutes-prop_union_commutes rs1 rs2 =- (rs1 -\/- rs2) == (rs2 -\/- rs1)- where types = rs1 :: RSet Integer- --- Intersection associates+-- | Intersection commutes.+--+-- > prop_intersection_commutes rs1 rs2 = (rs1 -/\- rs2) == (rs2 -/\- rs1)+prop_intersection_commutes :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool+prop_intersection_commutes rs1 rs2 = (rs1 -/\- rs2) == (rs2 -/\- rs1)++-- | Union commutes.+--+-- > prop_union_commutes rs1 rs2 = (rs1 -\/- rs2) == (rs2 -\/- rs1)+prop_union_commutes :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool+prop_union_commutes rs1 rs2 = (rs1 -\/- rs2) == (rs2 -\/- rs1)++-- | Intersection associates.+--+-- > prop_intersection_associates rs1 rs2 rs3 =+-- > ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3))+prop_intersection_associates :: (DiscreteOrdered a) => + RSet a -> RSet a -> RSet a -> Bool prop_intersection_associates rs1 rs2 rs3 = ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3))- where types = rs1 :: RSet Integer- --- Union associates++-- | Union associates.+--+-- > prop_union_associates rs1 rs2 rs3 =+-- > ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3))+prop_union_associates :: (DiscreteOrdered a) => + RSet a -> RSet a -> RSet a -> Bool prop_union_associates rs1 rs2 rs3 = ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3))- where types = rs1 :: RSet Integer- --- De Morgan's Law for Intersection++-- | De Morgan's Law for Intersection.+--+-- > prop_de_morgan_intersection rs1 rs2 =+-- > rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2)+prop_de_morgan_intersection :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool prop_de_morgan_intersection rs1 rs2 = rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2)- where types = rs1 :: RSet Integer --- De Morgan's Law for Union+-- | De Morgan's Law for Union.+--+-- > prop_de_morgan_union rs1 rs2 =+-- > rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2)++prop_de_morgan_union :: (DiscreteOrdered a) => RSet a -> RSet a -> Bool prop_de_morgan_union rs1 rs2 = rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2)- where types = rs1 :: RSet Integer
Data/Ranged/Ranges.hs view
@@ -1,5 +1,5 @@ -------------------------------------------------------------------------------- +-- -- Module : Data.Ranged.Ranges -- Copyright : (c) Paul Johnson 2006 -- License : BSD-style@@ -9,9 +9,7 @@ -- ----------------------------------------------------------------------------- - -- | A range has an upper and lower boundary.- module Data.Ranged.Ranges ( -- ** Construction Range (..),@@ -19,6 +17,7 @@ fullRange, -- ** Predicates rangeIsEmpty,+ rangeIsFull, rangeOverlap, rangeEncloses, rangeSingletonValue,@@ -29,11 +28,24 @@ singletonRange, rangeIntersection, rangeUnion,- rangeDifference+ rangeDifference, -- ** QuickCheck properties- -- $properties+ prop_unionRange,+ prop_unionRangeLength,+ prop_intersectionRange,+ prop_differenceRange,+ prop_intersectionOverlap,+ prop_enclosureUnion,+ prop_singletonRangeHas,+ prop_singletonRangeHasOnly,+ prop_singletonRangeConverse,+ prop_emptyNonSingleton,+ prop_fullNonSingleton,+ prop_nonSingleton,+ prop_intSingleton ) where +import Control.Monad import Data.Ranged.Boundaries import Data.Maybe import Test.QuickCheck@@ -42,8 +54,8 @@ data Ord v => Range v = Range {rangeLower, rangeUpper :: Boundary v} instance (DiscreteOrdered a) => Eq (Range a) where- r1 == r2 = (rangeIsEmpty r1 && rangeIsEmpty r2) || - (rangeLower r1 == rangeLower r2 && + r1 == r2 = (rangeIsEmpty r1 && rangeIsEmpty r2) ||+ (rangeLower r1 == rangeLower r2 && rangeUpper r1 == rangeUpper r2) @@ -54,11 +66,12 @@ | rangeIsEmpty r2 = GT | otherwise = compare (rangeLower r1, rangeUpper r1) (rangeLower r2, rangeUpper r2)- + instance (Show a, DiscreteOrdered a) => Show (Range a) where show r | rangeIsEmpty r = "Empty"- | otherwise = + | rangeIsFull r = "All x"+ | otherwise = case rangeSingletonValue r of Just v -> "x == " ++ show v Nothing -> lowerBound ++ "x" ++ upperBound@@ -87,25 +100,46 @@ [Range v] -> v -> Bool rangeListHas ls v = or $ map (\r -> rangeHas r v) ls + -- | The empty range emptyRange :: DiscreteOrdered v => Range v emptyRange = Range BoundaryAboveAll BoundaryBelowAll + -- | The full range. All values are within it. fullRange :: DiscreteOrdered v => Range v fullRange = Range BoundaryBelowAll BoundaryAboveAll + -- | A range containing a single value singletonRange :: DiscreteOrdered v => v -> Range v singletonRange v = Range (BoundaryBelow v) (BoundaryAbove v) + -- | If the range is a singleton, returns @Just@ the value. Otherwise returns -- @Nothing@.+--+-- Known bug: This always returns @Nothing@ for ranges including +-- @BoundaryBelowAll@ or @BoundaryAboveAll@. For bounded types this can be +-- incorrect. For instance, the following range only contains one value:+-- +-- > Range (BoundaryBelow maxBound) BoundaryAboveAll rangeSingletonValue :: DiscreteOrdered v => Range v -> Maybe v+rangeSingletonValue (Range (BoundaryBelow v1) (BoundaryBelow v2))+ | adjacent v1 v2 = Just v1+ | otherwise = Nothing rangeSingletonValue (Range (BoundaryBelow v1) (BoundaryAbove v2))- | v1 == v2 = Just v1- | otherwise = Nothing-rangeSingletonValue _ = Nothing+ | v1 == v2 = Just v1+ | otherwise = Nothing+rangeSingletonValue (Range (BoundaryAbove v1) (BoundaryBelow v2)) = + do+ v2' <- adjacentBelow v2+ v2'' <- adjacentBelow v2'+ if v1 == v2'' then return v2' else Nothing+rangeSingletonValue (Range (BoundaryAbove v1) (BoundaryAbove v2))+ | adjacent v1 v2 = Just v2+ | otherwise = Nothing+rangeSingletonValue (Range _ _) = Nothing -- | A range is empty unless its upper boundary is greater than its lower -- boundary.@@ -113,52 +147,56 @@ rangeIsEmpty (Range lower upper) = upper <= lower +-- | A range is full if it contains every possible value.+rangeIsFull :: DiscreteOrdered v => Range v -> Bool+rangeIsFull = (== fullRange)+ -- | Two ranges overlap if their intersection is non-empty. rangeOverlap :: DiscreteOrdered v => Range v -> Range v -> Bool-rangeOverlap r1 r2 = +rangeOverlap r1 r2 = not (rangeIsEmpty r1) && not (rangeIsEmpty r2) && not (rangeUpper r1 <= rangeLower r2 || rangeUpper r2 <= rangeLower r1)- - --- | The first range encloses the second if every value in the second range is +++-- | The first range encloses the second if every value in the second range is -- also within the first range. If the second range is empty then this is -- always true. rangeEncloses :: DiscreteOrdered v => Range v -> Range v -> Bool rangeEncloses r1 r2 =- (rangeLower r1 <= rangeLower r2 && rangeUpper r2 <= rangeUpper r1) + (rangeLower r1 <= rangeLower r2 && rangeUpper r2 <= rangeUpper r1) || rangeIsEmpty r2 -- | Intersection of two ranges, if any. rangeIntersection :: DiscreteOrdered v => Range v -> Range v -> Range v- -rangeIntersection (Range lower1 upper1) (Range lower2 upper2) =- Range (max lower1 lower2) (min upper1 upper2)- - +rangeIntersection r1@(Range lower1 upper1) r2@(Range lower2 upper2)+ | rangeIsEmpty r1 || rangeIsEmpty r2 = emptyRange+ | otherwise = Range (max lower1 lower2) (min upper1 upper2)++ -- | Union of two ranges. Returns one or two results. -- -- If there are two results then they are guaranteed to have a non-empty -- gap in between, but may not be in ascending order. rangeUnion :: DiscreteOrdered v => Range v -> Range v -> [Range v]- -rangeUnion r1@(Range lower1 upper1) r2@(Range lower2 upper2) =- if touching- then [Range lower upper]- else [r1, r2]+rangeUnion r1@(Range lower1 upper1) r2@(Range lower2 upper2)+ | rangeIsEmpty r1 = [r2]+ | rangeIsEmpty r2 = [r1]+ | otherwise =+ if touching then [Range lower upper] else [r1, r2] where- touching = (max lower1 lower2) <= (min upper1 upper2)- lower = min lower1 lower2- upper = max upper1 upper2+ touching = (max lower1 lower2) <= (min upper1 upper2)+ lower = min lower1 lower2+ upper = max upper1 upper2 --- | @range1@ minus @range2@. Returns zero, one or two results. Multiple --- results are guaranteed to have non-empty gaps in between, but may not be in +-- | @range1@ minus @range2@. Returns zero, one or two results. Multiple+-- results are guaranteed to have non-empty gaps in between, but may not be in -- ascending order. rangeDifference :: DiscreteOrdered v => Range v -> Range v -> [Range v]- -rangeDifference r1@(Range lower1 upper1) r2@(Range lower2 upper2) =++rangeDifference r1@(Range lower1 upper1) (Range lower2 upper2) = -- There are six possibilities -- 1: r2 completely less than r1 -- 2: r2 overlaps bottom of r1@@ -177,14 +215,14 @@ -- QuickCheck generators -instance (Arbitrary v, DiscreteOrdered v, Show v) => +instance (Arbitrary v, DiscreteOrdered v, Show v) => Arbitrary (Range v) where- + arbitrary = frequency [ (17, do -- Ordinary range b1 <- arbitrary b2 <- arbitrary- if b1 < b2 + if b1 < b2 then return $ Range b1 b2 else return $ Range b2 b1 ),@@ -195,100 +233,124 @@ (1, return emptyRange), (1, return fullRange) ]- + coarbitrary (Range lower upper) = variant 0 . coarbitrary lower . coarbitrary upper- - --- QuickCheck Properties -{- $properties-Range union -> prop_union r1 r2 n =-> (r1 `rangeHas` n || r2 `rangeHas` n) -> == (r1 `rangeUnion` r2) `rangeListHas` n--Range intersection--> prop_intersection r1 r2 n =-> (r1 `rangeHas` n && r2 `rangeHas` n)-> == (r1 `rangeIntersection` r2) `rangeHas` n--Range difference--> prop_difference r1 r2 n =-> (r1 `rangeHas` n && not (r2 `rangeHas` n))-> == (r1 `rangeDifference` r2) `rangeListHas` n--Singleton range--> prop_singletonHas v =-> singletonRange v `rangeHas` v--> prop_singletonConverse v =-> rangeSingletonValue (singletonRange v) == Just v---}---- For Integers (sparse type)+-- QuickCheck Properties --- Range union-prop_union_int r1 r2 n = - (r1 `rangeHas` n || r2 `rangeHas` n) +-- | The union of two ranges has a value iff either range has it.+-- +-- > prop_unionRange r1 r2 n =+-- > (r1 `rangeHas` n || r2 `rangeHas` n)+-- > == (r1 `rangeUnion` r2) `rangeListHas` n+prop_unionRange :: (DiscreteOrdered a) => Range a -> Range a -> a -> Bool+prop_unionRange r1 r2 n =+ (r1 `rangeHas` n || r2 `rangeHas` n) == (r1 `rangeUnion` r2) `rangeListHas` n- where t :: Integer ; t = n +-- | The union of two ranges always contains one or two ranges.+-- +-- > prop_unionRangeLength r1 r2 = (n == 1) || (n == 2)+-- > where n = length $ rangeUnion r1 r2+prop_unionRangeLength :: (DiscreteOrdered a) => Range a -> Range a -> Bool+prop_unionRangeLength r1 r2 = (n == 1) || (n == 2)+ where n = length $ rangeUnion r1 r2 --- Range intersection-prop_intersection_int r1 r2 n =+-- | The intersection of two ranges has a value iff both ranges have it.+-- +-- > prop_intersectionRange r1 r2 n =+-- > (r1 `rangeHas` n && r2 `rangeHas` n)+-- > == (r1 `rangeIntersection` r2) `rangeHas` n+prop_intersectionRange :: (DiscreteOrdered a) => Range a -> Range a -> a -> Bool+prop_intersectionRange r1 r2 n = (r1 `rangeHas` n && r2 `rangeHas` n) == (r1 `rangeIntersection` r2) `rangeHas` n- where t :: Integer ; t = n --- Range difference-prop_difference_int r1 r2 n =+-- | The difference of two ranges has a value iff the first range has it and+-- the second does not.+-- +-- > prop_differenceRange r1 r2 n =+-- > (r1 `rangeHas` n && not (r2 `rangeHas` n))+-- > == (r1 `rangeDifference` r2) `rangeListHas` n+prop_differenceRange :: (DiscreteOrdered a) => Range a -> Range a -> a -> Bool+prop_differenceRange r1 r2 n = (r1 `rangeHas` n && not (r2 `rangeHas` n)) == (r1 `rangeDifference` r2) `rangeListHas` n- where t :: Integer ; t = n --- Range Singleton Has-prop_singletonHas_int v =- singletonRange v `rangeHas` v- where t :: Integer ; t = v+-- | Iff two ranges overlap then their intersection is non-empty.+-- +-- > prop_intersectionOverlap r1 r2 = +-- > (rangeIsEmpty $ rangeIntersection r1 r2) == (rangeOverlap r1 r2)+prop_intersectionOverlap :: (DiscreteOrdered a) => Range a -> Range a -> Bool+prop_intersectionOverlap r1 r2 = + (rangeIsEmpty $ rangeIntersection r1 r2) == not (rangeOverlap r1 r2) --- Range Singleton inverse-prop_singletonConverse_int v =+-- | Range enclosure makes union an identity function.+-- +-- > prop_enclosureUnion r1 r2 = +-- > rangeEncloses r1 r2 == (rangeUnion r1 r2 == [r1])+prop_enclosureUnion :: (DiscreteOrdered a) => Range a -> Range a -> Bool+prop_enclosureUnion r1 r2 = rangeEncloses r1 r2 == (rangeUnion r1 r2 == [r1])++-- | Range Singleton has its member.+-- +-- > prop_singletonRangeHas v = singletonRange v `rangeHas` v+prop_singletonRangeHas :: (DiscreteOrdered a) => a -> Bool+prop_singletonRangeHas v = singletonRange v `rangeHas` v++-- | Range Singleton has only its member.+-- +-- > prop_singletonHasOnly v1 v2 =+-- > (v1 == v2) == (singletonRange v1 `rangeHas` v2)+prop_singletonRangeHasOnly :: (DiscreteOrdered a) => a -> a -> Bool+prop_singletonRangeHasOnly v1 v2 =+ (v1 == v2) == (singletonRange v1 `rangeHas` v2)++-- | A singleton range can have its value extracted.+-- +-- > prop_singletonRangeConverse v =+-- > rangeSingletonValue (singletonRange v) == Just v+prop_singletonRangeConverse:: (DiscreteOrdered a) => a -> Bool+prop_singletonRangeConverse v = rangeSingletonValue (singletonRange v) == Just v- where t :: Integer ; t = v --- For Reals (dense type)+-- | The empty range is not a singleton.+-- +-- > prop_emptyNonSingleton = rangeSingletonValue emptyRange == Nothing+prop_emptyNonSingleton :: Bool+prop_emptyNonSingleton = + rangeSingletonValue (emptyRange :: Range Int) == Nothing --- Range Union-prop_union_real r1 r2 n = - (r1 `rangeHas` n || r2 `rangeHas` n) - == (r1 `rangeUnion` r2) `rangeListHas` n- where t :: Double ; t = n+-- | The full range is not a singleton.+-- +-- > prop_fullNonSingleton = rangeSingletonValue fullRange == Nothing+prop_fullNonSingleton :: Bool+prop_fullNonSingleton = + rangeSingletonValue (fullRange :: Range Int) == Nothing --- Range intersection-prop_intersection_real r1 r2 n =- (r1 `rangeHas` n && r2 `rangeHas` n)- == (r1 `rangeIntersection` r2) `rangeHas` n- where t :: Double ; t = n+-- | For real x and y, @x < y@ implies that any range between them is a+-- non-singleton.+prop_nonSingleton :: Double -> Double -> Property+prop_nonSingleton x y = (x < y) ==> null $ mapMaybe rangeSingletonValue rs+ where rs = [+ Range (BoundaryBelow x) (BoundaryBelow y),+ Range (BoundaryAbove x) (BoundaryBelow y),+ Range (BoundaryBelow x) (BoundaryAbove y),+ Range (BoundaryAbove x) (BoundaryAbove y)] --- Range difference-prop_difference_real r1 r2 n =- (r1 `rangeHas` n && not (r2 `rangeHas` n))- == (r1 `rangeDifference` r2) `rangeListHas` n- where t :: Double ; t = n --- Range Singleton Has-prop_singletonHas_real v =- singletonRange v `rangeHas` v- where t :: Double ; t = v+-- | For all integers x and y, any range formed from boundaries on either side+-- of x and y is a singleton iff it contains exactly one integer.+prop_intSingleton :: Integer -> Integer -> Property+prop_intSingleton x y = forAll (rangeAround x y) $ \r ->+ case filter (rangeHas r) [x-1 .. y+1] of+ [v] -> rangeSingletonValue r == Just v+ _ -> rangeSingletonValue r == Nothing+ where+ rangeAround v1 v2 = return Range `ap` genBound v1 `ap` genBound v2+ genBound v = elements [BoundaryAbove v, BoundaryBelow v]+ --- Range Singleton inverse-prop_singletonConverse_real v =- rangeSingletonValue (singletonRange v) == Just v- where t :: Double ; t = v
− Doc/Data-Ranged-Boundaries.html
@@ -1,681 +0,0 @@-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">-<!--Rendered using the Haskell Html Library v0.2-->-<HTML-><HEAD-><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"-><TITLE->Data.Ranged.Boundaries</TITLE-><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"-><SCRIPT SRC="haddock.js" TYPE="text/javascript"-></SCRIPT-></HEAD-><BODY-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="topbar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "-></TD-><TD CLASS="title"-></TD-><TD CLASS="topbut"-><A HREF="index.html"->Contents</A-></TD-><TD CLASS="topbut"-><A HREF="doc-index.html"->Index</A-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="modulebar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><FONT SIZE="6"->Data.Ranged.Boundaries</FONT-></TD-><TD ALIGN="right"-><TABLE CLASS="narrow" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="infohead"->Portability</TD-><TD CLASS="infoval"->portable</TD-></TR-><TR-><TD CLASS="infohead"->Stability</TD-><TD CLASS="infoval"->experimental</TD-></TR-><TR-><TD CLASS="infohead"->Maintainer</TD-><TD CLASS="infoval"->paul@cogito.org.uk</TD-></TR-></TABLE-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section1"->Description</TD-></TR-><TR-><TD CLASS="doc"-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section1"->Synopsis</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="decl"-><SPAN CLASS="keyword"->class</SPAN-> Ord a => <A HREF="#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a <SPAN CLASS="keyword"->where</SPAN-></TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="decl"-><A HREF="#v%3Aadjacent"->adjacent</A-> :: a -> a -> Bool</TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3Aadjacent"->adjacent</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => a -> a -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3AenumAdjacent"->enumAdjacent</A-> :: (Ord a, Enum a) => a -> a -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3AboundedAdjacent"->boundedAdjacent</A-> :: (Ord a, Enum a) => a -> a -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="decl"-><SPAN CLASS="keyword"->data</SPAN-> <A HREF="#t%3ABoundary"->Boundary</A-> a</TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="decl"->= <A HREF="#v%3ABoundaryAbove"->BoundaryAbove</A-> a</TD-></TR-><TR-><TD CLASS="decl"->| <A HREF="#v%3ABoundaryBelow"->BoundaryBelow</A-> a</TD-></TR-><TR-><TD CLASS="decl"->| <A HREF="#v%3ABoundaryAboveAll"->BoundaryAboveAll</A-></TD-></TR-><TR-><TD CLASS="decl"->| <A HREF="#v%3ABoundaryBelowAll"->BoundaryBelowAll</A-></TD-></TR-></TABLE-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3Aabove"->above</A-> :: Ord v => <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> v -> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3A%2F%3E%2F"->(/>/)</A-> :: Ord v => v -> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> v -> Bool</TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section1"->Documentation</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><SPAN CLASS="keyword"->class</SPAN-> Ord a => <A NAME="t%3ADiscreteOrdered"-></A-><B->DiscreteOrdered</B-> a <SPAN CLASS="keyword"->where</SPAN-></TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="ndoc"-><P->Distinguish between dense and sparse ordered types. A dense type is -one in which any two values <TT->v1 < v2</TT-> have a third value <TT->v3</TT-> such that -<TT->v1 < v3 < v2</TT->.-</P-><P->In theory the floating types are dense, although in practice they can only have-finitely many values. This class treats them as dense.-</P-><P->Tuples up to 4 members are declared as instances. Larger tuples may be added-if necessary.-</P-><P->This approach was suggested by Ben Rudiak-Gould on comp.lang.functional.-</P-></TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="section4"->Methods</TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="decl"-><A NAME="v%3Aadjacent"-></A-><B->adjacent</B-> :: a -> a -> Bool</TD-></TR-><TR-><TD CLASS="doc"->Two values <TT->x</TT-> and <TT->y</TT-> are adjacent if <TT->x < y</TT-> and there does not - exist a third value between them. Always <TT->False</TT-> for dense types.-</TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="section4"-><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:DiscreteOrdered')" ALT="show/hide"-> Instances</TD-></TR-><TR-><TD CLASS="body"-><DIV ID="i:DiscreteOrdered" STYLE="display:block;"-><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> Bool</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> Char</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> Double</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> Float</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> Int</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> Integer</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> Ordering</TD-></TR-><TR-><TD CLASS="decl"->(Ord a, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> b) => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> (a, b)</TD-></TR-><TR-><TD CLASS="decl"->(Ord a, Ord b, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> c) => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> (a, b, c)</TD-></TR-><TR-><TD CLASS="decl"->(Ord a, Ord b, Ord c, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> d) => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> (a, b, c, d)</TD-></TR-><TR-><TD CLASS="decl"->Integral a => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> (Ratio a)</TD-></TR-><TR-><TD CLASS="decl"->Ord a => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> [a]</TD-></TR-></TABLE-></DIV-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3Aadjacent"-></A-><B->adjacent</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => a -> a -> Bool</TD-></TR-><TR-><TD CLASS="doc"->Two values <TT->x</TT-> and <TT->y</TT-> are adjacent if <TT->x < y</TT-> and there does not - exist a third value between them. Always <TT->False</TT-> for dense types.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3AenumAdjacent"-></A-><B->enumAdjacent</B-> :: (Ord a, Enum a) => a -> a -> Bool</TD-></TR-><TR-><TD CLASS="doc"->Check adjacency for sparse enumerated types (i.e. where there- is no value between <TT->x</TT-> and <TT->succ x</TT->). Use as the definition of- <A HREF="adjacent.html"->adjacent</A-> for most enumerated types.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3AboundedAdjacent"-></A-><B->boundedAdjacent</B-> :: (Ord a, Enum a) => a -> a -> Bool</TD-></TR-><TR-><TD CLASS="doc"->Check adjacency, allowing for case where x = maxBound. Use as the- definition of <A HREF="adjacent.html"->adjacent</A-> for bounded enumerated types such as Int and Char.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><SPAN CLASS="keyword"->data</SPAN-> <A NAME="t%3ABoundary"-></A-><B->Boundary</B-> a</TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="ndoc"-><P->A Boundary is a division of an ordered type into values above -and below the boundary. No value can sit on a boundary.-</P-><P->Known bug: for Bounded types -</P-><UL-><LI-><PRE->BoundaryAbove maxBound < BoundaryAboveAll</PRE-></LI-><LI-><PRE->BoundaryBelow minBound > BoundaryBelowAll</PRE-></LI-></UL-><P->This is incorrect because there are no possible values in -between the left and right sides of these inequalities. -</P-></TD-></TR-><TR-><TD CLASS="section4"->Constructors</TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"-><TR-><TD CLASS="arg"-><A NAME="v%3ABoundaryAbove"-></A-><B->BoundaryAbove</B-> a</TD-><TD CLASS="rdoc"->The argument is the highest value below the boundary.-</TD-></TR-><TR-><TD CLASS="arg"-><A NAME="v%3ABoundaryBelow"-></A-><B->BoundaryBelow</B-> a</TD-><TD CLASS="rdoc"->The argument is the lowest value above the boundary.-</TD-></TR-><TR-><TD CLASS="arg"-><A NAME="v%3ABoundaryAboveAll"-></A-><B->BoundaryAboveAll</B-></TD-><TD CLASS="rdoc"->The boundary above all values.-</TD-></TR-><TR-><TD CLASS="arg"-><A NAME="v%3ABoundaryBelowAll"-></A-><B->BoundaryBelowAll</B-></TD-><TD CLASS="rdoc"->The boundary below all values.-</TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="section4"-><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:Boundary')" ALT="show/hide"-> Instances</TD-></TR-><TR-><TD CLASS="body"-><DIV ID="i:Boundary" STYLE="display:block;"-><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"-><TR-><TD CLASS="decl"->Arbitrary a => Arbitrary (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a)</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => Eq (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a)</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => Ord (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a)</TD-></TR-><TR-><TD CLASS="decl"->Show a => Show (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a)</TD-></TR-></TABLE-></DIV-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3Aabove"-></A-><B->above</B-> :: Ord v => <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> v -> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"->True if the value is above the boundary, false otherwise.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3A%2F%3E%2F"-></A-><B->(/>/)</B-> :: Ord v => v -> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"->Same as <TT-><A HREF="Data-Ranged-Boundaries.html#v%3Aabove"->above</A-></TT->, but with the arguments reversed for more intuitive infix- usage. -</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="botbar"->Produced by <A HREF="http://www.haskell.org/haddock/"->Haddock</A-> version 0.8</TD-></TR-></TABLE-></BODY-></HTML->
− Doc/Data-Ranged-RangedSet.html
@@ -1,1456 +0,0 @@-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">-<!--Rendered using the Haskell Html Library v0.2-->-<HTML-><HEAD-><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"-><TITLE->Data.Ranged.RangedSet</TITLE-><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"-><SCRIPT SRC="haddock.js" TYPE="text/javascript"-></SCRIPT-></HEAD-><BODY-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="topbar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "-></TD-><TD CLASS="title"-></TD-><TD CLASS="topbut"-><A HREF="index.html"->Contents</A-></TD-><TD CLASS="topbut"-><A HREF="doc-index.html"->Index</A-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="modulebar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><FONT SIZE="6"->Data.Ranged.RangedSet</FONT-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="section4"-><B->Contents</B-></TD-></TR-><TR-><TD-><DL-><DT-><A HREF="#1"->Ranged Set Type-</A-></DT-><DT-><A HREF="#2"->Ranged Set construction functions and their Preconditions-</A-></DT-><DT-><A HREF="#3"->Predicates-</A-></DT-><DT-><A HREF="#4"->Set Operations-</A-></DT-><DT-><A HREF="#5"->Useful Sets-</A-></DT-><DT-><A HREF="#6"->QuickCheck Properties-</A-></DT-><DD-><DL-><DT-><A HREF="#7"->Construction-</A-></DT-><DT-><A HREF="#8"->Basic Operations-</A-></DT-><DT-><A HREF="#9"->Some Identities and Inequalities-</A-></DT-></DL-></DD-></DL-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section1"->Synopsis</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="decl"-><SPAN CLASS="keyword"->data</SPAN-> <A HREF="#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetRanges"->rSetRanges</A-> :: <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v]</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3AmakeRangedSet"->makeRangedSet</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3AunsafeRangedSet"->unsafeRangedSet</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3AvalidRangeList"->validRangeList</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3AnormaliseRangeList"->normaliseRangeList</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v]</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSingleton"->rSingleton</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetIsEmpty"->rSetIsEmpty</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3A-%3F-"->(-?-)</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetHas"->rSetHas</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3A-%3C%3D-"->(-<=-)</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetIsSubset"->rSetIsSubset</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3A-%3C-"->(-<-)</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetIsSubsetStrict"->rSetIsSubsetStrict</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3A-%5C%2F-"->(-\/-)</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetUnion"->rSetUnion</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3A-%2F%5C-"->(-/\-)</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetIntersection"->rSetIntersection</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3A-%21-"->(-!-)</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetDifference"->rSetDifference</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetNegation"->rSetNegation</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetEmpty"->rSetEmpty</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetFull"->rSetFull</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArSetUnfold"->rSetUnfold</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a -> (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a -> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a) -> (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a -> Maybe (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a)) -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a</TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="1"->Ranged Set Type-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><SPAN CLASS="keyword"->data</SPAN-> <A NAME="t%3ARSet"-></A-><B->RSet</B-> v</TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="ndoc"->An RSet (for Ranged Set) is a list of ranges. The ranges must be sorted- and not overlap.-</TD-></TR-><TR-><TD CLASS="section4"-><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:RSet')" ALT="show/hide"-> Instances</TD-></TR-><TR-><TD CLASS="body"-><DIV ID="i:RSet" STYLE="display:block;"-><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"-><TR-><TD CLASS="decl"->(Arbitrary v, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v, Show v) => Arbitrary (<A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v)</TD-></TR-><TR-><TD CLASS="decl"->(<A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v, ??? v) => Eq (<A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v)</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => Monoid (<A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a)</TD-></TR-><TR-><TD CLASS="decl"->(<A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v, ??? v) => Show (<A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v)</TD-></TR-></TABLE-></DIV-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetRanges"-></A-><B->rSetRanges</B-> :: <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v]</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="2"->Ranged Set construction functions and their Preconditions-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3AmakeRangedSet"-></A-><B->makeRangedSet</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="doc"->Create a new Ranged Set from a list of ranges. The list may contain- ranges that overlap or are not in ascending order.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3AunsafeRangedSet"-></A-><B->unsafeRangedSet</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="doc"->Create a new Ranged Set from a list of ranges. <TT->validRangeList ranges</TT-> - must return <TT->True</TT->. This precondition is not checked.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3AvalidRangeList"-></A-><B->validRangeList</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> Bool</TD-></TR-><TR-><TD CLASS="doc"->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.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3AnormaliseRangeList"-></A-><B->normaliseRangeList</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v]</TD-></TR-><TR-><TD CLASS="doc"->Rearrange and merge the ranges in the list so that they are in order and- non-overlapping.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSingleton"-></A-><B->rSingleton</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="doc"->Create a Ranged Set from a single element.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="3"->Predicates-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetIsEmpty"-></A-><B->rSetIsEmpty</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"->True if the set has no members.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3A-%3F-"-></A-><B->(-?-)</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> v -> Bool</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetHas"-></A-><B->rSetHas</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"->True if the value is within the ranged set. Infix precedence is left 5.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3A-%3C%3D-"-></A-><B->(-<=-)</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetIsSubset"-></A-><B->rSetIsSubset</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"-><P->True if the first argument is a subset of the second argument, or is - equal. -</P-><P->Infix precedence is left 5.-</P-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3A-%3C-"-></A-><B->(-<-)</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetIsSubsetStrict"-></A-><B->rSetIsSubsetStrict</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"-><P->True if the first argument is a strict subset of the second argument.-</P-><P->Infix precedence is left 5.-</P-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="4"->Set Operations-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3A-%5C%2F-"-></A-><B->(-\/-)</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetUnion"-></A-><B->rSetUnion</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="doc"->Set union for ranged sets. Infix precedence is left 6.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3A-%2F%5C-"-></A-><B->(-/\-)</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetIntersection"-></A-><B->rSetIntersection</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="doc"->Set intersection for ranged sets. Infix precedence is left 7.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3A-%21-"-></A-><B->(-!-)</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetDifference"-></A-><B->rSetDifference</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> v</TD-></TR-><TR-><TD CLASS="doc"->Set difference. Infix precedence is left 6.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetNegation"-></A-><B->rSetNegation</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a</TD-></TR-><TR-><TD CLASS="doc"->Set negation.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="5"->Useful Sets-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetEmpty"-></A-><B->rSetEmpty</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a</TD-></TR-><TR-><TD CLASS="doc"->The empty set.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetFull"-></A-><B->rSetFull</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a</TD-></TR-><TR-><TD CLASS="doc"->The set that contains everything.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArSetUnfold"-></A-><B->rSetUnfold</B-></TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="arg"->:: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a</TD-><TD CLASS="rdoc"-></TD-></TR-><TR-><TD CLASS="arg"->=> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a</TD-><TD CLASS="rdoc"->A first lower boundary.-</TD-></TR-><TR-><TD CLASS="arg"->-> (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a -> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a)</TD-><TD CLASS="rdoc"->A function from a lower boundary to an upper boundary, which must- return a result greater than the argument (not checked).-</TD-></TR-><TR-><TD CLASS="arg"->-> (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a -> Maybe (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> a))</TD-><TD CLASS="rdoc"->A function from a lower boundary to <TT->Maybe</TT-> the successor lower - boundary, which must return a result greater than the argument - (not checked).-</TD-></TR-><TR-><TD CLASS="arg"->-> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->RSet</A-> a</TD-><TD CLASS="rdoc"-></TD-></TR-><TR-><TD CLASS="ndoc" COLSPAN="2"->Construct a range set.-</TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="6"->QuickCheck Properties-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section3"-><A NAME="7"->Construction-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="doc"-><P->A normalised range list is valid for unsafeRangedSet-</P-><PRE-> prop_validNormalised ls = validRangeList $ normaliseRangeList ls- where types = ls :: [Range Double]-</PRE-><P->Iff a value is in a range list then it is in a ranged set-constructed from that list.-</P-><PRE-> prop_has ls v = (ls `rangeListHas` v) == rangedSet ls -?- v-</PRE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section3"-><A NAME="8"->Basic Operations-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="doc"-><P->Iff a value is in either of two ranged sets then it is in the union of-those two sets.-</P-><PRE-> prop_union rs1 rs2 v =- (rs1 -?- v || rs2 -?- v) == ((rs1 -\/- rs2) -?- v)-</PRE-><P->Iff a value is in both of two ranged sets then it is in the intersection-of those two sets.-</P-><PRE-> prop_intersection rs1 rs2 v =- (rs1 -?- v && rs2 -?- v) == ((rs1 -/\- rs2) -?- v)-</PRE-><P->Iff a value is in ranged set 1 and not in ranged set 2 then it is in the-difference of the two.-</P-><PRE-> prop_difference rs1 rs2 v = - (rs1 -?- v && not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v)-</PRE-><P->Iff a value is not in a ranged set then it is in its negation. -</P-><PRE-> prop_negation rs v = rs -?- v == not (rSetNegation rs -?- v)-</PRE-><P->A set that contains a value is not empty-</P-><PRE-> prop_not_empty rs v = (rs -?- v) ==> not (rSetIsEmpty rs)-</PRE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section3"-><A NAME="9"->Some Identities and Inequalities-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="doc"-><P->The empty set has no members.-</P-><PRE-> prop_empty v = not (rSetEmpty -?- v)-</PRE-><P->The full set has every member.-</P-><PRE-> prop_full v = rSetFull -?- v-</PRE-><P->The intersection of a set with its negation is empty.-</P-><PRE-> prop_empty_intersection rs =- rSetIsEmpty (rs -/\- rSetNegation rs) -</PRE-><P->The union of a set with its negation is full.-</P-><PRE-> prop_full_union rs v =- rSetIsFull (rs -\/- rSetNegation rs)-</PRE-><P->The union of two sets is the non-strict superset of both.-</P-><PRE-> prop_union_superset rs1 rs2 =- rs1 -<=- u && rs2 -<=- u - where- u = rs1 -\/- rs2-</PRE-><P->The intersection of two sets is the non-strict subset of both.-</P-><PRE-> prop_intersection_subset rs1 rs2 =- i -<=- rs1 && i -<=- rs2- where- i = rs1 -/\- rs2-</PRE-><P->The difference of two sets intersected with the subtractand is empty.-</P-><PRE-> prop_diff_intersect rs1 rs2 =- rSetIsEmpty ((rs1 -!- rs2) -/\- rs2)-</PRE-><P->A set is the non-strict subset of itself.-</P-><PRE-> prop_subset rs = rs -<=- rs-</PRE-><P->A set is not the strict subset of itself.-</P-><PRE-> prop_strict_subset rs = not (rs -<- rs)-</PRE-><P->If rs1 - rs2 is not empty then the union of rs1 and rs2 will be a strict -superset of rs2.-</P-><PRE-> prop_union_strict_superset rs1 rs2 =- (not $ rSetIsEmpty (rs1 -!- rs2))- ==> (rs2 -<- (rs1 -\/- rs2))-</PRE-><P->Intersection commutes-</P-><PRE-> prop_intersection_commutes rs1 rs2 =- (rs1 -/\- rs2) == (rs2 -/\- rs1)-</PRE-><P->Union commutes-</P-><PRE-> prop_union_commutes rs1 rs2 =- (rs1 -\/- rs2) == (rs2 -\/- rs1)-</PRE-><P->Intersection associates-</P-><PRE-> prop_intersection_associates rs1 rs2 rs3 =- ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3))-</PRE-><P->Union associates-</P-><PRE-> prop_union_associates rs1 rs2 rs3 =- ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3))-</PRE-><P->De Morgan's Law for Intersection-</P-><PRE-> prop_de_morgan_intersection rs1 rs2 =- rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2)-</PRE-><P->De Morgan's Law for Union-</P-><PRE-> prop_de_morgan_union rs1 rs2 =- rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2)-</PRE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="botbar"->Produced by <A HREF="http://www.haskell.org/haddock/"->Haddock</A-> version 0.8</TD-></TR-></TABLE-></BODY-></HTML->
− Doc/Data-Ranged-Ranges.html
@@ -1,838 +0,0 @@-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">-<!--Rendered using the Haskell Html Library v0.2-->-<HTML-><HEAD-><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"-><TITLE->Data.Ranged.Ranges</TITLE-><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"-><SCRIPT SRC="haddock.js" TYPE="text/javascript"-></SCRIPT-></HEAD-><BODY-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="topbar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "-></TD-><TD CLASS="title"-></TD-><TD CLASS="topbut"-><A HREF="index.html"->Contents</A-></TD-><TD CLASS="topbut"-><A HREF="doc-index.html"->Index</A-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="modulebar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><FONT SIZE="6"->Data.Ranged.Ranges</FONT-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="section4"-><B->Contents</B-></TD-></TR-><TR-><TD-><DL-><DT-><A HREF="#1"->Construction-</A-></DT-><DT-><A HREF="#2"->Predicates-</A-></DT-><DT-><A HREF="#3"->Membership-</A-></DT-><DT-><A HREF="#4"->Set Operations-</A-></DT-><DT-><A HREF="#5"->QuickCheck properties-</A-></DT-></DL-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section1"->Description</TD-></TR-><TR-><TD CLASS="doc"->A range has an upper and lower boundary.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section1"->Synopsis</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="decl"-><SPAN CLASS="keyword"->data</SPAN-> <A HREF="#t%3ARange"->Range</A-> v = <A HREF="#v%3ARange"->Range</A-> {<TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="recfield"-><A HREF="#v%3ArangeLower"->rangeLower</A->, <A HREF="#v%3ArangeUpper"->rangeUpper</A-> :: (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> v)</TD-></TR-></TABLE->}</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3AemptyRange"->emptyRange</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3AfullRange"->fullRange</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArangeIsEmpty"->rangeIsEmpty</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArangeOverlap"->rangeOverlap</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArangeEncloses"->rangeEncloses</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArangeSingletonValue"->rangeSingletonValue</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> Maybe v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArangeHas"->rangeHas</A-> :: Ord v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArangeListHas"->rangeListHas</A-> :: Ord v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> v -> Bool</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3AsingletonRange"->singletonRange</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArangeIntersection"->rangeIntersection</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArangeUnion"->rangeUnion</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v]</TD-></TR-><TR-><TD CLASS="s8"-></TD-></TR-><TR-><TD CLASS="decl"-><A HREF="#v%3ArangeDifference"->rangeDifference</A-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v]</TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="1"->Construction-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><SPAN CLASS="keyword"->data</SPAN-> <A NAME="t%3ARange"-></A-><B->Range</B-> v</TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="ndoc"->A Range has upper and lower boundaries.-</TD-></TR-><TR-><TD CLASS="section4"->Constructors</TD-></TR-><TR-><TD CLASS="body"-><TABLE CLASS="vanilla" CELLSPACING="5" CELLPADDING="0"-><TR-><TD CLASS="arg"-><A NAME="v%3ARange"-></A-><B->Range</B-></TD-><TD CLASS="rdoc"-></TD-></TR-><TR-><TD CLASS="body" COLSPAN="2"-><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"-><TR-><TD CLASS="arg"-><A NAME="v%3ArangeLower"-></A-><B->rangeLower</B->, <A NAME="v%3ArangeUpper"-></A-><B->rangeUpper</B-> :: (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Boundary</A-> v)</TD-><TD CLASS="rdoc"-></TD-></TR-></TABLE-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="section4"-><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:Range')" ALT="show/hide"-> Instances</TD-></TR-><TR-><TD CLASS="body"-><DIV ID="i:Range" STYLE="display:block;"-><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"-><TR-><TD CLASS="decl"->(Arbitrary v, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v, Show v) => Arbitrary (<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v)</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => Eq (<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> a)</TD-></TR-><TR-><TD CLASS="decl"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a => Ord (<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> a)</TD-></TR-><TR-><TD CLASS="decl"->(Show a, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> a) => Show (<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> a)</TD-></TR-></TABLE-></DIV-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3AemptyRange"-></A-><B->emptyRange</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v</TD-></TR-><TR-><TD CLASS="doc"->The empty range-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3AfullRange"-></A-><B->fullRange</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v</TD-></TR-><TR-><TD CLASS="doc"->The full range. All values are within it.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="2"->Predicates-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArangeIsEmpty"-></A-><B->rangeIsEmpty</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"->A range is empty unless its upper boundary is greater than its lower- boundary.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArangeOverlap"-></A-><B->rangeOverlap</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"->Two ranges overlap if their intersection is non-empty.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArangeEncloses"-></A-><B->rangeEncloses</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"->The first range encloses the second if every value in the second range is - also within the first range. If the second range is empty then this is- always true.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArangeSingletonValue"-></A-><B->rangeSingletonValue</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> Maybe v</TD-></TR-><TR-><TD CLASS="doc"->If the range is a singleton, returns <TT->Just</TT-> the value. Otherwise returns- <TT->Nothing</TT->.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="3"->Membership-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArangeHas"-></A-><B->rangeHas</B-> :: Ord v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"->True if the value is within the range.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArangeListHas"-></A-><B->rangeListHas</B-> :: Ord v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v] -> v -> Bool</TD-></TR-><TR-><TD CLASS="doc"->True if the value is within one of the ranges.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="4"->Set Operations-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3AsingletonRange"-></A-><B->singletonRange</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v</TD-></TR-><TR-><TD CLASS="doc"->A range containing a single value-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArangeIntersection"-></A-><B->rangeIntersection</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v</TD-></TR-><TR-><TD CLASS="doc"->Intersection of two ranges, if any.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArangeUnion"-></A-><B->rangeUnion</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v]</TD-></TR-><TR-><TD CLASS="doc"-><P->Union of two ranges. Returns one or two results.-</P-><P->If there are two results then they are guaranteed to have a non-empty- gap in between, but may not be in ascending order.-</P-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"-><A NAME="v%3ArangeDifference"-></A-><B->rangeDifference</B-> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->DiscreteOrdered</A-> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"->Range</A-> v]</TD-></TR-><TR-><TD CLASS="doc"-><TT->range1</TT-> minus <TT->range2</TT->. Returns zero, one or two results. Multiple - results are guaranteed to have non-empty gaps in between, but may not be in - ascending order.-</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section2"-><A NAME="5"->QuickCheck properties-</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="doc"-><P->Range union-</P-><PRE-> prop_union r1 r2 n =- (r1 `rangeHas` n || r2 `rangeHas` n) - == (r1 `rangeUnion` r2) `rangeListHas` n-</PRE-><P->Range intersection-</P-><PRE-> prop_intersection r1 r2 n =- (r1 `rangeHas` n && r2 `rangeHas` n)- == (r1 `rangeIntersection` r2) `rangeHas` n-</PRE-><P->Range difference-</P-><PRE-> prop_difference r1 r2 n =- (r1 `rangeHas` n && not (r2 `rangeHas` n))- == (r1 `rangeDifference` r2) `rangeListHas` n-</PRE-><P->Singleton range-</P-><PRE-> prop_singletonHas v =- singletonRange v `rangeHas` v-</PRE-><PRE-> prop_singletonConverse v =- rangeSingletonValue (singletonRange v) == Just v-</PRE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="botbar"->Produced by <A HREF="http://www.haskell.org/haddock/"->Haddock</A-> version 0.8</TD-></TR-></TABLE-></BODY-></HTML->
− Doc/Data-Ranged.html
@@ -1,106 +0,0 @@-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">-<!--Rendered using the Haskell Html Library v0.2-->-<HTML-><HEAD-><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"-><TITLE->Data.Ranged</TITLE-><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"-><SCRIPT SRC="haddock.js" TYPE="text/javascript"-></SCRIPT-></HEAD-><BODY-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="topbar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "-></TD-><TD CLASS="title"-></TD-><TD CLASS="topbut"-><A HREF="index.html"->Contents</A-></TD-><TD CLASS="topbut"-><A HREF="doc-index.html"->Index</A-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="modulebar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><FONT SIZE="6"->Data.Ranged</FONT-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="section1"->Documentation</TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"->module <A HREF="Data-Ranged-Boundaries.html"->Data.Ranged.Boundaries</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"->module <A HREF="Data-Ranged-Ranges.html"->Data.Ranged.Ranges</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="decl"->module <A HREF="Data-Ranged-RangedSet.html"->Data.Ranged.RangedSet</A-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="botbar"->Produced by <A HREF="http://www.haskell.org/haddock/"->Haddock</A-> version 0.8</TD-></TR-></TABLE-></BODY-></HTML->
− Doc/doc-index.html
@@ -1,454 +0,0 @@-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">-<!--Rendered using the Haskell Html Library v0.2-->-<HTML-><HEAD-><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"-><TITLE-> (Index)</TITLE-><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"-></HEAD-><BODY-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="topbar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "-></TD-><TD CLASS="title"-></TD-><TD CLASS="topbut"-><A HREF="index.html"->Contents</A-></TD-><TD CLASS="topbut"-><A HREF="doc-index.html"->Index</A-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD-><TABLE CELLPADDING="0" CELLSPACING="5"-><TR-><TD CLASS="indexentry"->-!-</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3A-%21-"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->-/\-</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3A-%2F%5C-"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->-<-</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3A-%3C-"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->-<=-</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3A-%3C%3D-"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->-?-</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3A-%3F-"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->-\/-</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3A-%5C%2F-"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->/>/</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#v%3A%2F%3E%2F"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->Boundary</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->BoundaryAbove</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#v%3ABoundaryAbove"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->BoundaryAboveAll</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#v%3ABoundaryAboveAll"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->BoundaryBelow</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#v%3ABoundaryBelow"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->BoundaryBelowAll</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#v%3ABoundaryBelowAll"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->DiscreteOrdered</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->RSet</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#t%3ARSet"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry" COLSPAN="2"->Range</TD-></TR-><TR-><TD CLASS="indexannot"->1 (Type/Class)</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#t%3ARange"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexannot"->2 (Data Constructor)</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ARange"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->above</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#v%3Aabove"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->adjacent</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#v%3Aadjacent"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->boundedAdjacent</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#v%3AboundedAdjacent"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->emptyRange</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3AemptyRange"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->enumAdjacent</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Boundaries.html#v%3AenumAdjacent"->Data.Ranged.Boundaries</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->fullRange</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3AfullRange"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->makeRangedSet</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3AmakeRangedSet"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->normaliseRangeList</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3AnormaliseRangeList"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetDifference</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetDifference"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetEmpty</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetEmpty"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetFull</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetFull"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetHas</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetHas"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetIntersection</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetIntersection"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetIsEmpty</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetIsEmpty"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetIsSubset</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetIsSubset"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetIsSubsetStrict</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetIsSubsetStrict"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetNegation</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetNegation"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetRanges</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetRanges"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetUnfold</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetUnfold"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSetUnion</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSetUnion"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rSingleton</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3ArSingleton"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeDifference</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeDifference"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeEncloses</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeEncloses"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeHas</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeHas"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeIntersection</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeIntersection"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeIsEmpty</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeIsEmpty"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeListHas</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeListHas"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeLower</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeLower"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeOverlap</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeOverlap"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeSingletonValue</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeSingletonValue"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeUnion</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeUnion"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->rangeUpper</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3ArangeUpper"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->singletonRange</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-Ranges.html#v%3AsingletonRange"->Data.Ranged.Ranges</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->unsafeRangedSet</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3AunsafeRangedSet"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-><TR-><TD CLASS="indexentry"->validRangeList</TD-><TD CLASS="indexlinks"-><A HREF="Data-Ranged-RangedSet.html#v%3AvalidRangeList"->Data.Ranged.RangedSet</A->, Data.Ranged</TD-></TR-></TABLE-></TD-></TR-></TABLE-></BODY-></HTML->
− Doc/index.html
@@ -1,120 +0,0 @@-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">-<!--Rendered using the Haskell Html Library v0.2-->-<HTML-><HEAD-><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"-><TITLE-></TITLE-><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"-><SCRIPT SRC="haddock.js" TYPE="text/javascript"-></SCRIPT-></HEAD-><BODY-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD CLASS="topbar"-><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"-><TR-><TD-><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "-></TD-><TD CLASS="title"-></TD-><TD CLASS="topbut"-><A HREF="index.html"->Contents</A-></TD-><TD CLASS="topbut"-><A HREF="doc-index.html"->Index</A-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="section1"->Modules</TD-></TR-><TR-><TD-><TABLE CLASS="vanilla2" CELLSPACING="0" CELLPADDING="0"-><TR-><TD STYLE="width: 50em"-><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'n:0')" ALT="show/hide"->Data</TD-><TD-></TD-><TD-></TD-></TR-><TR-><TD STYLE="padding: 0; padding-left: 2em" COLSPAN="3"-><TABLE CLASS="vanilla2" CELLSPACING="0" CELLPADDING="0" ID="n:0" STYLE="display:block;"-><TR-><TD STYLE="width: 48em"-><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'n:1')" ALT="show/hide"-><A HREF="Data-Ranged.html"->Data.Ranged</A-></TD-><TD-></TD-><TD-></TD-></TR-><TR-><TD STYLE="padding: 0; padding-left: 2em" COLSPAN="3"-><TABLE CLASS="vanilla2" CELLSPACING="0" CELLPADDING="0" ID="n:1" STYLE="display:block;"-><TR-><TD STYLE="padding-left: 1.25em;width: 46em"-><A HREF="Data-Ranged-Boundaries.html"->Data.Ranged.Boundaries</A-></TD-><TD-></TD-><TD-></TD-></TR-><TR-><TD STYLE="padding-left: 1.25em;width: 46em"-><A HREF="Data-Ranged-RangedSet.html"->Data.Ranged.RangedSet</A-></TD-><TD-></TD-><TD-></TD-></TR-><TR-><TD STYLE="padding-left: 1.25em;width: 46em"-><A HREF="Data-Ranged-Ranges.html"->Data.Ranged.Ranges</A-></TD-><TD-></TD-><TD-></TD-></TR-></TABLE-></TD-></TR-></TABLE-></TD-></TR-></TABLE-></TD-></TR-><TR-><TD CLASS="s15"-></TD-></TR-><TR-><TD CLASS="botbar"->Produced by <A HREF="http://www.haskell.org/haddock/"->Haddock</A-> version 0.8</TD-></TR-></TABLE-></BODY-></HTML->
README.txt view
@@ -110,10 +110,14 @@ Unfortunately there is no simple way to guarantee that computations on infinite sets will terminate. So infinite sets are not supported. -QuickCheck-----------+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.cabal view
@@ -1,17 +1,21 @@ Name: Ranged-sets-Version: 0.1.1+Version: 0.2.0 License: BSD3 License-file: LICENSE.txt-Copyright: Paul Johnson, 2005, 2006, 2007+Copyright: Paul Johnson, 2005, 2006, 2007, 2008 Author: Paul Johnson-Homepage: http://ranged-sets.sourceforge.net/+Homepage: http://code.haskell.org/ranged-sets Maintainer: paul@cogito.org.uk Stability: beta-Category: Data -Build-Depends: base, QuickCheck+Category: Data+Build-Depends: base, QuickCheck, HUnit+Build-type: Simple Synopsis: Ranged sets for Haskell-Description: A ranged set is an ordered list of ranges. This allows sets - such as all reals x such that +Description: A ranged set is an ordered list of ranges. This allows sets+ such as all reals x such that (0.25 < x <= 0.75 or 1.4 <= x < 2.3 or 4.5 < x).-Exposed-modules: Data.Ranged, Data.Ranged.Boundaries, Data.Ranged.Ranges, Data.Ranged.RangedSet-Extra-source-files: README.txt CHANGES.txt INSTALL.txt TODO.txt Doc/Data-Ranged-Boundaries.html Doc/Data-Ranged.html Doc/Data-Ranged-RangedSet.html Doc/Data-Ranged-Ranges.html Doc/doc-index.html Doc/index.html +Exposed-modules: Data.Ranged, Data.Ranged.Boundaries, Data.Ranged.Ranges, + Data.Ranged.RangedSet+Extra-source-files: tests/Makefile, tests/Main.hs, README.txt, CHANGES.txt, + INSTALL.txt, TODO.txt+ghc-options: -Wall
+ tests/Main.hs view
@@ -0,0 +1,184 @@+{-# OPTIONS_GHC -fglasgow-exts #-}++module Main where++import Data.Ranged+import Test.HUnit+import Test.QuickCheck+++conf :: Config+conf = defaultConfig { configMaxTest = 1000, configMaxFail = 10000 }+++main :: IO ()+main = do+ putStrLn "QuickCheck Data.Ranged.Ranges:"+ putStrLn " Sparse type Integer:"+ putStrLn " * prop_unionRange"+ check conf $ \(r1 :: Range Integer) -> prop_unionRange r1+ putStrLn " * prop_unionRangeLength"+ check conf $ \(r1 :: Range Integer) -> prop_unionRangeLength r1+ putStrLn " * prop_intersectionRange"+ check conf $ \(r1 :: Range Integer) -> prop_intersectionRange r1+ putStrLn " * prop_intersectionOverlap"+ check conf $ \(r1 :: Range Integer) -> prop_intersectionOverlap r1+ putStrLn " * prop_enclosureUnion"+ check conf $ \(r1 :: Range Integer) -> prop_enclosureUnion r1+ putStrLn " * prop_differenceRange"+ check conf $ \(r1 :: Range Integer) -> prop_differenceRange r1+ putStrLn " * prop_singletonRangeHas"+ check conf $ \(v :: Integer) -> prop_singletonRangeHas v+ putStrLn " * prop_singletonRangeHasOnly"+ check conf $ \(v :: Integer) -> prop_singletonRangeHasOnly v+ putStrLn " * prop_singletonRangeConverse"+ check conf $ \(v :: Integer) -> prop_singletonRangeConverse v++ putStrLn " Dense type Double:"+ putStrLn " * prop_unionRange"+ check conf $ \(r1 :: Range Double) -> prop_unionRange r1+ putStrLn " * prop_unionRangeLength"+ check conf $ \(r1 :: Range Double) -> prop_unionRangeLength r1+ putStrLn " * prop_intersectionRange"+ check conf $ \(r1 :: Range Double) -> prop_intersectionRange r1+ putStrLn " * prop_intersectionOverlap"+ check conf $ \(r1 :: Range Integer) -> prop_intersectionOverlap r1+ putStrLn " * prop_enclosureUnion"+ check conf $ \(r1 :: Range Integer) -> prop_enclosureUnion r1+ putStrLn " * prop_differenceRange"+ check conf $ \(r1 :: Range Double) -> prop_differenceRange r1+ putStrLn " * prop_singletonRangeHas"+ check conf $ \(v :: Double) -> prop_singletonRangeHas v+ putStrLn " * prop_singletonRangeHasOnly"+ check conf $ \(v :: Double) -> prop_singletonRangeHasOnly v+ putStrLn " * prop_singletonRangeConverse"+ check conf $ \(v :: Double) -> prop_singletonRangeConverse v++ putStrLn " Type-insensitive tests:"+ putStrLn " * prop_emptyNonSingleton"+ check conf prop_emptyNonSingleton+ putStrLn " * prop_fullNonSingleton"+ check conf prop_fullNonSingleton+ putStrLn " * prop_nonSingleton"+ check conf prop_nonSingleton+ putStrLn " * prop_intSingleton"+ check conf prop_intSingleton++ putStrLn " Checking show for range:"+ runTestTT $ TestList + [+ TestCase $ assertEqual "Show range1" "3 <= x <= 8" $ + show $ Range (BoundaryBelow (3 :: Int)) (BoundaryAbove 8),+ TestCase $ assertEqual "Show range2" "x < 8" $+ show $ Range (BoundaryBelowAll) (BoundaryBelow (8 :: Int)),+ TestCase $ assertEqual "Show range3" "3 < x" $+ show $ Range (BoundaryAbove (3 :: Int)) (BoundaryAboveAll),+ TestCase $ assertEqual "Show singleton" "x == 4" $ + show $ singletonRange (4 :: Int),+ TestCase $ assertEqual "Show full" "All x" $ + show (fullRange :: Range Int),+ TestCase $ assertEqual "Show empty" "Empty" $ + show (emptyRange :: Range Int)+ ]++ putStrLn "QuickCheck Data.Ranged.RangedSet:"+ putStrLn " Sparse type Integer:"+ putStrLn " * prop_validNormalised"+ check conf $ \(rs :: [Range Integer]) -> prop_validNormalised rs+ putStrLn " * prop_has"+ check conf $ \(rs :: [Range Integer]) -> prop_has rs+ putStrLn " * prop_unfold"+ check conf prop_unfold+ putStrLn " * prop_union"+ check conf $ \(rset1 :: RSet Integer) -> prop_union rset1+ putStrLn " * prop_intersection"+ check conf $ \(rset1 :: RSet Integer) -> prop_intersection rset1+ putStrLn " * prop_difference"+ check conf $ \(rset1 :: RSet Integer) -> prop_difference rset1+ putStrLn " * prop_negation"+ check conf $ \(rset1 :: RSet Integer) -> prop_negation rset1+ putStrLn " * prop_not_empty"+ check conf $ \(rset1 :: RSet Integer) -> prop_not_empty rset1+ putStrLn " * prop_empty"+ check conf $ \(v :: Integer) -> prop_empty v+ putStrLn " * prop_full"+ check conf $ \(v :: Integer) -> prop_full v+ putStrLn " * prop_empty_intersection"+ check conf $ \(rset1 :: RSet Integer) -> prop_empty_intersection rset1+ putStrLn " * prop_full_union"+ check conf $ \(rset1 :: RSet Integer) -> prop_full_union rset1+ putStrLn " * prop_union_superset"+ check conf $ \(rset1 :: RSet Integer) -> prop_union_superset rset1+ putStrLn " * prop_intersection_subset"+ check conf $ \(rset1 :: RSet Integer) -> prop_intersection_subset rset1+ putStrLn " * prop_diff_intersect"+ check conf $ \(rset1 :: RSet Integer) -> prop_diff_intersect rset1+ putStrLn " * prop_subset"+ check conf $ \(rset1 :: RSet Integer) -> prop_subset rset1+ putStrLn " * prop_strict_subset"+ check conf $ \(rset1 :: RSet Integer) -> prop_strict_subset rset1+ putStrLn " * prop_union_strict_superset"+ check conf $ \(rset1 :: RSet Integer) -> prop_union_strict_superset rset1+ putStrLn " * prop_intersection_commutes"+ check conf $ \(rset1 :: RSet Integer) -> prop_intersection_commutes rset1+ putStrLn " * prop_union_commutes"+ check conf $ \(rset1 :: RSet Integer) -> prop_union_commutes rset1+ putStrLn " * prop_intersection_associates"+ check conf $ \(rset1 :: RSet Integer) -> prop_intersection_associates rset1+ putStrLn " * prop_union_associates"+ check conf $ \(rset1 :: RSet Integer) -> prop_union_associates rset1+ putStrLn " * prop_de_morgan_intersection"+ check conf $ \(rset1 :: RSet Integer) -> prop_de_morgan_intersection rset1+ putStrLn " * prop_de_morgan_union"+ check conf $ \(rset1 :: RSet Integer) -> prop_de_morgan_union rset1++ putStrLn " Dense type Double:"+ putStrLn " * prop_validNormalised"+ check conf $ \(rs :: [Range Double]) -> prop_validNormalised rs+ putStrLn " * prop_has"+ check conf $ \(rs :: [Range Double]) -> prop_has rs+ putStrLn " * prop_unfold"+ check conf prop_unfold+ putStrLn " * prop_union"+ check conf $ \(rset1 :: RSet Double) -> prop_union rset1+ putStrLn " * prop_intersection"+ check conf $ \(rset1 :: RSet Double) -> prop_intersection rset1+ putStrLn " * prop_difference"+ check conf $ \(rset1 :: RSet Double) -> prop_difference rset1+ putStrLn " * prop_negation"+ check conf $ \(rset1 :: RSet Double) -> prop_negation rset1+ putStrLn " * prop_not_empty"+ check conf $ \(rset1 :: RSet Double) -> prop_not_empty rset1+ putStrLn " * prop_empty"+ check conf $ \(v :: Double) -> prop_empty v+ putStrLn " * prop_full"+ check conf $ \(v :: Double) -> prop_full v+ putStrLn " * prop_empty_intersection"+ check conf $ \(rset1 :: RSet Double) -> prop_empty_intersection rset1+ putStrLn " * prop_full_union"+ check conf $ \(rset1 :: RSet Double) -> prop_full_union rset1+ putStrLn " * prop_union_superset"+ check conf $ \(rset1 :: RSet Double) -> prop_union_superset rset1+ putStrLn " * prop_intersection_subset"+ check conf $ \(rset1 :: RSet Double) -> prop_intersection_subset rset1+ putStrLn " * prop_diff_intersect"+ check conf $ \(rset1 :: RSet Double) -> prop_diff_intersect rset1+ putStrLn " * prop_subset"+ check conf $ \(rset1 :: RSet Double) -> prop_subset rset1+ putStrLn " * prop_strict_subset"+ check conf $ \(rset1 :: RSet Double) -> prop_strict_subset rset1+ putStrLn " * prop_union_strict_superset"+ check conf $ \(rset1 :: RSet Double) -> prop_union_strict_superset rset1+ putStrLn " * prop_intersection_commutes"+ check conf $ \(rset1 :: RSet Double) -> prop_intersection_commutes rset1+ putStrLn " * prop_union_commutes"+ check conf $ \(rset1 :: RSet Double) -> prop_union_commutes rset1+ putStrLn " * prop_intersection_associates"+ check conf $ \(rset1 :: RSet Double) -> prop_intersection_associates rset1+ putStrLn " * prop_union_associates"+ check conf $ \(rset1 :: RSet Double) -> prop_union_associates rset1+ putStrLn " * prop_de_morgan_intersection"+ check conf $ \(rset1 :: RSet Double) -> prop_de_morgan_intersection rset1+ putStrLn " * prop_de_morgan_union"+ check conf $ \(rset1 :: RSet Double) -> prop_de_morgan_union rset1+
+ tests/Makefile view
@@ -0,0 +1,16 @@+# Tests for Ranged Sets.++all:+ ghc --make -fhpc -i.. -odir . -hidir . -Wall Main.hs -o test-rset+ rm -f test-rset.tix+ ./test-rset+ hpc markup --destdir=Report test-rset+ hpc report test-rset++clean:+ rm -fR Data+ rm -f test-rset.tix+ rm -f test-rset+ rm -f *.o *.hi+ rm -fR Report+