libghc-ranged-sets-doc 0.3.0-5build2 / usr / share / doc / libghc-ranged-sets-doc / html / Ranged-sets.txt

-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Ranged sets for Haskell
--   
--   A ranged set is an ordered list of ranges. This allows sets such as
--   all reals x such that:
--   
--   <pre>
--   (0.25 &lt; x &lt;= 0.75 or 1.4 &lt;= x &lt; 2.3 or 4.5 &lt; x)
--   </pre>
--   
--   Alternatively you can have all strings s such that:
--   
--   <pre>
--   ("F" &lt;= s &lt; "G")
--   </pre>
@package Ranged-sets
@version 0.3.0


module Data.Ranged.Boundaries

-- | Distinguish between dense and sparse ordered types. A dense type is
--   one in which any two values <tt>v1 &lt; v2</tt> have a third value
--   <tt>v3</tt> such that <tt>v1 &lt; v3 &lt; v2</tt>.
--   
--   In theory the floating types are dense, although in practice they can
--   only have finitely many values. This class treats them as dense.
--   
--   Tuples up to 4 members are declared as instances. Larger tuples may be
--   added if necessary.
--   
--   Most values of sparse types have an <tt>adjacentBelow</tt>, such that,
--   for all x:
--   
--   <pre>
--   case adjacentBelow x of
--      Just x1 -&gt; adjacent x1 x
--      Nothing -&gt; True
--   </pre>
--   
--   The exception is for bounded types when <tt>x == lowerBound</tt>. For
--   dense types <tt>adjacentBelow</tt> always returns <a>Nothing</a>.
--   
--   This approach was suggested by Ben Rudiak-Gould on
--   comp.lang.functional.
class Ord a => DiscreteOrdered a
adjacent :: DiscreteOrdered a => a -> a -> Bool
adjacentBelow :: DiscreteOrdered a => a -> Maybe a

-- | Check adjacency for sparse enumerated types (i.e. where there is no
--   value between <tt>x</tt> and <tt>succ x</tt>).
enumAdjacent :: (Ord a, Enum a) => a -> a -> Bool

-- | Check adjacency, allowing for case where x = maxBound. Use as the
--   definition of <a>adjacent</a> for bounded enumerated types such as Int
--   and Char.
boundedAdjacent :: (Ord a, Enum a) => a -> a -> Bool

-- | The usual implementation of <a>adjacentBelow</a> for bounded
--   enumerated types.
boundedBelow :: (Eq a, Enum a, Bounded a) => a -> Maybe a

-- | 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
--   
--   <ul>
--   <li><pre>BoundaryAbove maxBound &lt; BoundaryAboveAll</pre></li>
--   <li><pre>BoundaryBelow minBound &gt; BoundaryBelowAll</pre></li>
--   </ul>
--   
--   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 -> Boundary a

-- | The argument is the lowest value above the boundary.
BoundaryBelow :: a -> Boundary a

-- | The boundary above all values.
BoundaryAboveAll :: Boundary a

-- | The boundary below all values.
BoundaryBelowAll :: Boundary a

-- | True if the value is above the boundary, false otherwise.
above :: Ord v => Boundary v -> v -> Bool

-- | Same as <a>above</a>, but with the arguments reversed for more
--   intuitive infix usage.
(/>/) :: Ord v => v -> Boundary v -> Bool
instance Show a => Show (Boundary a)
instance CoArbitrary a => CoArbitrary (Boundary a)
instance Arbitrary a => Arbitrary (Boundary a)
instance DiscreteOrdered a => Ord (Boundary a)
instance DiscreteOrdered a => Eq (Boundary a)
instance (Ord a, Ord b, Ord c, DiscreteOrdered d) => DiscreteOrdered (a, b, c, d)
instance (Ord a, Ord b, DiscreteOrdered c) => DiscreteOrdered (a, b, c)
instance (Ord a, DiscreteOrdered b) => DiscreteOrdered (a, b)
instance Ord a => DiscreteOrdered [a]
instance Integral a => DiscreteOrdered (Ratio a)
instance DiscreteOrdered Float
instance DiscreteOrdered Double
instance DiscreteOrdered Integer
instance DiscreteOrdered Int
instance DiscreteOrdered Char
instance DiscreteOrdered Ordering
instance DiscreteOrdered Bool


