range-0.3.0.2: An efficient and versatile range library.

Safe HaskellSafe
LanguageHaskell98

Data.Range.Algebra

Contents

Description

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.

Synopsis

Documentation

data RangeExpr a Source #

Instances
Functor RangeExpr Source # 
Instance details

Defined in Data.Range.Algebra.Internal

Methods

fmap :: (a -> b) -> RangeExpr a -> RangeExpr b #

(<$) :: a -> RangeExpr b -> RangeExpr a #

Eq a => Eq (RangeExpr a) Source # 
Instance details

Defined in Data.Range.Algebra.Internal

Methods

(==) :: RangeExpr a -> RangeExpr a -> Bool #

(/=) :: RangeExpr a -> RangeExpr a -> Bool #

Show a => Show (RangeExpr a) Source # 
Instance details

Defined in Data.Range.Algebra.Internal

Operations

const :: a -> RangeExpr a Source #

Lifts the input value as a constant into an expression.

invert :: RangeExpr a -> RangeExpr a Source #

Returns an expression that represents the inverse of the input expression.

union :: RangeExpr a -> RangeExpr a -> RangeExpr a Source #

Returns an expression that represents the set union of the input expressions.

intersection :: RangeExpr a -> RangeExpr a -> RangeExpr a Source #

Returns an expression that represents the set intersection of the input expressions.

difference :: RangeExpr a -> RangeExpr a -> RangeExpr a Source #

Returns an expression that represents the set difference of the input expressions.

Evaluation

type Algebra f a = f a -> a Source #

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.

class RangeAlgebra a where Source #

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.

Methods

eval :: Algebra RangeExpr a Source #

This function is used to convert your built expressions into ranges.

Instances
Ord a => RangeAlgebra [Range a] Source #

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.

Instance details

Defined in Data.Range.Algebra

RangeAlgebra (a -> Bool) Source #

Multiple ranges represented by a predicate function, indicating membership of a point in one of the ranges.

Instance details

Defined in Data.Range.Algebra

Methods

eval :: Algebra RangeExpr (a -> Bool) Source #