range 0.1.2.0 → 0.2.0.0
raw patch · 5 files changed
+64/−16 lines, 5 filesdep ~basedep ~free
Dependency ranges changed: base, free
Files
- Data/Range/Algebra.hs +21/−0
- Data/Range/Algebra/Internal.hs +30/−2
- Data/Range/Algebra/Predicate.hs +7/−4
- Data/Range/RangeTree.hs +1/−8
- range.cabal +5/−2
Data/Range/Algebra.hs view
@@ -1,6 +1,14 @@ {-# LANGUAGE Safe #-} {-# 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. module Data.Range.Algebra ( RangeExpr -- ** Operations@@ -18,26 +26,39 @@ import Control.Monad.Free +-- | Lifts the input value as a constant into an expression. const :: a -> RangeExpr a const = RangeExpr . Pure +-- | Returns an expression that represents the inverse of the input expression. invert :: RangeExpr a -> RangeExpr a invert = RangeExpr . Free . Invert . getFree +-- | Returns an expression that represents the set union of the input expressions. 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. 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. 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. class RangeAlgebra a where 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. instance (Ord a, Enum 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. instance RangeAlgebra (a -> Bool) where eval = iter predicateAlgebra . getFree
Data/Range/Algebra/Internal.hs view
@@ -1,3 +1,4 @@+{-# LANGUAGE CPP #-} {-# LANGUAGE Safe #-} {-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE FlexibleContexts #-}@@ -10,16 +11,43 @@ import Data.Range.RangeInternal import Control.Monad.Free+#if MIN_VERSION_base(4,9,0)+import Data.Functor.Classes+#endif data RangeExprF r = Invert r | Union r r | Intersection r r | Difference r r- deriving (Show, Eq, Ord, Functor)+ deriving (Show, Eq, Functor) +#if MIN_VERSION_base(4,9,0)+instance Eq1 RangeExprF where+ liftEq eq (Invert a) (Invert b) = eq a b+ liftEq eq (Union a c) (Union b d) = eq a b && eq c d+ liftEq eq (Intersection a c) (Intersection b d) = eq a b && eq c d+ liftEq eq (Difference a c) (Difference b d) = eq a b && eq c d+ liftEq _ _ _ = False++instance Show1 RangeExprF where+ liftShowsPrec showPrec showList p (Invert x) = showString "not " . showParen True (showPrec (p + 1) x)+ liftShowsPrec showPrec showList p (Union a b) =+ showPrec (p + 1) a .+ showString " \\/ " .+ showPrec (p + 1) b+ liftShowsPrec showPrec showList p (Intersection a b) =+ showPrec (p + 1) a .+ showString " /\\ " .+ showPrec (p + 1) b+ liftShowsPrec showPrec showList p (Difference a b) =+ showPrec (p + 1) a .+ showString " - " .+ showPrec (p + 1) b+#endif+ newtype RangeExpr a = RangeExpr { getFree :: Free RangeExprF a }- deriving (Show, Eq, Ord, Functor)+ deriving (Show, Eq, Functor) type Algebra f a = f a -> a
Data/Range/Algebra/Predicate.hs view
@@ -1,9 +1,12 @@ module Data.Range.Algebra.Predicate where +import Control.Applicative+ import Data.Range.Algebra.Internal predicateAlgebra :: Algebra RangeExprF (a -> Bool)-predicateAlgebra (Invert f) a = not (f a)-predicateAlgebra (Union f g) a = f a || g a-predicateAlgebra (Intersection f g) a = f a && g a-predicateAlgebra (Difference f g) a = f a && not (g a)+predicateAlgebra (Invert f) = liftA not f+predicateAlgebra (Union f g) = liftA2 (||) f g+predicateAlgebra (Intersection f g) = liftA2 (&&) f g+predicateAlgebra (Difference f g) = liftA2 (&&~) f g+ where (&&~) a b = a && not b
Data/Range/RangeTree.hs view
@@ -1,13 +1,6 @@ {-# LANGUAGE Safe #-} --- | Internally the range library converts your ranges into an internal representation of--- multiple ranges that I call a RangeMerge. 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 RangeTree structure 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. Use RangeTree's whenever you wish to perform--- multiple operations in a row and wish for it to be as efficient as possible.-module Data.Range.RangeTree+module Data.Range.RangeTree {-# DEPRECATED "Use \"Data.Range.Algebra\" instead" #-} ( evaluate , RangeTree(..) , RangeOperation(..)
range.cabal view
@@ -10,7 +10,7 @@ -- PVP summary: +-+------- breaking API changes -- | | +----- non-breaking API additions -- | | | +--- code changes with no API change-version: 0.1.2.0+version: 0.2.0.0 -- A short (one-line) description of the package. synopsis: This has a bunch of code for specifying and managing ranges in your code.@@ -84,6 +84,9 @@ , test-framework-quickcheck2 >= 0.2 && < 0.4 , test-framework >= 0.4 && < 0.9 , random >= 1.0- , free >= 4.12 , range+ if impl(ghc < 8)+ build-depends: free >= 4.12 && < 5+ else+ build-depends: free >= 4.12 ghc-options: -rtsopts -Wall -fno-enable-rewrite-rules