Safe Haskell	Safe
Language	Haskell2010

Data.Range.Algebra

Contents

Expression trees
- Building expressions
Evaluation

Description

Internally the range library converts your ranges into an internal 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.

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 Ranges 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 this introduction from the School of Haskell.

Examples

Evaluate to a Ranges value (the typical use):

import qualified Data.Range.Algebra as A
import Data.Ranges

expr :: A.RangeExpr (Ranges Integer)
expr = A.invert (A.const (SingletonRange 5))

A.eval expr :: Ranges Integer
-- Ranges [ube 4,lbi 6]

Evaluate the same expression as a predicate (no intermediate structure built):

import qualified Data.Range.Algebra as A
import Data.Ranges

let expr = A.union (A.const (1 +=+ 10)) (A.const (20 +=+ 30)) :: A.RangeExpr (Ranges Integer)
A.eval (fmap inRanges expr) 25  -- True
A.eval (fmap inRanges expr) 15  -- False

Synopsis

data RangeExpr a
const :: a -> RangeExpr a
invert :: RangeExpr a -> RangeExpr a
union :: RangeExpr a -> RangeExpr a -> RangeExpr a
intersection :: RangeExpr a -> RangeExpr a -> RangeExpr a
difference :: RangeExpr a -> RangeExpr a -> RangeExpr a
type Algebra (f :: Type -> Type) a = f a -> a
class RangeAlgebra a where
- eval :: Algebra RangeExpr a

Expression trees

data RangeExpr a Source #

An expression tree representing a sequence of set operations on ranges. Construct trees with const, union, intersection, difference, and invert, then collapse the tree with eval.

The type parameter a is the range representation the tree will eventually evaluate to (e.g. [Range Integer] or Integer -> Bool).

RangeExpr is a Functor, so you can map over the leaf values before evaluation.

Instances

Instances details

Functor RangeExpr Source #
Instance details Defined in Data.Range.Algebra.Internal Methods fmap :: (a -> b) -> RangeExpr a -> RangeExpr b (<$) :: a -> RangeExpr b -> RangeExpr a
Show a => Show (RangeExpr a) Source #
Instance details Defined in Data.Range.Algebra.Internal Methods showsPrec :: Int -> RangeExpr a -> ShowS show :: RangeExpr a -> String showList :: [RangeExpr a] -> ShowS
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

Building expressions

const :: a -> RangeExpr a Source #

Lifts a value as a constant leaf into an expression tree.

Note: this function shadows const. The Data.Range.Algebra module uses import Prelude hiding (const); callers that import both should qualify.

invert :: RangeExpr a -> RangeExpr a Source #

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.

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

Wraps two expressions in a set-union node. When evaluated, produces all values covered by either expression.

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

Wraps two expressions in a set-intersection node. When evaluated, produces only values covered by both expressions.

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

Wraps two expressions in a set-difference node. When evaluated, produces values in the first expression that are absent from the second.

Evaluation

type Algebra (f :: Type -> Type) a = f a -> a Source #

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

Concretely, Algebra f a = f a -> a, meaning: given a functor f applied to an already-evaluated a, produce the final a. The iter function from the free package drives the bottom-up fold.

class RangeAlgebra a where Source #

A type class for types that a RangeExpr can be evaluated to. Three instances are provided out of the box; additional targets can be added by implementing this class.

Methods

eval :: Algebra RangeExpr a Source #

Collapses a RangeExpr tree into its target representation by evaluating every node bottom-up. Three evaluation targets are supported:

Ranges a — canonical, indexed set with pre-built membership predicate. The primary target for user code; instance defined in Data.Ranges.
[Range a] — a merged, canonical list. Used internally and useful when you need to inspect individual ranges.
a -> Bool — a membership predicate; no intermediate structure built.

Instances

Instances details

Ord a => RangeAlgebra (Ranges a) Source #	Evaluates a `RangeExpr` tree whose leaves are `Ranges` values, producing a canonicalised `Ranges` with a pre-built membership predicate. This is the primary evaluation target for user-facing algebra expressions. The implementation converts leaves to `[Range a]` internally, folds the tree in a single `RangeMerge` pass (the same efficient path as the `[Range a]` instance), then wraps the result with `mkRanges`.
Instance details Defined in Data.Ranges Methods eval :: Algebra RangeExpr (Ranges a) Source #
Ord a => RangeAlgebra [Range a] Source #	Evaluates to a merged, canonical list of non-overlapping ranges. Used internally by Data.Ranges and useful when you need to inspect individual `Range` values. Prefer the `Ranges` instance for general use.
Instance details Defined in Data.Range.Algebra Methods eval :: Algebra RangeExpr [Range a] Source #
RangeAlgebra (a -> Bool) Source #	Evaluates to a membership predicate `a -> Bool`. No intermediate structure is constructed. With `Ranges` leaves, use `eval (fmap inRanges expr)` to reach this instance.
Instance details Defined in Data.Range.Algebra Methods eval :: Algebra RangeExpr (a -> Bool) Source #