Copyright	(c) Masahiro Sakai 2011-2014
License	BSD-style
Maintainer	masahiro.sakai@gmail.com
Stability	provisional
Portability	non-portable (ScopedTypeVariables, DeriveDataTypeable)
Safe Haskell	Safe
Language	Haskell2010

Data.IntegerInterval

Contents

Interval type
Construction
Query
Universal comparison operators
Existential comparison operators
Existential comparison operators that produce witnesses (experimental)
Combine
Map
Operations
Conversion
Intervals relation
Orphan instances

Description

Interval datatype and interval arithmetic over integers.

For the purpose of abstract interpretation, it might be convenient to use Lattice instance. See also lattices package (http://hackage.haskell.org/package/lattices).

Since: 1.2.0

Synopsis

data IntegerInterval
module Data.ExtendedReal
data Boundary
- = Open
- | Closed
interval :: (Extended Integer, Boundary) -> (Extended Integer, Boundary) -> IntegerInterval
(<=..<=) :: Extended Integer -> Extended Integer -> IntegerInterval
(<..<=) :: Extended Integer -> Extended Integer -> IntegerInterval
(<=..<) :: Extended Integer -> Extended Integer -> IntegerInterval
(<..<) :: Extended Integer -> Extended Integer -> IntegerInterval
whole :: IntegerInterval
empty :: IntegerInterval
singleton :: Integer -> IntegerInterval
null :: IntegerInterval -> Bool
isSingleton :: IntegerInterval -> Bool
member :: Integer -> IntegerInterval -> Bool
notMember :: Integer -> IntegerInterval -> Bool
isSubsetOf :: IntegerInterval -> IntegerInterval -> Bool
isProperSubsetOf :: IntegerInterval -> IntegerInterval -> Bool
isConnected :: IntegerInterval -> IntegerInterval -> Bool
lowerBound :: IntegerInterval -> Extended Integer
upperBound :: IntegerInterval -> Extended Integer
lowerBound' :: IntegerInterval -> (Extended Integer, Boundary)
upperBound' :: IntegerInterval -> (Extended Integer, Boundary)
width :: IntegerInterval -> Integer
memberCount :: IntegerInterval -> Maybe Integer
(<!) :: IntegerInterval -> IntegerInterval -> Bool
(<=!) :: IntegerInterval -> IntegerInterval -> Bool
(==!) :: IntegerInterval -> IntegerInterval -> Bool
(>=!) :: IntegerInterval -> IntegerInterval -> Bool
(>!) :: IntegerInterval -> IntegerInterval -> Bool
(/=!) :: IntegerInterval -> IntegerInterval -> Bool
(<?) :: IntegerInterval -> IntegerInterval -> Bool
(<=?) :: IntegerInterval -> IntegerInterval -> Bool
(==?) :: IntegerInterval -> IntegerInterval -> Bool
(>=?) :: IntegerInterval -> IntegerInterval -> Bool
(>?) :: IntegerInterval -> IntegerInterval -> Bool
(/=?) :: IntegerInterval -> IntegerInterval -> Bool
(<??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer)
(<=??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer)
(==??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer)
(>=??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer)
(>??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer)
(/=??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer)
intersection :: IntegerInterval -> IntegerInterval -> IntegerInterval
intersections :: [IntegerInterval] -> IntegerInterval
hull :: IntegerInterval -> IntegerInterval -> IntegerInterval
hulls :: [IntegerInterval] -> IntegerInterval
mapMonotonic :: (Integer -> Integer) -> IntegerInterval -> IntegerInterval
pickup :: IntegerInterval -> Maybe Integer
simplestIntegerWithin :: IntegerInterval -> Maybe Integer
toInterval :: Real r => IntegerInterval -> Interval r
fromInterval :: Interval Integer -> IntegerInterval
fromIntervalOver :: RealFrac r => Interval r -> IntegerInterval
fromIntervalUnder :: RealFrac r => Interval r -> IntegerInterval
relate :: IntegerInterval -> IntegerInterval -> Relation

Interval type

data IntegerInterval Source #

The intervals (i.e. connected and convex subsets) over integers (Z).

Instances

Instances details

Data IntegerInterval Source #
Instance details Defined in Data.IntegerInterval.Internal Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> IntegerInterval -> c IntegerInterval # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c IntegerInterval # toConstr :: IntegerInterval -> Constr # dataTypeOf :: IntegerInterval -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c IntegerInterval) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c IntegerInterval) # gmapT :: (forall b. Data b => b -> b) -> IntegerInterval -> IntegerInterval # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> IntegerInterval -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> IntegerInterval -> r # gmapQ :: (forall d. Data d => d -> u) -> IntegerInterval -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> IntegerInterval -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> IntegerInterval -> m IntegerInterval # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> IntegerInterval -> m IntegerInterval # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> IntegerInterval -> m IntegerInterval #
Num IntegerInterval Source #
Instance details Defined in Data.IntegerInterval Methods (+) :: IntegerInterval -> IntegerInterval -> IntegerInterval # (-) :: IntegerInterval -> IntegerInterval -> IntegerInterval # (*) :: IntegerInterval -> IntegerInterval -> IntegerInterval # negate :: IntegerInterval -> IntegerInterval # abs :: IntegerInterval -> IntegerInterval # signum :: IntegerInterval -> IntegerInterval # fromInteger :: Integer -> IntegerInterval #
Read IntegerInterval Source #
Instance details Defined in Data.IntegerInterval Methods readsPrec :: Int -> ReadS IntegerInterval # readList :: ReadS [IntegerInterval] # readPrec :: ReadPrec IntegerInterval # readListPrec :: ReadPrec [IntegerInterval] #
Show IntegerInterval Source #
Instance details Defined in Data.IntegerInterval Methods showsPrec :: Int -> IntegerInterval -> ShowS # show :: IntegerInterval -> String # showList :: [IntegerInterval] -> ShowS #
NFData IntegerInterval Source #
Instance details Defined in Data.IntegerInterval.Internal Methods rnf :: IntegerInterval -> () #
Eq IntegerInterval Source #
Instance details Defined in Data.IntegerInterval.Internal Methods (==) :: IntegerInterval -> IntegerInterval -> Bool # (/=) :: IntegerInterval -> IntegerInterval -> Bool #
Hashable IntegerInterval Source #
Instance details Defined in Data.IntegerInterval.Internal Methods hashWithSalt :: Int -> IntegerInterval -> Int # hash :: IntegerInterval -> Int #
BoundedJoinSemiLattice IntegerInterval Source #
Instance details Defined in Data.IntegerInterval Methods bottom :: IntegerInterval #
BoundedMeetSemiLattice IntegerInterval Source #
Instance details Defined in Data.IntegerInterval Methods top :: IntegerInterval #
Lattice IntegerInterval Source #
Instance details Defined in Data.IntegerInterval Methods (\/) :: IntegerInterval -> IntegerInterval -> IntegerInterval # (/\) :: IntegerInterval -> IntegerInterval -> IntegerInterval #

module Data.ExtendedReal

data Boundary Source #

Boundary of an interval may be open (excluding an endpoint) or closed (including an endpoint).

Since: 2.0.0

Constructors

Open
Closed

Instances

Instances details

Data Boundary Source #
Instance details Defined in Data.Interval.Internal Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Boundary -> c Boundary # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Boundary # toConstr :: Boundary -> Constr # dataTypeOf :: Boundary -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Boundary) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Boundary) # gmapT :: (forall b. Data b => b -> b) -> Boundary -> Boundary # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Boundary -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Boundary -> r # gmapQ :: (forall d. Data d => d -> u) -> Boundary -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Boundary -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Boundary -> m Boundary # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Boundary -> m Boundary # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Boundary -> m Boundary #
Bounded Boundary Source #
Instance details Defined in Data.Interval.Internal Methods minBound :: Boundary # maxBound :: Boundary #
Enum Boundary Source #
Instance details Defined in Data.Interval.Internal Methods succ :: Boundary -> Boundary # pred :: Boundary -> Boundary # toEnum :: Int -> Boundary # fromEnum :: Boundary -> Int # enumFrom :: Boundary -> [Boundary] # enumFromThen :: Boundary -> Boundary -> [Boundary] # enumFromTo :: Boundary -> Boundary -> [Boundary] # enumFromThenTo :: Boundary -> Boundary -> Boundary -> [Boundary] #
Generic Boundary Source #
Instance details Defined in Data.Interval.Internal Associated Types type Rep Boundary :: Type -> Type # Methods from :: Boundary -> Rep Boundary x # to :: Rep Boundary x -> Boundary #
Read Boundary Source #
Instance details Defined in Data.Interval.Internal Methods readsPrec :: Int -> ReadS Boundary # readList :: ReadS [Boundary] # readPrec :: ReadPrec Boundary # readListPrec :: ReadPrec [Boundary] #
Show Boundary Source #
Instance details Defined in Data.Interval.Internal Methods showsPrec :: Int -> Boundary -> ShowS # show :: Boundary -> String # showList :: [Boundary] -> ShowS #
NFData Boundary Source #
Instance details Defined in Data.Interval.Internal Methods rnf :: Boundary -> () #
Eq Boundary Source #
Instance details Defined in Data.Interval.Internal Methods (==) :: Boundary -> Boundary -> Bool # (/=) :: Boundary -> Boundary -> Bool #
Ord Boundary Source #
Instance details Defined in Data.Interval.Internal Methods compare :: Boundary -> Boundary -> Ordering # (<) :: Boundary -> Boundary -> Bool # (<=) :: Boundary -> Boundary -> Bool # (>) :: Boundary -> Boundary -> Bool # (>=) :: Boundary -> Boundary -> Bool # max :: Boundary -> Boundary -> Boundary # min :: Boundary -> Boundary -> Boundary #
Hashable Boundary Source #
Instance details Defined in Data.Interval.Internal Methods hashWithSalt :: Int -> Boundary -> Int # hash :: Boundary -> Int #
type Rep Boundary Source #
Instance details Defined in Data.Interval.Internal type Rep Boundary = D1 ('MetaData "Boundary" "Data.Interval.Internal" "data-interval-2.1.2-MIRiQQEkd820wHV9oduNz" 'False) (C1 ('MetaCons "Open" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Closed" 'PrefixI 'False) (U1 :: Type -> Type))

Construction

interval Source #

Arguments

:: (Extended Integer, Boundary)	lower bound and whether it is included
-> (Extended Integer, Boundary)	upper bound and whether it is included
-> IntegerInterval

smart constructor for IntegerInterval

(<=..<=) infix 5 Source #

Arguments

:: Extended Integer	lower bound `l`
-> Extended Integer	upper bound `u`
-> IntegerInterval

closed interval [l,u]

(<..<=) infix 5 Source #

Arguments

:: Extended Integer	lower bound `l`
-> Extended Integer	upper bound `u`
-> IntegerInterval

left-open right-closed interval (l,u]

(<=..<) infix 5 Source #

Arguments

:: Extended Integer	lower bound `l`
-> Extended Integer	upper bound `u`
-> IntegerInterval

left-closed right-open interval [l, u)

(<..<) infix 5 Source #

Arguments

:: Extended Integer	lower bound `l`
-> Extended Integer	upper bound `u`
-> IntegerInterval

open interval (l, u)

whole :: IntegerInterval Source #

whole real number line (-∞, ∞)

empty :: IntegerInterval Source #

empty (contradicting) interval

singleton :: Integer -> IntegerInterval Source #

singleton set [x,x]

Query

null :: IntegerInterval -> Bool Source #

Is the interval empty?

isSingleton :: IntegerInterval -> Bool Source #

Is the interval single point?

Since: 2.0.0

member :: Integer -> IntegerInterval -> Bool Source #

Is the element in the interval?

notMember :: Integer -> IntegerInterval -> Bool Source #

Is the element not in the interval?

isSubsetOf :: IntegerInterval -> IntegerInterval -> Bool Source #

Is this a subset? (i1 `isSubsetOf` i2) tells whether i1 is a subset of i2.

isProperSubsetOf :: IntegerInterval -> IntegerInterval -> Bool Source #

Is this a proper subset? (i.e. a subset but not equal).

isConnected :: IntegerInterval -> IntegerInterval -> Bool Source #

Does the union of two range form a set which is the intersection between the integers and a connected real interval?

lowerBound :: IntegerInterval -> Extended Integer Source #

Lower endpoint (i.e. greatest lower bound) of the interval.

lowerBound of the empty interval is PosInf.
lowerBound of a left unbounded interval is NegInf.
lowerBound of an interval may or may not be a member of the interval.

upperBound :: IntegerInterval -> Extended Integer Source #

Upper endpoint (i.e. least upper bound) of the interval.

upperBound of the empty interval is NegInf.
upperBound of a right unbounded interval is PosInf.
upperBound of an interval is a member of the interval.

lowerBound' :: IntegerInterval -> (Extended Integer, Boundary) Source #

lowerBound of the interval and whether it is included in the interval. The result is convenient to use as an argument for interval.

upperBound' :: IntegerInterval -> (Extended Integer, Boundary) Source #

upperBound of the interval and whether it is included in the interval. The result is convenient to use as an argument for interval.

width :: IntegerInterval -> Integer Source #

Width of a interval. Width of an unbounded interval is undefined.

memberCount :: IntegerInterval -> Maybe Integer Source #

How many integers lie within the (bounded) interval. Equal to Just (width + 1) for non-empty, bounded intervals. The memberCount of an unbounded interval is Nothing.

Universal comparison operators

(<!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

For all x in X, y in Y. x < y?

(<=!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

For all x in X, y in Y. x <= y?

(==!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

For all x in X, y in Y. x == y?

(>=!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

For all x in X, y in Y. x >= y?

(>!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

For all x in X, y in Y. x > y?

(/=!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

For all x in X, y in Y. x /= y?

Existential comparison operators

(<?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

Does there exist an x in X, y in Y such that x < y?

(<=?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

Does there exist an x in X, y in Y such that x <= y?

(==?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

Does there exist an x in X, y in Y such that x == y?

(>=?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

Does there exist an x in X, y in Y such that x >= y?

(>?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

Does there exist an x in X, y in Y such that x > y?

(/=?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 Source #

Does there exist an x in X, y in Y such that x /= y?

Existential comparison operators that produce witnesses (experimental)

(<??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 Source #

Does there exist an x in X, y in Y such that x < y?

(<=??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 Source #

Does there exist an x in X, y in Y such that x <= y?

(==??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 Source #

Does there exist an x in X, y in Y such that x == y?

(>=??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 Source #

Does there exist an x in X, y in Y such that x >= y?

(>??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 Source #

Does there exist an x in X, y in Y such that x > y?

(/=??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 Source #

Does there exist an x in X, y in Y such that x /= y?

Combine

intersection :: IntegerInterval -> IntegerInterval -> IntegerInterval Source #

intersection of two intervals

intersections :: [IntegerInterval] -> IntegerInterval Source #

intersection of a list of intervals.

hull :: IntegerInterval -> IntegerInterval -> IntegerInterval Source #

convex hull of two intervals

hulls :: [IntegerInterval] -> IntegerInterval Source #

convex hull of a list of intervals.

Map

mapMonotonic :: (Integer -> Integer) -> IntegerInterval -> IntegerInterval Source #

mapMonotonic f i is the image of i under f, where f must be a strict monotone function.

Operations

pickup :: IntegerInterval -> Maybe Integer Source #

pick up an element from the interval if the interval is not empty.

simplestIntegerWithin :: IntegerInterval -> Maybe Integer Source #

simplestIntegerWithin returns the simplest rational number within the interval.

An integer y is said to be simpler than another y' if

```
abs y <= abs y'
```

(see also approxRational and simplestRationalWithin)

Conversion

toInterval :: Real r => IntegerInterval -> Interval r Source #

Convert the interval to Interval data type.

fromInterval :: Interval Integer -> IntegerInterval Source #

Conversion from Interval data type.

fromIntervalOver :: RealFrac r => Interval r -> IntegerInterval Source #

Given a Interval I over R, compute the smallest IntegerInterval J such that I ⊆ J.

fromIntervalUnder :: RealFrac r => Interval r -> IntegerInterval Source #

Given a Interval I over R, compute the largest IntegerInterval J such that J ⊆ I.

Intervals relation

relate :: IntegerInterval -> IntegerInterval -> Relation Source #

Computes how two intervals are related according to the Relation classification

Orphan instances

Num IntegerInterval Source #
Instance details Methods (+) :: IntegerInterval -> IntegerInterval -> IntegerInterval # (-) :: IntegerInterval -> IntegerInterval -> IntegerInterval # (*) :: IntegerInterval -> IntegerInterval -> IntegerInterval # negate :: IntegerInterval -> IntegerInterval # abs :: IntegerInterval -> IntegerInterval # signum :: IntegerInterval -> IntegerInterval # fromInteger :: Integer -> IntegerInterval #
Read IntegerInterval Source #
Instance details Methods readsPrec :: Int -> ReadS IntegerInterval # readList :: ReadS [IntegerInterval] # readPrec :: ReadPrec IntegerInterval # readListPrec :: ReadPrec [IntegerInterval] #
Show IntegerInterval Source #
Instance details Methods showsPrec :: Int -> IntegerInterval -> ShowS # show :: IntegerInterval -> String # showList :: [IntegerInterval] -> ShowS #
BoundedJoinSemiLattice IntegerInterval Source #
Instance details Methods bottom :: IntegerInterval #
BoundedMeetSemiLattice IntegerInterval Source #
Instance details Methods top :: IntegerInterval #
Lattice IntegerInterval Source #
Instance details Methods (\/) :: IntegerInterval -> IntegerInterval -> IntegerInterval # (/\) :: IntegerInterval -> IntegerInterval -> IntegerInterval #