-- | A range has an upper and lower boundary.
module Data.Ranged.Ranges

-- | A Range has upper and lower boundaries.
data Ord v => Range v
Range :: Boundary v -> Boundary v -> Range v
rangeLower :: Range v -> Boundary v
rangeUpper :: Range v -> Boundary v

-- | The empty range
emptyRange :: DiscreteOrdered v => Range v

-- | The full range. All values are within it.
fullRange :: DiscreteOrdered v => Range v

-- | A range is empty unless its upper boundary is greater than its lower
--   boundary.
rangeIsEmpty :: DiscreteOrdered v => Range v -> Bool

-- | A range is full if it contains every possible value.
rangeIsFull :: DiscreteOrdered v => Range v -> Bool

-- | Two ranges overlap if their intersection is non-empty.
rangeOverlap :: DiscreteOrdered v => Range v -> Range v -> Bool

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

-- | If the range is a singleton, returns <tt>Just</tt> the value.
--   Otherwise returns <tt>Nothing</tt>.
--   
--   Known bug: This always returns <tt>Nothing</tt> for ranges including
--   <tt>BoundaryBelowAll</tt> or <tt>BoundaryAboveAll</tt>. For bounded
--   types this can be incorrect. For instance, the following range only
--   contains one value:
--   
--   <pre>
--   Range (BoundaryBelow maxBound) BoundaryAboveAll
--   </pre>
rangeSingletonValue :: DiscreteOrdered v => Range v -> Maybe v

-- | True if the value is within the range.
rangeHas :: Ord v => Range v -> v -> Bool

-- | True if the value is within one of the ranges.
rangeListHas :: Ord v => [Range v] -> v -> Bool

-- | A range containing a single value
singletonRange :: DiscreteOrdered v => v -> Range v

-- | Intersection of two ranges, if any.
rangeIntersection :: DiscreteOrdered v => Range v -> Range v -> Range v

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

-- | <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.
rangeDifference :: DiscreteOrdered v => Range v -> Range v -> [Range v]

-- | The union of two ranges has a value iff either range has it.
--   
--   <pre>
--   prop_unionRange r1 r2 n =
--      (r1 `rangeHas` n || r2 `rangeHas` n)
--      == (r1 `rangeUnion` r2) `rangeListHas` n
--   </pre>
prop_unionRange :: DiscreteOrdered a => Range a -> Range a -> a -> Bool

-- | The union of two ranges always contains one or two ranges.
--   
--   <pre>
--   prop_unionRangeLength r1 r2 = (n == 1) || (n == 2)
--      where n = length $ rangeUnion r1 r2
--   </pre>
prop_unionRangeLength :: DiscreteOrdered a => Range a -> Range a -> Bool

-- | The intersection of two ranges has a value iff both ranges have it.
--   
--   <pre>
--   prop_intersectionRange r1 r2 n =
--      (r1 `rangeHas` n &amp;&amp; r2 `rangeHas` n)
--      == (r1 `rangeIntersection` r2) `rangeHas` n
--   </pre>
prop_intersectionRange :: DiscreteOrdered a => Range a -> Range a -> a -> Bool

-- | The difference of two ranges has a value iff the first range has it
--   and the second does not.
--   
--   <pre>
--   prop_differenceRange r1 r2 n =
--      (r1 `rangeHas` n &amp;&amp; not (r2 `rangeHas` n))
--      == (r1 `rangeDifference` r2) `rangeListHas` n
--   </pre>
prop_differenceRange :: DiscreteOrdered a => Range a -> Range a -> a -> Bool

-- | Iff two ranges overlap then their intersection is non-empty.
--   
--   <pre>
--   prop_intersectionOverlap r1 r2 =
--       (rangeIsEmpty $ rangeIntersection r1 r2) == (rangeOverlap r1 r2)
--   </pre>
prop_intersectionOverlap :: DiscreteOrdered a => Range a -> Range a -> Bool

