packages feed

range 0.3.2.0 → 0.3.2.1

raw patch · 8 files changed

+370/−101 lines, 8 filesdep +doctest

Dependencies added: doctest

Files

Data/Range.hs view
@@ -7,6 +7,14 @@ -- -- __Note:__ It is intended that you will read the documentation in this module from top to bottom. --+-- = Module guide+--+-- * "Data.Range" — __start here__. Direct functions on @['Range' a]@.+-- * "Data.Ranges" — 'Data.Ranges.Ranges' newtype with 'Monoid' \/ 'Semigroup' semantics (@('<>')@ means union).+-- * "Data.Range.Ord" — 'Data.Range.Ord.KeyRange' and 'Data.Range.Ord.SortedRange' newtypes for 'Ord'-requiring contexts.+-- * "Data.Range.Parser" — Parsec-based parser for CLI range strings.+-- * "Data.Range.Algebra" — F-Algebra for deferred, efficient expression trees.+-- -- = Understanding custom range syntax -- -- This library supports five different types of ranges:@@ -135,48 +143,50 @@ import qualified Data.Range.Algebra as Alg  -- | Performs a set union between the two input ranges and returns the resultant set of--- ranges.------ For example:+-- ranges. The output is already in merged (canonical) form; a subsequent call to+-- 'mergeRanges' is redundant. -- -- >>> union [1 +=+ 10] [5 +=+ (15 :: Integer)] -- [1 +=+ 15]--- (0.00 secs, 587,152 bytes)+--+-- See also 'intersection', 'difference', 'invert'. union :: (Ord a) => [Range a] -> [Range a] -> [Range a] union a b = Alg.eval $ Alg.union (Alg.const a) (Alg.const b) {-# INLINE union #-}  -- | Performs a set intersection between the two input ranges and returns the resultant set of--- ranges.------ For example:+-- ranges. The output is already in merged (canonical) form; a subsequent call to+-- 'mergeRanges' is redundant. -- -- >>> intersection [1 +=* 10] [5 +=+ (15 :: Integer)] -- [5 +=* 10]--- (0.00 secs, 584,616 bytes)+--+-- See also 'union', 'difference', 'invert'. intersection :: (Ord a) => [Range a] -> [Range a] -> [Range a] intersection a b = Alg.eval $ Alg.intersection (Alg.const a) (Alg.const b) {-# INLINE intersection #-}  -- | Performs a set difference between the two input ranges and returns the resultant set of--- ranges.------ For example:+-- ranges. The output is already in merged (canonical) form; a subsequent call to+-- 'mergeRanges' is redundant. -- -- >>> difference [1 +=+ 10] [5 +=+ (15 :: Integer)] -- [1 +=* 5]--- (0.00 secs, 590,424 bytes)+--+-- See also 'union', 'intersection', 'invert'. difference :: (Ord a) => [Range a] -> [Range a] -> [Range a] difference a b = Alg.eval $ Alg.difference (Alg.const a) (Alg.const b) {-# INLINE difference #-} --- | An inversion function, given a set of ranges it returns the inverse set of ranges.------ For example:+-- | Returns the complement of the given ranges: all values /not/ covered by any+-- of the input ranges. -- -- >>> invert [1 +=* 10, 15 *=+ (20 :: Integer)] -- [ube 1,10 +=+ 15,lbe 20]--- (0.00 secs, 623,456 bytes)+--+-- Note that @'invert' . 'invert' == 'id'@ for any list of ranges.+--+-- See also 'union', 'intersection', 'difference'. invert :: (Ord a) => [Range a] -> [Range a] invert = Alg.eval . Alg.invert . Alg.const {-# INLINE invert #-}@@ -230,9 +240,11 @@ rangesAdjoin :: (Ord a) => Range a -> Range a -> Bool rangesAdjoin a b = Adjoin == (rangesOverlapType a b) --- | Given a range and a value it will tell you wether or not the value is in the range.--- Remember that all ranges are inclusive.+-- | Given a range and a value, returns 'True' if the value is within the range.+-- Respects 'Inclusive' and 'Exclusive' bounds. --+-- See also 'inRanges' for testing against a list of ranges.+-- -- The primary value of this library is performance and this method can be used to show -- this quite clearly. For example, you can try and approximate basic range functionality -- with "Data.List.elem" so we can generate an apples to apples comparison in GHCi:@@ -255,8 +267,18 @@ inRange (UpperBoundRange upper) value = Overlap == againstUpperBound (Bound value Inclusive) upper inRange InfiniteRange _ = True --- | Given a list of ranges this function tells you if a value is in any of those ranges.--- This is especially useful for more complex ranges.+-- | Returns 'True' if the value falls within any of the given ranges.+-- This is the primary membership test for the library and is significantly more+-- performant than approximating it with @'elem' x [lo..hi]@.+--+-- >>> inRanges [1 +=+ 10, 20 +=+ 30] (5 :: Integer)+-- True+-- >>> inRanges [1 +=+ 10, 20 +=+ 30] (15 :: Integer)+-- False+-- >>> inRanges [] (0 :: Integer)+-- False+--+-- See also 'inRange' for testing against a single range. inRanges :: (Ord a) => [Range a] -> a -> Bool inRanges rs a = any (`inRange` a) rs @@ -287,7 +309,17 @@ aboveRange (UpperBoundRange upper)  value = Overlap == againstLowerBound (Bound value Inclusive) (invertBound upper) aboveRange InfiniteRange            _     = False --- | Checks if the value provided is above all of the ranges provided.+-- | Returns 'True' if the value is strictly above (greater than the upper bound of)+-- all of the given ranges.+--+-- >>> aboveRanges [1 +=+ 5, 10 +=+ 15] (20 :: Integer)+-- True+-- >>> aboveRanges [1 +=+ 5, lbi 10] (20 :: Integer)+-- False+-- >>> aboveRanges [] (0 :: Integer)+-- True+--+-- See also 'aboveRange', 'belowRanges'. aboveRanges :: (Ord a) => [Range a] -> a -> Bool aboveRanges rs a = all (`aboveRange` a) rs @@ -318,7 +350,17 @@ belowRange (UpperBoundRange _)      _     = False belowRange InfiniteRange            _     = False --- | Checks if the value provided is below all of the ranges provided.+-- | Returns 'True' if the value is strictly below (less than the lower bound of)+-- all of the given ranges.+--+-- >>> belowRanges [5 +=+ 10, 20 +=+ 30] (1 :: Integer)+-- True+-- >>> belowRanges [ubi 10, 20 +=+ 30] (1 :: Integer)+-- False+-- >>> belowRanges [] (0 :: Integer)+-- True+--+-- See also 'belowRange', 'aboveRanges'. belowRanges :: (Ord a) => [Range a] -> a -> Bool belowRanges rs a = all (`belowRange` a) rs @@ -346,6 +388,8 @@ -- @ -- mergeRanges . union [] -- @+--+-- See also 'joinRanges' for merging ranges that are contiguous for 'Enum' types. mergeRanges :: (Ord a) => [Range a] -> [Range a] mergeRanges = Alg.eval . Alg.union (Alg.const []) . Alg.const {-# INLINE mergeRanges #-}@@ -419,5 +463,7 @@ -- -- You can use this method to ensure that all ranges for whom the value implements 'Enum' can be -- compressed to their smallest representation.+--+-- See also 'mergeRanges' for the overlap-only merge that works on any 'Ord' type. joinRanges :: (Ord a, Enum a) => [Range a] -> [Range a] joinRanges = exportRangeMerge . joinRM . loadRanges
Data/Range/Algebra.hs view
@@ -2,36 +2,44 @@ {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}  -- | Internally the range library converts your ranges into an internal--- efficient representation of multiple ranges. When you do multiple unions and--- intersections in a row converting to and from that data structure becomes--- extra work that is not required. To amortize those costs away the @RangeExpr@--- algebra exists. You can specify a tree of operations in advance and then--- evaluate them all at once. This is not only useful for efficiency but for--- parsing too. Build up @RangeExpr@'s whenever you wish to perform multiple--- operations in a row, and evaluate it in one step to be as efficient as possible.+-- efficient representation. When you perform multiple unions and intersections+-- in a row, converting to and from that representation on every step is extra+-- work. The @RangeExpr@ algebra amortises this cost: build a tree of operations+-- first, then evaluate the whole tree in one pass. ----- __Note:__ This module is based on F-Algebras to do much of the heavy conceptual--- lifting. If you have never seen F-Algebras before then I highly recommend reading--- through <https://www.schoolofhaskell.com/user/bartosz/understanding-algebras this introductory content>+-- __When to use this module:__ Build a 'RangeExpr' when you are combining three+-- or more operations in a pipeline, or when you want to evaluate the same+-- expression against multiple targets (e.g. both @['Range' a]@ and @a -> 'Bool'@).+-- A single @union a b@ is no faster through the algebra than a direct call.+--+-- __Note:__ This module is based on F-Algebras. If you have never encountered+-- them before, see+-- <https://www.schoolofhaskell.com/user/bartosz/understanding-algebras this introduction> -- from the School of Haskell. -- -- == Examples ----- A simple example of using this module would look like this:+-- Evaluate to a concrete list of ranges: -- -- >>> import qualified Data.Range.Algebra as A--- (A.eval . A.invert $ A.const [SingletonRange 5]) :: [Range Integer]--- [LowerBoundRange 6,UpperBoundRange 4]--- (0.01 secs, 597,656 bytes)+-- >>> import Data.Range+-- >>> A.eval . A.invert $ A.const [SingletonRange (5 :: Integer)]+-- [ube 4,lbi 6] ----- You can also use this module to evaluate range predicates.+-- Evaluate the same expression as a predicate (no intermediate list is built): --+-- >>> let expr = A.union (A.const [1 +=+ 10]) (A.const [20 +=+ 30]) :: A.RangeExpr [Range Integer]+-- >>> (A.eval expr :: Integer -> Bool) 25+-- True+-- >>> (A.eval expr :: Integer -> Bool) 15+-- False -- module Data.Range.Algebra-  ( RangeExpr-    -- ** Operations+  ( -- * Expression trees+    RangeExpr+    -- ** Building expressions   , const, invert, union, intersection, difference-    -- ** Evaluation+    -- * Evaluation   , Algebra, RangeAlgebra(..)   ) where @@ -44,40 +52,52 @@  import Control.Monad.Free --- | Lifts the input value as a constant into an expression.+-- | Lifts a value as a constant leaf into an expression tree.+--+-- Note: this function shadows 'Prelude.const'. The "Data.Range.Algebra" module+-- uses @import Prelude hiding (const)@; callers that import both should qualify. const :: a -> RangeExpr a const = RangeExpr . Pure --- | Returns an expression that represents the inverse of the input expression.+-- | Wraps an expression in a set-complement (invert) node.+-- When evaluated, produces all values /not/ covered by the inner expression.+-- Note that @'invert' . 'invert' == 'id'@. invert :: RangeExpr a -> RangeExpr a invert = RangeExpr . Free . Invert . getFree --- | Returns an expression that represents the set union of the input expressions.+-- | Wraps two expressions in a set-union node.+-- When evaluated, produces all values covered by either expression. union :: RangeExpr a -> RangeExpr a -> RangeExpr a union a b = RangeExpr . Free $ Union (getFree a) (getFree b) --- | Returns an expression that represents the set intersection of the input expressions.+-- | Wraps two expressions in a set-intersection node.+-- When evaluated, produces only values covered by both expressions. intersection :: RangeExpr a -> RangeExpr a -> RangeExpr a intersection a b = RangeExpr . Free $ Intersection (getFree a) (getFree b) --- | Returns an expression that represents the set difference of the input expressions.+-- | Wraps two expressions in a set-difference node.+-- When evaluated, produces values in the first expression that are absent from the second. difference :: RangeExpr a -> RangeExpr a -> RangeExpr a difference a b = RangeExpr . Free $ Difference (getFree a) (getFree b) --- | Represents the fact that there exists an algebra for the given representation--- of a range, so that a range expression of the same type can be evaluated, yielding--- that representation.+-- | A type class for types that a 'RangeExpr' can be evaluated to.+-- Two instances are provided out of the box; additional targets can be added+-- by implementing this class. class RangeAlgebra a where-  -- | This function is used to convert your built expressions into ranges.+  -- | Collapses a 'RangeExpr' tree into its target representation by+  -- evaluating every node bottom-up. Two evaluation targets are supported:+  --+  -- * @['Data.Range.Range' a]@ — a merged, canonical list of non-overlapping ranges.+  -- * @a -> 'Bool'@ — a membership predicate; no intermediate list is constructed.   eval :: Algebra RangeExpr a --- | Multiple ranges represented by a list of disjoint ranges.--- Note that input ranges are allowed to overlap, but the output--- ranges are guaranteed to be disjoint.+-- | Evaluates to a merged, canonical list of non-overlapping ranges.+-- Input ranges are allowed to overlap; the output is guaranteed to be disjoint. instance (Ord a) => RangeAlgebra [Range a] where   eval = iter rangeAlgebra . getFree --- | Multiple ranges represented by a predicate function, indicating membership--- of a point in one of the ranges.+-- | Evaluates to a membership predicate @a -> 'Bool'@.+-- More efficient than the @['Range' a]@ instance when you only need to test+-- membership and do not need to inspect the ranges themselves. instance RangeAlgebra (a -> Bool) where   eval = iter predicateAlgebra . getFree
Data/Range/Algebra/Internal.hs view
@@ -40,12 +40,25 @@     showString " - " .     showPrec (p + 1) b +-- | An expression tree representing a sequence of set operations on ranges.+-- Construct trees with 'Data.Range.Algebra.const', 'Data.Range.Algebra.union',+-- 'Data.Range.Algebra.intersection', 'Data.Range.Algebra.difference', and+-- 'Data.Range.Algebra.invert', then collapse the tree with 'Data.Range.Algebra.eval'.+--+-- The type parameter @a@ is the range representation the tree will eventually+-- evaluate to (e.g. @['Data.Range.Range' Integer]@ or @Integer -> 'Bool'@).+--+-- @RangeExpr@ is a 'Functor', so you can map over the leaf values before evaluation. newtype RangeExpr a = RangeExpr { getFree :: Free RangeExprF a }   deriving (Show, Eq, Functor) --- | This is an F-Algebra. You don't need to know what this is in order to be able--- to use this module, but, if you are interested you can--- <https://www.schoolofhaskell.com/user/bartosz/understanding-algebras read more on School of Haskell>.+-- | The type of an evaluation function for a 'RangeExpr'. You will not normally+-- need to reference this alias directly; it exists to express the signature of+-- 'Data.Range.Algebra.eval'.+--+-- Concretely, @Algebra f a = f a -> a@, meaning: given a functor @f@ applied to+-- an already-evaluated @a@, produce the final @a@. The 'Control.Monad.Free.iter'+-- function from the @free@ package drives the bottom-up fold. type Algebra f a = f a -> a  rangeMergeAlgebra :: (Ord a) => Algebra RangeExprF (RangeMerge a)
Data/Range/Ord.hs view
@@ -15,6 +15,7 @@ -- == Example: Map keyed on ranges -- -- @+-- import Data.Range (Range, (+=+), lbi) -- import Data.Range.Ord (KeyRange(..)) -- import qualified Data.Map.Strict as Map --@@ -28,17 +29,26 @@ --   ] -- @ ----- == Example: sorting ranges by position+-- == Example: sorting ranges by position on the number line ----- @--- import Data.Range.Ord (SortedRange(..))--- import Data.List (sortOn)+-- >>> import Data.List (sortOn)+-- >>> sortOn SortedRange [lbi 10, 1 +=+ 5, ube 0 :: Range Integer]+-- [ube 0,1 +=+ 5,lbi 10] --+-- @+-- -- or equivalently: -- displayRanges :: Ord a => [Range a] -> [Range a] -- displayRanges = sortOn SortedRange -- @ module Data.Range.Ord-   ( KeyRange(..)+   ( -- * Structural ordering+     -- | Use 'KeyRange' when you need 'Range' values as 'Data.Map.Map' keys or+     -- in a 'Data.Set.Set'. The ordering is consistent but not semantically+     -- meaningful on the number line.+     KeyRange(..)+     -- * Positional ordering+     -- | Use 'SortedRange' when you want to sort ranges by where they sit on+     -- the number line (lower bound first, upper bound as tiebreaker).    , SortedRange(..)    ) where @@ -59,7 +69,13 @@ -- This ordering is not semantically meaningful on the number line — -- @SingletonRange 5@ and @SpanRange (Bound 5 Inclusive) (Bound 5 Inclusive)@ -- are considered distinct. It is only appropriate where any consistent total--- order will do.+-- order will do (deduplication, 'Data.Map.Map' keys).+--+-- Use 'unKeyRange' to unwrap the underlying 'Range'.+--+-- See also 'SortedRange' for ordering by position on the number line.+--+-- @since 0.3.2.0 newtype KeyRange a = KeyRange { unKeyRange :: Range a }    deriving (Eq, Show) @@ -124,8 +140,18 @@ -- -- The 'Eq' instance is consistent with 'Ord': two 'SortedRange' values are -- equal iff they have the same lower and upper bounds. This means--- @SortedRange (SingletonRange 5)@ and--- @SortedRange (5 +=+ 5)@ are considered equal.+-- @SortedRange (SingletonRange 5)@ and @SortedRange (5 +=+ 5)@ are considered+-- equal (they occupy the same point on the number line).+--+-- Use 'unSortedRange' to unwrap the underlying 'Range'. Typical usage:+--+-- >>> import Data.List (sortOn)+-- >>> sortOn SortedRange [lbi 10, 1 +=+ 5, ube 0 :: Range Integer]+-- [ube 0,1 +=+ 5,lbi 10]+--+-- See also 'KeyRange' for a structural ordering suitable for 'Data.Map.Map' keys.+--+-- @since 0.3.2.0 newtype SortedRange a = SortedRange { unSortedRange :: Range a }  instance Show a => Show (SortedRange a) where
Data/Range/Parser.hs view
@@ -1,26 +1,49 @@ {-# LANGUAGE FlexibleContexts #-} --- | This package provides a simple range parser.+-- | A simple parser for human-readable range strings, designed for CLI programs. ----- This range parser was designed to be a useful tool for CLI programs. For example, by--- default, this example depicts how the parser works:+-- By default, ranges are separated by commas and span endpoints by a hyphen: -- -- >>> parseRanges "-5,8-10,13-15,20-" :: Either ParseError [Range Integer]--- Right [UpperBoundRange 5,SpanRange 8 10,SpanRange 13 15,LowerBoundRange 20]--- (0.01 secs, 681,792 bytes)+-- Right [UpperBoundRange (Bound 5 Inclusive),SpanRange (Bound 8 Inclusive) (Bound 10 Inclusive),SpanRange (Bound 13 Inclusive) (Bound 15 Inclusive),LowerBoundRange (Bound 20 Inclusive)] ----- And the * character translates to an infinite range. This is very useful for accepting--- ranges as input in CLI programs, but not as useful for parsing .cabal or package.json files.+-- The @*@ wildcard produces an infinite range: ----- To handle more complex parsing cases it is recommended that you use the ranges library--- in conjunction with parsec or Alex/Happy and convert the versions that you find into--- ranges.+-- >>> parseRanges "*" :: Either ParseError [Range Integer]+-- Right [InfiniteRange]+--+-- Use 'customParseRanges' to change the separator characters:+--+-- >>> let args = defaultArgs { unionSeparator = ";", rangeSeparator = ".." }+-- >>> customParseRanges args "1..5;10" :: Either ParseError [Range Integer]+-- Right [SpanRange (Bound 1 Inclusive) (Bound 5 Inclusive),SingletonRange 10]+--+-- __Known limitations:__+--+-- * Only non-negative integer literals are recognised. The input @\"-5\"@ is parsed+--   as @UpperBoundRange 5@ (an upper-bounded range), not @SingletonRange (-5)@.+--   For negative values, use 'customParseRanges' with a different 'rangeSeparator',+--   or pre-process the input string.+--+-- * Unrecognised input is silently consumed as an empty list rather than producing+--   a parse error. For example, @parseRanges \"abc\"@ returns @Right []@. This is a+--   consequence of using 'Text.Parsec.sepBy' internally and is by design for+--   CLI use where partial input is common.+--+-- For more complex parsing (e.g. @.cabal@ or @package.json@ files), parse version+-- strings with Parsec or Alex\/Happy and convert the results into 'Range' values directly. module Data.Range.Parser-   ( parseRanges+   ( -- * Parsing+     parseRanges    , customParseRanges+     -- * Configuration    , RangeParserArgs(..)    , defaultArgs+     -- * Lower-level parser    , ranges+     -- * Re-exports+     -- | 'ParseError' is re-exported from "Text.Parsec" for convenience, so+     -- callers do not need to import Parsec directly just to match on parse failures.    , ParseError    ) where @@ -29,16 +52,20 @@  import Data.Range --- | These are the arguments that will be used when parsing a string as a range.+-- | Configuration for the range parser. All three fields are plain strings, so+-- multi-character separators (e.g. @\"..\"@) are supported. data RangeParserArgs = Args-   { unionSeparator :: String -- ^ A separator that represents a union.-   , rangeSeparator :: String -- ^ A separator that separates the two halves of a range.-   , wildcardSymbol :: String -- ^ A separator that implies an unbounded range.+   { unionSeparator :: String -- ^ Separates multiple ranges in a union. Default: @\",\"@.+   , rangeSeparator :: String -- ^ Separates the two endpoints of a span. Default: @\"-\"@.+   , wildcardSymbol :: String -- ^ Symbol for an infinite range. Default: @\"*\"@.    }    deriving(Show) --- | These are the default arguments that are used by the parser. Please feel free to use--- the default arguments for you own parser and modify it from the defaults at will.+-- | The default parser configuration: comma-separated ranges, hyphen-separated+-- endpoints, and @*@ as the wildcard. Modify individual fields with record syntax:+--+-- >>> defaultArgs { unionSeparator = ";", rangeSeparator = ".." }+-- Args {unionSeparator = ";", rangeSeparator = "..", wildcardSymbol = "*"} defaultArgs :: RangeParserArgs defaultArgs = Args    { unionSeparator = ","@@ -46,22 +73,33 @@    , wildcardSymbol = "*"    } --- | Given a string, this function will either return a parse error back to the user or the--- list of ranges that are represented by the parsed string. Very useful for CLI programs--- that need to load ranges from a single-line string.+-- | Parses a range string using the default separators (@,@ and @-@). Returns+-- either a 'ParseError' or the list of parsed ranges.+--+-- The 'Read' instance of @a@ is used to parse individual numeric literals, so+-- the type must have a well-behaved 'Read'. Exotic types with unusual 'Read'+-- instances may not parse correctly.+--+-- See the module documentation for known limitations around negative numbers+-- and unrecognised input. parseRanges :: (Read a) => String -> Either ParseError [Range a] parseRanges = parse (ranges defaultArgs) "(range parser)" --- | If you disagree with the default characters for separating ranges then this function can--- be used to customise them, up to a point.+-- | Like 'parseRanges' but with caller-supplied separator configuration.+-- Use this when the default @,@ and @-@ characters conflict with your input format.+--+-- >>> let args = defaultArgs { unionSeparator = ";", rangeSeparator = ".." }+-- >>> customParseRanges args "1..5;10" :: Either ParseError [Range Integer]+-- Right [SpanRange (Bound 1 Inclusive) (Bound 5 Inclusive),SingletonRange 10] customParseRanges :: Read a => RangeParserArgs -> String -> Either ParseError [Range a] customParseRanges args = parse (ranges args) "(range parser)"  string_ :: Stream s m Char => String -> ParsecT s u m () string_ x = string x >> return () --- | Given the parser arguments this returns a parsec parser that is capable of parsing a list of--- ranges.+-- | Returns a Parsec 'Parser' for a list of ranges using the given configuration.+-- Use this when embedding range parsing into a larger Parsec grammar; for+-- standalone parsing prefer 'parseRanges' or 'customParseRanges'. ranges :: (Read a) => RangeParserArgs -> Parser [Range a] ranges args = range `sepBy` (string $ unionSeparator args)    where
Data/Ranges.hs view
@@ -1,13 +1,32 @@ {-# LANGUAGE Safe #-} --- | This module provides a simpler interface than the 'Data.Range' module, allowing you to work with--- multiple ranges at the same time.+-- | This module provides a 'Newtype' wrapper around @['Data.Range.Range' a]@ that+-- integrates with standard Haskell type classes, making it easy to accumulate and+-- compose ranges using familiar idioms. ----- One of the main advantages of this module is that it implements 'Monoid' for 'Ranges' which lets you--- write code like:--- +-- The primary advantage over "Data.Range" is that 'Ranges' implements 'Semigroup'+-- and 'Monoid', where @('<>')@ means /union-and-merge/. This composes naturally with+-- standard Haskell functions:+--+-- >>> import Data.Foldable (fold)+-- >>> fold [1 +=+ 5, 3 +=+ 8, lbi 20 :: Ranges Integer]+-- Ranges [1 +=+ 8,lbi 20]+--+-- >>> mconcat [1 +=+ 5, 10 +=+ 15, 12 +=+ 20 :: Ranges Integer]+-- Ranges [1 +=+ 5,10 +=+ 20]+--+-- __When to use this module vs "Data.Range":__+--+-- * Use "Data.Range" when working with @['Range' a]@ directly or calling individual+--   set operations like 'union' and 'intersection'.+-- * Use this module when you want 'Monoid' / 'Semigroup' semantics, need 'Functor'+--   to map over all range boundaries, or are threading ranges through code that+--   expects a 'Monoid' (e.g. 'mconcat', 'fold', writer-style accumulation). module Data.Ranges (+  -- * The Ranges type+  Ranges(..),   -- * Range creation+  -- $creation   (+=+),   (+=*),   (*=+),@@ -28,83 +47,168 @@   invert,   -- * Enumerable methods   fromRanges,-  joinRanges,-  -- * Data types-  Ranges(..)+  joinRanges ) where  import Data.Semigroup import qualified Data.Range as R --- TODO Can we make this use a Range Algebra internally ?+-- $creation+-- Each operator constructs a single-element 'Ranges'. Because 'Ranges' is a+-- 'Semigroup', you can combine them directly with '<>':+--+-- >>> (1 +=+ 5 :: Ranges Integer) <> (3 +=+ 8)+-- Ranges [1 +=+ 8]+--+-- The operators mirror those in "Data.Range" but return 'Ranges' instead of+-- @'R.Range'@, so they compose naturally without wrapping and unwrapping.++-- | A set of ranges represented as a merged, canonical list of+-- non-overlapping 'R.Range' values.+--+-- The 'Semigroup' instance merges ranges on @('<>')@:+--+-- >>> (1 +=+ 5 :: Ranges Integer) <> (3 +=+ 8)+-- Ranges [1 +=+ 8]+--+-- 'mempty' is the empty set (no ranges). 'mconcat' merges an entire list at once,+-- which is more efficient than repeated @('<>')@:+--+-- >>> mconcat [1 +=+ 5, 10 +=+ 15, 12 +=+ 20 :: Ranges Integer]+-- Ranges [1 +=+ 5,10 +=+ 20]+--+-- The 'Functor' instance maps a function over every boundary value in every range:+--+-- >>> fmap (*2) (1 +=+ 5 :: Ranges Integer)+-- Ranges [2 +=+ 10] newtype Ranges a = Ranges { unRanges :: [R.Range a] }  instance Show a => Show (Ranges a) where    showsPrec i (Ranges xs) = ((++) "Ranges ") . showsPrec i xs +-- | @('<>')@ computes the set union of two 'Ranges' and merges the result into+-- canonical (non-overlapping) form. Associative, with 'mempty' as the identity. instance Ord a => Semigroup (Ranges a) where    (<>) (Ranges a) (Ranges b) = Ranges . R.mergeRanges $ a ++ b +-- | 'mempty' is the empty set. 'mconcat' is more efficient than folding '<>'+-- because it merges all ranges in a single pass. instance Ord a => Monoid (Ranges a) where    mempty = Ranges []    mappend (Ranges a) (Ranges b) = Ranges . R.mergeRanges $ a ++ b    mconcat = Ranges . R.mergeRanges . concat . fmap unRanges +-- | Maps a function over every boundary value in every range.+-- Note that mapping a non-monotonic function can produce ill-formed ranges+-- (e.g. a span whose lower bound ends up greater than its upper bound).+-- Use with care on ordered types. instance Functor Ranges where    fmap f (Ranges xs) = Ranges . fmap (fmap f) $ xs +-- | Mathematically equivalent to @[x, y]@. See 'R.+=+' for details. (+=+) :: a -> a -> Ranges a (+=+) a b = Ranges . pure $ (R.+=+) a b +-- | Mathematically equivalent to @[x, y)@. See 'R.+=*' for details. (+=*) :: a -> a -> Ranges a (+=*) a b = Ranges . pure $ (R.+=*) a b +-- | Mathematically equivalent to @(x, y]@. See 'R.*=+' for details. (*=+) :: a -> a -> Ranges a (*=+) a b = Ranges . pure $ (R.*=+) a b +-- | Mathematically equivalent to @(x, y)@. See 'R.*=*' for details. (*=*) :: a -> a -> Ranges a (*=*) a b = Ranges . pure $ (R.*=*) a b +-- | Mathematically equivalent to @[x, ∞)@. See 'R.lbi' for details. lbi :: a -> Ranges a lbi = Ranges . pure . R.lbi +-- | Mathematically equivalent to @(x, ∞)@. See 'R.lbe' for details. lbe :: a -> Ranges a lbe = Ranges . pure . R.lbe +-- | Mathematically equivalent to @(−∞, x]@. See 'R.ubi' for details. ubi :: a -> Ranges a ubi = Ranges . pure . R.ubi +-- | Mathematically equivalent to @(−∞, x)@. See 'R.ube' for details. ube :: a -> Ranges a ube = Ranges . pure . R.ube +-- | The infinite range, covering all values. See 'R.inf' for details. inf :: Ranges a inf = Ranges [R.inf] +-- | Returns 'True' if the value falls within any of the given ranges.+--+-- >>> inRanges (1 +=+ 10 <> 20 +=+ 30 :: Ranges Integer) 5+-- True+-- >>> inRanges (1 +=+ 10 <> 20 +=+ 30 :: Ranges Integer) 15+-- False inRanges :: (Ord a) => Ranges a -> a -> Bool inRanges (Ranges xs) = R.inRanges xs --- | Checks if the value provided is above all of the ranges provided.+-- | Returns 'True' if the value is strictly above (greater than the upper+-- bound of) all of the given ranges.+--+-- >>> aboveRanges (1 +=+ 5 <> 10 +=+ 15 :: Ranges Integer) 20+-- True+-- >>> aboveRanges (1 +=+ 5 <> lbi 10 :: Ranges Integer) 20+-- False aboveRanges :: (Ord a) => Ranges a -> a -> Bool aboveRanges (Ranges xs) a = R.aboveRanges xs a --- | Checks if the value provided is below all of the ranges provided.+-- | Returns 'True' if the value is strictly below (less than the lower+-- bound of) all of the given ranges.+--+-- >>> belowRanges (5 +=+ 10 <> 20 +=+ 30 :: Ranges Integer) 1+-- True+-- >>> belowRanges (ubi 10 <> 20 +=+ 30 :: Ranges Integer) 1+-- False belowRanges :: (Ord a) => Ranges a -> a -> Bool belowRanges (Ranges rs) a = R.belowRanges rs a +-- | Set union of two 'Ranges'. The output is in merged canonical form.+-- Equivalent to @('<>')@. union :: (Ord a) => Ranges a -> Ranges a -> Ranges a union (Ranges a) (Ranges b) = Ranges $ R.union a b +-- | Set intersection of two 'Ranges'. Returns only values present in both.+--+-- >>> intersection (1 +=+ 10) (5 +=+ 15 :: Ranges Integer)+-- Ranges [5 +=+ 10] intersection :: (Ord a) => Ranges a -> Ranges a -> Ranges a intersection (Ranges a) (Ranges b) = Ranges $ R.intersection a b +-- | Set difference: values in the first 'Ranges' that are not in the second.+--+-- >>> difference (1 +=+ 10) (5 +=+ 15 :: Ranges Integer)+-- Ranges [1 +=* 5] difference :: (Ord a) => Ranges a -> Ranges a -> Ranges a difference (Ranges a) (Ranges b) = Ranges $ R.difference a b +-- | Returns the complement of the given 'Ranges': all values /not/ covered.+-- Note that @'invert' . 'invert' == 'id'@. invert :: (Ord a) => Ranges a -> Ranges a invert = Ranges . R.invert . unRanges +-- | Instantiates all values covered by the ranges as a list.+-- __Warning:__ This is a convenience function and is not efficient. Prefer+-- membership checks with 'inRanges' where possible. Combine with 'take' to+-- avoid evaluating infinite ranges.+--+-- >>> take 6 . fromRanges $ (1 +=+ 3 :: Ranges Integer) <> (10 +=+ 12)+-- [1,10,2,11,3,12] fromRanges :: (Ord a, Enum a) => Ranges a -> [a] fromRanges = R.fromRanges . unRanges +-- | Joins adjacent ranges that are contiguous for 'Enum' types. For example,+-- @[1 +=+ 5, 6 +=+ 10]@ can be collapsed to @[1 +=+ 10]@ for 'Integer'+-- because there is no integer between 5 and 6.+--+-- >>> joinRanges (mconcat [1 +=+ 5, 6 +=+ 10] :: Ranges Integer)+-- Ranges [1 +=+ 10] joinRanges :: (Ord a, Enum a) => Ranges a -> Ranges a joinRanges = Ranges . R.joinRanges . unRanges
+ DocTest.hs view
@@ -0,0 +1,13 @@+module Main (main) where++import Test.DocTest++main :: IO ()+main = doctest+   [ "-XSafe"+   , "Data/Range.hs"+   , "Data/Ranges.hs"+   , "Data/Range/Ord.hs"+   , "Data/Range/Parser.hs"+   , "Data/Range/Algebra.hs"+   ]
range.cabal view
@@ -10,7 +10,7 @@ -- PVP summary:      +-+------- breaking API changes --                   | | +----- non-breaking API additions --                   | | | +--- code changes with no API change-version:             0.3.2.0+version:             0.3.2.1  -- A short (one-line) description of the package. synopsis:            An efficient and versatile range library.@@ -108,6 +108,15 @@                   , range    default-language: Haskell2010    ghc-options: -rtsopts -Wall -fno-enable-rewrite-rules++test-suite doctest-range+  type:             exitcode-stdio-1.0+  main-is:          DocTest.hs+  build-depends:    base >= 4.7 && < 5+                  , doctest >= 0.20 && < 1+                  , range+  default-language: Haskell2010+  ghc-options:      -Wall  benchmark bench-range   type:             exitcode-stdio-1.0