Data.Range.Algebra

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:

ghci> import qualified Data.Range.Algebra as A
ghci> (A.eval . A.invert $ A.const [SingletonRange 5]) :: [Range Integer]
[LowerBoundRange 6,UpperBoundRange 4]
(0.01 secs, 597,656 bytes)
ghci>

You can also use this module to evaluate range predicates.

Documentation

data RangeExpr a

Instances

Functor RangeExpr

Defined in Data.Range.Algebra.Internal

Methods

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

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

Eq a => Eq (RangeExpr a)

Defined in Data.Range.Algebra.Internal

Methods

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

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

Show a => Show (RangeExpr a)

Defined in Data.Range.Algebra.Internal

Methods

showsPrec :: Int -> RangeExpr a -> ShowS

show :: RangeExpr a -> String

showList :: [RangeExpr a] -> ShowS

Operations

const :: a -> RangeExpr a

Lifts the input value as a constant into an expression.

invert :: RangeExpr a -> RangeExpr a

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

union :: RangeExpr a -> RangeExpr a -> RangeExpr a

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

intersection :: RangeExpr a -> RangeExpr a -> RangeExpr a

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

difference :: RangeExpr a -> RangeExpr a -> RangeExpr a

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

Evaluation

type Algebra f a = f a -> 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.

class RangeAlgebra a where

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.

Minimal complete definition

eval

Methods

eval :: Algebra RangeExpr a

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

Instances

(Ord a, Enum a) => RangeAlgebra [Range 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.

Defined in Data.Range.Algebra

Methods

eval :: Algebra RangeExpr [Range a]

RangeAlgebra (a -> Bool)

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

Defined in Data.Range.Algebra

Methods

eval :: Algebra RangeExpr (a -> Bool)