-- | Range enclosure makes union an identity function.
--   
--   <pre>
--   prop_enclosureUnion r1 r2 =
--      rangeEncloses r1 r2 == (rangeUnion r1 r2 == [r1])
--   </pre>
prop_enclosureUnion :: DiscreteOrdered a => Range a -> Range a -> Bool

-- | Range Singleton has its member.
--   
--   <pre>
--   prop_singletonRangeHas v = singletonRange v `rangeHas` v
--   </pre>
prop_singletonRangeHas :: DiscreteOrdered a => a -> Bool

-- | Range Singleton has only its member.
--   
--   <pre>
--   prop_singletonHasOnly v1 v2 =
--      (v1 == v2) == (singletonRange v1 `rangeHas` v2)
--   </pre>
prop_singletonRangeHasOnly :: DiscreteOrdered a => a -> a -> Bool

-- | A singleton range can have its value extracted.
--   
--   <pre>
--   prop_singletonRangeConverse v =
--      rangeSingletonValue (singletonRange v) == Just v
--   </pre>
prop_singletonRangeConverse :: DiscreteOrdered a => a -> Bool

-- | The empty range is not a singleton.
--   
--   <pre>
--   prop_emptyNonSingleton = rangeSingletonValue emptyRange == Nothing
--   </pre>
prop_emptyNonSingleton :: Bool

-- | The full range is not a singleton.
--   
--   <pre>
--   prop_fullNonSingleton = rangeSingletonValue fullRange == Nothing
--   </pre>
prop_fullNonSingleton :: Bool

-- | For real x and y, <tt>x &lt; y</tt> implies that any range between
--   them is a non-singleton.
prop_nonSingleton :: Double -> Double -> Property

-- | 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
instance (CoArbitrary v, DiscreteOrdered v, Show v) => CoArbitrary (Range v)
instance (Arbitrary v, DiscreteOrdered v, Show v) => Arbitrary (Range v)
instance (Show a, DiscreteOrdered a) => Show (Range a)
instance DiscreteOrdered a => Ord (Range a)
instance DiscreteOrdered a => Eq (Range a)

module Data.Ranged.RangedSet

-- | An RSet (for Ranged Set) is a list of ranges. The ranges must be
--   sorted and not overlap.
data DiscreteOrdered v => RSet v
rSetRanges :: RSet v -> [Range v]

-- | Create a new Ranged Set from a list of ranges. The list may contain
--   ranges that overlap or are not in ascending order.
makeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v

-- | Create a new Ranged Set from a list of ranges. <tt>validRangeList
--   ranges</tt> must return <tt>True</tt>. This precondition is not
--   checked.
unsafeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v

-- | 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.
validRangeList :: DiscreteOrdered v => [Range v] -> Bool

-- | Rearrange and merge the ranges in the list so that they are in order
--   and non-overlapping.
normaliseRangeList :: DiscreteOrdered v => [Range v] -> [Range v]

-- | Create a Ranged Set from a single element.
rSingleton :: DiscreteOrdered v => v -> RSet v

-- | Construct a range set.
rSetUnfold :: DiscreteOrdered a => Boundary a -> (Boundary a -> Boundary a) -> (Boundary a -> Maybe (Boundary a)) -> RSet a

-- | True if the set has no members.
rSetIsEmpty :: DiscreteOrdered v => RSet v -> Bool

-- | True if the negation of the set has no members.
rSetIsFull :: DiscreteOrdered v => RSet v -> Bool

-- | True if the value is within the ranged set. Infix precedence is left
--   5.
(-?-) :: DiscreteOrdered v => RSet v -> v -> Bool

-- | True if the value is within the ranged set. Infix precedence is left
--   5.
rSetHas :: DiscreteOrdered v => RSet v -> v -> Bool

