-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | An efficient and versatile range library.
--
-- The range library alows the use of performant and versatile ranges in
-- your code. It supports bounded and unbounded ranges, ranges in a
-- nested manner (like library versions), an efficient algebra of range
-- computation and even a simplified interface for ranges for the common
-- cases. This library is far more efficient than using the default
-- Data.List functions to approximate range behaviour. Performance is the
-- major value offering of this library. If this is your first time using
-- this library it is highly recommended that you start with
-- Data.Range; it contains the basics of this library that meet
-- most use cases.
@package range
@version 0.3.0.2
-- | 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.
--
-- 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 this introductory
-- content from the School of Haskell.
--
-- Examples
--
-- A simple example of using this module would look like this:
--
--
-- >>> 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)
--
--
-- You can also use this module to evaluate range predicates.
module Data.Range.Algebra
data RangeExpr a
-- | Lifts the input value as a constant into an expression.
const :: a -> RangeExpr a
-- | Returns an expression that represents the inverse of the input
-- expression.
invert :: RangeExpr a -> RangeExpr a
-- | Returns an expression that represents the set union of the input
-- expressions.
union :: RangeExpr a -> RangeExpr a -> RangeExpr a
-- | Returns an expression that represents the set intersection of the
-- input expressions.
intersection :: RangeExpr a -> RangeExpr a -> RangeExpr a
-- | Returns an expression that represents the set difference of the input
-- expressions.
difference :: RangeExpr a -> RangeExpr a -> RangeExpr a
-- | 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 read
-- more on School of Haskell.
type Algebra f a = f a -> a
-- | 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.
class RangeAlgebra a
-- | This function is used to convert your built expressions into ranges.
eval :: RangeAlgebra a => Algebra RangeExpr a
instance GHC.Classes.Ord a => Data.Range.Algebra.RangeAlgebra [Data.Range.Data.Range a]
instance Data.Range.Algebra.RangeAlgebra (a -> GHC.Types.Bool)
-- | This module provides a simple api to access range functionality. It
-- provides standard set operations on ranges, the ability to merge
-- ranges together and, importantly, the ability to check if a value is
-- within a range. The primary benifit of the Range library is
-- performance and versatility.
--
-- Note: It is intended that you will read the documentation in
-- this module from top to bottom.
--
-- Understanding custom range syntax
--
-- This library supports five different types of ranges:
--
--
-- - SpanRange: A range starting from a value and ending with
-- another value.
-- - SingletonRange: This range is really just a shorthand for a
-- range that starts and ends with the same value.
-- - LowerBoundRange: A range that starts at a value and extends
-- infinitely in the positive direction.
-- - UpperBoundRange: A range that starts at a value and extends
-- infinitely in the negative direction.
-- - InfiniteRange: A range that includes all values in your
-- range.
--
--
-- All of these ranges are bounded in an Inclusive or
-- Exclusive manner.
--
-- To run through a simple example of what this looks like, let's start
-- with mathematical notation and then move into our own notation.
--
-- The bound [1, 5) says "All of the numbers from one to five,
-- including one but excluding 5."
--
-- Using the data types directly, you could write this as:
--
--
-- SpanRange (Bound 1 Inclusive) (Bound 5 Exclusive)
--
--
-- This is overly verbose, as a result, this library contains operators
-- and functions for writing this much more succinctly. The above example
-- could be written as:
--
--
-- 1 +=* 5
--
--
-- There the + symbol is used to represent the inclusive side of
-- a range and the * symbol is used to represent the exclusive
-- side of a range.
--
-- The Show instance of the Range class will actually
-- output these simplified helper functions, for example:
--
--
-- >>> [SingletonRange 5, SpanRange (Bound 1 Inclusive) (Bound 5 Exclusive), InfiniteRange]
-- [SingletonRange 5,1 +=* 5,inf]
--
--
-- There are lbi, lbe, ubi and ube functions
-- to create lower bound inclusive, lower bound exclusive, upper bound
-- inclusive and upper bound exclusive ranges respectively.
--
-- SingletonRange x is equivalent to x +=+ x but is
-- nicer for presentational purposes in a Show.
--
-- Now that you know the basic syntax to declare ranges, the following
-- uses cases will be easier to understand.
--
-- Use case 1: Basic Integer Range
--
-- The standard use case for this library is efficiently discovering if
-- an integer is within a given range.
--
-- For example, if we had the range made up of the inclusive unions of
-- [5, 10] and [20, 30] and [25, Infinity)
-- then we could instantiate, and simplify, such a range like this:
--
--
-- >>> mergeRanges [(5 :: Integer) +=+ 10, 20 +=+ 30, lbi 25]
-- [5 +=+ 10,lbi 20]
--
--
-- You can then test if elements are within this range:
--
--
-- >>> let ranges = mergeRanges [(5 :: Integer) +=+ 10, 20 +=+ 30, lbi 25]
--
-- >>> inRanges ranges 7
-- True
--
-- >>> inRanges ranges 50
-- True
--
-- >>> inRanges ranges 15
-- False
--
--
-- The other convenience methods in this library will help you perform
-- more range operations.
--
-- Use case 2: Version ranges
--
-- All the Range library really needs to work, is the Ord type. If
-- you have a data type that can be ordered, than we can perform range
-- calculations on it. The Data.Version type is an excellent example of
-- this. For example, let's say that you want to say: "I accept a version
-- range of [1.1.0, 1.2.1] or [1.3, 1.4) or [1.4, 1.4.2)" then you can
-- write that as:
--
--
-- >>> :m + Data.Version
--
-- >>> let v x = Version x []
--
-- >>> let ranges = mergeRanges [v [1, 1, 0] +=+ v [1,2,1], v [1,3] +=* v [1,4], v [1,4] +=* v [1,4,2]]
--
-- >>> inRanges ranges (v [1,0])
-- False
--
-- >>> inRanges ranges (v [1,5])
-- False
--
-- >>> inRanges ranges (v [1,1,5])
-- True
--
-- >>> inRanges ranges (v [1,3,5])
-- True
--
--
-- As you can see, it is almost identical to the previous example, yet
-- you are now comparing if a version is within a version range! Not only
-- that, but so long as your type is orderable, the ranges can be merged
-- together cleanly.
--
-- With any luck, you can apply this library to your use case of choice.
-- Good luck!
module Data.Range
-- | Mathematically equivalent to [x, y].
--
-- x +=+ y is the short version of SpanRange (Bound x
-- Inclusive) (Bound y Inclusive)
(+=+) :: a -> a -> Range a
-- | Mathematically equivalent to [x, y).
--
-- x +=* y is the short version of SpanRange (Bound x
-- Inclusive) (Bound y Exclusive)
(+=*) :: a -> a -> Range a
-- | Mathematically equivalent to (x, y].
--
-- x *=+ y is the short version of SpanRange (Bound x
-- Exclusive) (Bound y Inclusive)
(*=+) :: a -> a -> Range a
-- | Mathematically equivalent to (x, y).
--
-- x *=* y is the short version of SpanRange (Bound x
-- Exclusive) (Bound y Exclusive)
(*=*) :: a -> a -> Range a
-- | Mathematically equivalent to [x, Infinity).
--
-- lbi x is the short version of LowerBoundRange (Bound x
-- Inclusive)
lbi :: a -> Range a
-- | Mathematically equivalent to (x, Infinity).
--
-- lbe x is the short version of LowerBoundRange (Bound x
-- Exclusive)
lbe :: a -> Range a
-- | Mathematically equivalent to (Infinity, x].
--
-- ubi x is the short version of UpperBoundRange (Bound x
-- Inclusive)
ubi :: a -> Range a
-- | Mathematically equivalent to (Infinity, x).
--
-- ube x is the short version of UpperBoundRange (Bound x
-- Exclusive)
ube :: a -> Range a
-- | Shorthand for the InfiniteRange
inf :: Range a
-- | 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.
--
-- 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:
--
--
-- >>> :set +s
--
-- >>> elem (10000000 :: Integer) [1..10000000]
-- True
-- (0.26 secs, 720,556,888 bytes)
--
-- >>> inRange (1 +=+ 10000000) (10000000 :: Integer)
-- True
-- (0.00 secs, 557,656 bytes)
--
-- >>>
--
--
-- As you can see, this function is significantly more performant, in
-- both speed and memory, than using the elem function.
inRange :: Ord a => Range a -> a -> Bool
-- | 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.
inRanges :: Ord a => [Range a] -> a -> Bool
-- | Checks if the value provided is above (or greater than) the biggest
-- value in the given range.
--
-- The LowerBoundRange and the InfiniteRange will always
-- cause this method to return False because you can't have a value
-- higher than them since they are both infinite in the positive
-- direction.
--
--
-- >>> aboveRange (SingletonRange 5) (6 :: Integer)
-- True
--
-- >>> aboveRange (1 +=+ 5) (6 :: Integer)
-- True
--
-- >>> aboveRange (1 +=+ 5) (0 :: Integer)
-- False
--
-- >>> aboveRange (lbi 0) (6 :: Integer)
-- False
--
-- >>> aboveRange (ubi 0) (6 :: Integer)
-- True
--
-- >>> aboveRange inf (6 :: Integer)
-- False
--
aboveRange :: Ord a => Range a -> a -> Bool
-- | Checks if the value provided is above all of the ranges provided.
aboveRanges :: Ord a => [Range a] -> a -> Bool
-- | Checks if the value provided is below (or less than) the smallest
-- value in the given range.
--
-- The UpperBoundRange and the InfiniteRange will always
-- cause this method to return False because you can't have a value lower
-- than them since they are both infinite in the negative direction.
--
--
-- >>> belowRange (SingletonRange 5) (4 :: Integer)
-- True
--
-- >>> belowRange (1 +=+ 5) (0 :: Integer)
-- True
--
-- >>> belowRange (1 +=+ 5) (6 :: Integer)
-- False
--
-- >>> belowRange (lbi 6) (0 :: Integer)
-- True
--
-- >>> belowRange (ubi 6) (0 :: Integer)
-- False
--
-- >>> belowRange inf (6 :: Integer)
-- False
--
belowRange :: Ord a => Range a -> a -> Bool
-- | Checks if the value provided is below all of the ranges provided.
belowRanges :: Ord a => [Range a] -> a -> Bool
-- | A check to see if two ranges overlap. The ranges overlap if at least
-- one value exists within both ranges. If they do overlap then true is
-- returned; false otherwise.
--
-- For example:
--
--
-- >>> rangesOverlap (1 +=+ 5) (3 +=+ 7)
-- True
--
-- >>> rangesOverlap (1 +=+ 5) (5 +=+ 7)
-- True
--
-- >>> rangesOverlap (1 +=* 5) (5 +=+ 7)
-- False
--
--
-- The last case of these three is the primary "gotcha" of this method.
-- With [1, 5) and [5, 7] there is no value that exists
-- within both ranges. Therefore, technically, the ranges do not overlap.
-- If you expected this to return True then it is likely that you would
-- prefer to use rangesAdjoin instead.
rangesOverlap :: Ord a => Range a -> Range a -> Bool
-- | A check to see if two ranges overlap or adjoin. The ranges adjoin if
-- no values exist between them. If they do overlap or adjoin then true
-- is returned; false otherwise.
--
-- For example:
--
--
-- >>> rangesAdjoin (1 +=+ 5) (3 +=+ 7)
-- True
--
-- >>> rangesAdjoin (1 +=+ 5) (5 +=+ 7)
-- True
--
-- >>> rangesAdjoin (1 +=* 5) (5 +=+ 7)
-- True
--
--
-- The last case of these three is the primary "gotcha" of this method.
-- With [1, 5) and [5, 7] there exist no values between
-- them. Therefore the ranges adjoin. If you expected this to return
-- False then it is likely that you would prefer to use
-- rangesOverlap instead.
rangesAdjoin :: Ord a => Range a -> Range a -> Bool
-- | An array of ranges may have overlaps; this function will collapse that
-- array into as few Ranges as possible. For example:
--
--
-- >>> mergeRanges [lbi 12, 1 +=+ 10, 5 +=+ (15 :: Integer)]
-- [lbi 1]
-- (0.01 secs, 588,968 bytes)
--
--
-- As you can see, the mergeRanges method collapsed multiple ranges into
-- a single range that still covers the same surface area.
--
-- This may be useful for a few use cases:
--
--
-- - You are hyper concerned about performance and want to have the
-- minimum number of ranges for comparison in the inRanges function.
-- - You wish to display ranges to a human and want to show the minimum
-- number of ranges to avoid having to make people perform those
-- calculations themselves.
--
--
-- Please note that the use of any of the operations on sets of ranges
-- like invert, union and intersection will have the same behaviour as
-- mergeRanges as a side effect. So, for example, this is redundant:
--
--
-- mergeRanges . union []
--
mergeRanges :: Ord a => [Range a] -> [Range a]
-- | Performs a set union between the two input ranges and returns the
-- resultant set of ranges.
--
-- For example:
--
--
-- >>> union [1 +=+ 10] [5 +=+ (15 :: Integer)]
-- [1 +=+ 15]
-- (0.00 secs, 587,152 bytes)
--
union :: Ord a => [Range a] -> [Range a] -> [Range a]
-- | Performs a set intersection between the two input ranges and returns
-- the resultant set of ranges.
--
-- For example:
--
--
-- >>> intersection [1 +=* 10] [5 +=+ (15 :: Integer)]
-- [5 +=* 10]
-- (0.00 secs, 584,616 bytes)
--
intersection :: Ord a => [Range a] -> [Range a] -> [Range a]
-- | Performs a set difference between the two input ranges and returns the
-- resultant set of ranges.
--
-- For example:
--
--
-- >>> difference [1 +=+ 10] [5 +=+ (15 :: Integer)]
-- [1 +=* 5]
-- (0.00 secs, 590,424 bytes)
--
difference :: Ord a => [Range a] -> [Range a] -> [Range a]
-- | An inversion function, given a set of ranges it returns the inverse
-- set of ranges.
--
-- For example:
--
--
-- >>> invert [1 +=* 10, 15 *=+ (20 :: Integer)]
-- [ube 1,10 +=+ 15,lbe 20]
-- (0.00 secs, 623,456 bytes)
--
invert :: Ord a => [Range a] -> [Range a]
-- | Instantiate all of the values in a range.
--
-- Warning: This method is meant as a convenience method, it is
-- not efficient.
--
-- A set of ranges represents a collection of real values without
-- actually instantiating those values. Not instantiating ranges, allows
-- the range library to support infinite ranges and be super performant.
--
-- However, sometimes you actually want to get the values that your range
-- represents, or even get a sample set of the values. This function
-- generates as many of the values that belong to your range as you like.
--
-- Because ranges can be infinite, it is highly recommended to combine
-- this method with something like "Data.List.take" to avoid an infinite
-- recursion.
--
-- This method will attempt to take a sample from all of the ranges that
-- you have provided, however it is not guaranteed that you will get an
-- even sampling. All that is guaranteed is that you will only get back
-- values that are within one or more of the ranges you provide.
--
-- Examples
--
-- A simple span:
--
--
-- >>> take 5 . fromRanges $ [1 +=+ 10 :: Range Integer, 20 +=+ 30]
-- [1,20,2,21,3]
-- (0.01 secs, 566,016 bytes)
--
--
-- An infinite range:
--
--
-- >>> take 5 . fromRanges $ [inf :: Range Integer]
-- [0,1,-1,2,-2]
-- (0.00 secs, 566,752 bytes)
--
fromRanges :: (Ord a, Enum a) => [Range a] -> [a]
-- | Joins together ranges that we only know can be joined because of the
-- Enum class.
--
-- To make the purpose of this method easier to understand, let's run
-- throuh a simple example:
--
--
-- >>> mergeRanges [1 +=+ 5, 6 +=+ 10] :: [Range Integer]
-- [1 +=+ 5,6 +=+ 10]
--
--
-- In this example, you know that the values are all of the type
-- Integer. Because of this, you know that there are no values
-- between 5 and 6. You may expect that the mergeRanges function
-- should "just know" that it can merge these together; but it can't
-- because it does not have the required constraints. This becomes more
-- obvious if you modify the example to use Double instead:
--
--
-- >>> mergeRanges [1.5 +=+ 5.5, 6.5 +=+ 10.5] :: [Range Double]
-- [1.5 +=+ 5.5,6.5 +=+ 10.5]
--
--
-- Now we can see that there are an infinite number of values between 5.5
-- and 6.5 and thus no such join between the two ranges could occur.
--
-- This function, joinRanges, provides the missing piece that you would
-- expect:
--
--
-- >>> joinRanges $ mergeRanges [1 +=+ 5, 6 +=+ 10] :: [Range Integer]
-- [1 +=+ 10]
--
--
-- You can use this method to ensure that all ranges for whom the value
-- implements Enum can be compressed to their smallest
-- representation.
joinRanges :: (Ord a, Enum a) => [Range a] -> [Range a]
-- | Represents a bound at a particular value with a BoundType.
-- There is no implicit understanding if this is a lower or upper bound,
-- it could be either.
data Bound a
Bound :: a -> BoundType -> Bound a
-- | The value at the edge of this bound.
[boundValue] :: Bound a -> a
-- | The type of bound. Should be Inclusive or Exclusive.
[boundType] :: Bound a -> BoundType
-- | Represents a type of boundary.
data BoundType
-- | The value at the boundary should be included in the bound.
Inclusive :: BoundType
-- | The value at the boundary should be excluded in the bound.
Exclusive :: BoundType
-- | The Range Data structure; it is capable of representing any type of
-- range. This is the primary data structure in this library. Everything
-- should be possible to convert back into this datatype. All ranges in
-- this structure are inclusively bound.
data Range a
-- | Represents a single element as a range. SingletonRange a is
-- equivalent to SpanRange (Bound a Inclusive) (Bound a
-- Inclusive).
SingletonRange :: a -> Range a
-- | Represents a bounded span of elements. The first argument is expected
-- to be less than or equal to the second argument.
SpanRange :: Bound a -> Bound a -> Range a
-- | Represents a range with a finite lower bound and an infinite upper
-- bound.
LowerBoundRange :: Bound a -> Range a
-- | Represents a range with an infinite lower bound and a finite upper
-- bound.
UpperBoundRange :: Bound a -> Range a
-- | Represents an infinite range over all values.
InfiniteRange :: Range a
-- | This package provides a simple range parser.
--
-- This range parser was designed to be a useful tool for CLI programs.
-- For example, by default, this example depicts how the parser works:
--
--
-- >>> 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)
--
--
-- 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.
--
-- 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.
module Data.Range.Parser
-- | 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.
parseRanges :: Read a => String -> Either ParseError [Range a]
-- | If you disagree with the default characters for separating ranges then
-- this function can be used to customise them, up to a point.
customParseRanges :: Read a => RangeParserArgs -> String -> Either ParseError [Range a]
-- | These are the arguments that will be used when parsing a string as a
-- range.
data RangeParserArgs
Args :: String -> String -> String -> RangeParserArgs
-- | A separator that represents a union.
[unionSeparator] :: RangeParserArgs -> String
-- | A separator that separates the two halves of a range.
[rangeSeparator] :: RangeParserArgs -> String
-- | A separator that implies an unbounded range.
[wildcardSymbol] :: RangeParserArgs -> String
-- | 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.
defaultArgs :: RangeParserArgs
-- | Given the parser arguments this returns a parsec parser that is
-- capable of parsing a list of ranges.
ranges :: Read a => RangeParserArgs -> Parser [Range a]
-- | The abstract data type ParseError represents parse errors. It
-- provides the source position (SourcePos) of the error and a
-- list of error messages (Message). A ParseError can be
-- returned by the function parse. ParseError is an
-- instance of the Show and Eq classes.
data ParseError
instance GHC.Show.Show Data.Range.Parser.RangeParserArgs
-- | This module provides a simpler interface than the Range module,
-- allowing you to work with multiple ranges at the same time.
--
-- One of the main advantages of this module is that it implements
-- Monoid for Ranges which lets you write code like:
module Data.Ranges
(+=+) :: a -> a -> Ranges a
(+=*) :: a -> a -> Ranges a
(*=+) :: a -> a -> Ranges a
(*=*) :: a -> a -> Ranges a
lbi :: a -> Ranges a
lbe :: a -> Ranges a
ubi :: a -> Ranges a
ube :: a -> Ranges a
inf :: Ranges a
inRanges :: Ord a => Ranges a -> a -> Bool
-- | Checks if the value provided is above all of the ranges provided.
aboveRanges :: Ord a => Ranges a -> a -> Bool
-- | Checks if the value provided is below all of the ranges provided.
belowRanges :: Ord a => Ranges a -> a -> Bool
union :: Ord a => Ranges a -> Ranges a -> Ranges a
intersection :: Ord a => Ranges a -> Ranges a -> Ranges a
difference :: Ord a => Ranges a -> Ranges a -> Ranges a
invert :: Ord a => Ranges a -> Ranges a
fromRanges :: (Ord a, Enum a) => Ranges a -> [a]
joinRanges :: (Ord a, Enum a) => Ranges a -> Ranges a
newtype Ranges a
Ranges :: [Range a] -> Ranges a
[unRanges] :: Ranges a -> [Range a]
instance GHC.Show.Show a => GHC.Show.Show (Data.Ranges.Ranges a)
instance GHC.Classes.Ord a => GHC.Base.Semigroup (Data.Ranges.Ranges a)
instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.Ranges.Ranges a)
instance GHC.Base.Functor Data.Ranges.Ranges