-- | True if the first argument is a subset of the second argument, or is
--   equal.
--   
--   Infix precedence is left 5.
(-<=-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool

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

-- | True if the first argument is a strict subset of the second argument.
--   
--   Infix precedence is left 5.
(-<-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool

-- | True if the first argument is a strict subset of the second argument.
--   
--   Infix precedence is left 5.
rSetIsSubsetStrict :: DiscreteOrdered v => RSet v -> RSet v -> Bool

-- | Set union for ranged sets. Infix precedence is left 6.
(-\/-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v

-- | Set union for ranged sets. Infix precedence is left 6.
rSetUnion :: DiscreteOrdered v => RSet v -> RSet v -> RSet v

-- | Set intersection for ranged sets. Infix precedence is left 7.
(-/\-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v

-- | Set intersection for ranged sets. Infix precedence is left 7.
rSetIntersection :: DiscreteOrdered v => RSet v -> RSet v -> RSet v

-- | Set difference. Infix precedence is left 6.
(-!-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v

-- | Set difference. Infix precedence is left 6.
rSetDifference :: DiscreteOrdered v => RSet v -> RSet v -> RSet v

-- | Set negation.
rSetNegation :: DiscreteOrdered a => RSet a -> RSet a

-- | The empty set.
rSetEmpty :: DiscreteOrdered a => RSet a

-- | The set that contains everything.
rSetFull :: DiscreteOrdered a => RSet a

-- | A normalised range list is valid for unsafeRangedSet
--   
--   <pre>
--   prop_validNormalised ls = validRangeList $ normaliseRangeList ls
--   </pre>
prop_validNormalised :: DiscreteOrdered a => [Range a] -> Bool

-- | Iff a value is in a range list then it is in a ranged set constructed
--   from that list.
--   
--   <pre>
--   prop_has ls v = (ls `rangeListHas` v) == makeRangedSet ls -?- v
--   </pre>
prop_has :: DiscreteOrdered a => [Range a] -> a -> Bool

-- | Verifies the correct membership of a set containing all integers
--   starting with the digit "1" up to 19999.
--   
--   <pre>
--   prop_unfold = (v &lt;= 99999 &amp;&amp; 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 &lt;= 1000 then Just $ BoundaryBelow $ n * 10 else Nothing
--   </pre>
prop_unfold :: Integer -> Bool

-- | Iff a value is in either of two ranged sets then it is in the union of
--   those two sets.
--   
--   <pre>
--   prop_union rs1 rs2 v =
--      (rs1 -?- v || rs2 -?- v) == ((rs1 -\/- rs2) -?- v)
--   </pre>
prop_union :: DiscreteOrdered a => RSet a -> RSet a -> a -> Bool

-- | Iff a value is in both of two ranged sets then it is n the
--   intersection of those two sets.
--   
--   <pre>
--   prop_intersection rs1 rs2 v =
--      (rs1 -?- v &amp;&amp; rs2 -?- v) == ((rs1 -/\- rs2) -?- v)
--   </pre>
prop_intersection :: DiscreteOrdered a => RSet a -> RSet a -> a -> Bool

-- | Iff a value is in ranged set 1 and not in ranged set 2 then it is in
--   the difference of the two.
--   
--   <pre>
--   prop_difference rs1 rs2 v =
--      (rs1 -?- v &amp;&amp; not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v)
--   </pre>
prop_difference :: DiscreteOrdered a => RSet a -> RSet a -> a -> Bool

-- | Iff a value is not in a ranged set then it is in its negation.
--   
--   <pre>
--   prop_negation rs v = rs -?- v == not (rSetNegation rs -?- v)
--   </pre>
prop_negation :: DiscreteOrdered a => RSet a -> a -> Bool

-- | A set that contains a value is not empty
--   
--   <pre>
--   prop_not_empty rs v = (rs -?- v) ==&gt; not (rSetIsEmpty rs)
--   </pre>
prop_not_empty :: DiscreteOrdered a => RSet a -> a -> Property

-- | The empty set has no members.
--   
--   <pre>
--   prop_empty v = not (rSetEmpty -?- v)
--   </pre>
prop_empty :: DiscreteOrdered a => a -> Bool

-- | The full set has every member.
--   
--   <pre>
--   prop_full v = rSetFull -?- v
--   </pre>
prop_full :: DiscreteOrdered a => a -> Bool

-- | The intersection of a set with its negation is empty.
--   
--   <pre>
--   prop_empty_intersection rs =
--      rSetIsEmpty (rs -/\- rSetNegation rs)
--   </pre>
prop_empty_intersection :: DiscreteOrdered a => RSet a -> Bool

-- | The union of a set with its negation is full.
--   
--   <pre>
--   prop_full_union rs v =
--      rSetIsFull (rs -\/- rSetNegation rs)
--   </pre>
prop_full_union :: DiscreteOrdered a => RSet a -> Bool

-- | The union of two sets is the non-strict superset of both.
--   
--   <pre>
--   prop_union_superset rs1 rs2 =
--      rs1 -&lt;=- u &amp;&amp; rs2 -&lt;=- u
--      where
--         u = rs1 -\/- rs2
--   </pre>
prop_union_superset :: DiscreteOrdered a => RSet a -> RSet a -> Bool

-- | The intersection of two sets is the non-strict subset of both.
--   
--   <pre>
--   prop_intersection_subset rs1 rs2 =
--      i -&lt;=- rs1 &amp;&amp; i -&lt;=- rs2
--      where
--         i = rs1 -/\- rs2
--   </pre>
prop_intersection_subset :: DiscreteOrdered a => RSet a -> RSet a -> Bool

-- | The difference of two sets intersected with the subtractand is empty.
--   
--   <pre>
--   prop_diff_intersect rs1 rs2 =
--      rSetIsEmpty ((rs1 -!- rs2) -/\- rs2)
--   </pre>
prop_diff_intersect :: DiscreteOrdered a => RSet a -> RSet a -> Bool

-- | A set is the non-strict subset of itself.
--   
--   <pre>
--   prop_subset rs = rs -&lt;=- rs
--   </pre>
prop_subset :: DiscreteOrdered a => RSet a -> Bool

-- | A set is not the strict subset of itself.
--   
--   <pre>
--   prop_strict_subset rs = not (rs -&lt;- rs)
--   </pre>
prop_strict_subset :: DiscreteOrdered a => RSet a -> Bool

-- | If rs1 - rs2 is not empty then the union of rs1 and rs2 will be a
--   strict superset of rs2.
--   
--   <pre>
--   prop_union_strict_superset rs1 rs2 =
--      (not $ rSetIsEmpty (rs1 -!- rs2))
--      ==&gt; (rs2 -&lt;- (rs1 -\/- rs2))
--   </pre>
prop_union_strict_superset :: DiscreteOrdered a => RSet a -> RSet a -> Property

-- | Intersection commutes.
--   
--   <pre>
--   prop_intersection_commutes rs1 rs2 = (rs1 -/\- rs2) == (rs2 -/\- rs1)
--   </pre>
prop_intersection_commutes :: DiscreteOrdered a => RSet a -> RSet a -> Bool

-- | Union commutes.
--   
--   <pre>
--   prop_union_commutes rs1 rs2 = (rs1 -\/- rs2) == (rs2 -\/- rs1)
--   </pre>
prop_union_commutes :: DiscreteOrdered a => RSet a -> RSet a -> Bool

-- | Intersection associates.
--   
--   <pre>
--   prop_intersection_associates rs1 rs2 rs3 =
--      ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3))
--   </pre>
prop_intersection_associates :: DiscreteOrdered a => RSet a -> RSet a -> RSet a -> Bool

-- | Union associates.
--   
--   <pre>
--   prop_union_associates rs1 rs2 rs3 =
--      ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3))
--   </pre>
prop_union_associates :: DiscreteOrdered a => RSet a -> RSet a -> RSet a -> Bool

-- | De Morgan's Law for Intersection.
--   
--   <pre>
--   prop_de_morgan_intersection rs1 rs2 =
--      rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2)
--   </pre>
prop_de_morgan_intersection :: DiscreteOrdered a => RSet a -> RSet a -> Bool

-- | De Morgan's Law for Union.
--   
--   <pre>
--   prop_de_morgan_union rs1 rs2 =
--      rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2)
--   </pre>
prop_de_morgan_union :: DiscreteOrdered a => RSet a -> RSet a -> Bool
instance DiscreteOrdered v => Eq (RSet v)
instance (Show v, DiscreteOrdered v) => Show (RSet v)
instance (CoArbitrary v, DiscreteOrdered v, Show v) => CoArbitrary (RSet v)
instance (Arbitrary v, DiscreteOrdered v, Show v) => Arbitrary (RSet v)
instance DiscreteOrdered a => Monoid (RSet a)

module Data.Ranged