Data.IntegerInterval

Interval datatype and interval arithmetic over integers.

Since 1.2.0

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

Interval type

data IntegerInterval

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

Instances

Eq IntegerInterval

Methods

(==) :: IntegerInterval -> IntegerInterval -> Bool

(/=) :: IntegerInterval -> IntegerInterval -> Bool

Data IntegerInterval

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 :: (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

Methods

(+) :: IntegerInterval -> IntegerInterval -> IntegerInterval

(-) :: IntegerInterval -> IntegerInterval -> IntegerInterval

(*) :: IntegerInterval -> IntegerInterval -> IntegerInterval

negate :: IntegerInterval -> IntegerInterval

abs :: IntegerInterval -> IntegerInterval

signum :: IntegerInterval -> IntegerInterval

fromInteger :: Integer -> IntegerInterval

Read IntegerInterval

Methods

readsPrec :: Int -> ReadS IntegerInterval

readList :: ReadS [IntegerInterval]

readPrec :: ReadPrec IntegerInterval

readListPrec :: ReadPrec [IntegerInterval]

Show IntegerInterval

Methods

showsPrec :: Int -> IntegerInterval -> ShowS

show :: IntegerInterval -> String

showList :: [IntegerInterval] -> ShowS

NFData IntegerInterval

Methods

rnf :: IntegerInterval -> ()

Hashable IntegerInterval

Methods

hashWithSalt :: Int -> IntegerInterval -> Int

hash :: IntegerInterval -> Int

JoinSemiLattice IntegerInterval

Methods

(\/) :: IntegerInterval -> IntegerInterval -> IntegerInterval

join :: IntegerInterval -> IntegerInterval -> IntegerInterval

MeetSemiLattice IntegerInterval

Methods

(/\) :: IntegerInterval -> IntegerInterval -> IntegerInterval

meet :: IntegerInterval -> IntegerInterval -> IntegerInterval

Lattice IntegerInterval

BoundedJoinSemiLattice IntegerInterval

Methods

bottom :: IntegerInterval

BoundedMeetSemiLattice IntegerInterval

Methods

top :: IntegerInterval

BoundedLattice IntegerInterval

module Data.ExtendedReal

Construction

interval

Arguments

:: (Extended Integer, Bool)

lower bound and whether it is included

-> (Extended Integer, Bool)

upper bound and whether it is included

-> IntegerInterval

smart constructor for IntegerInterval

(<=..<=) infix 5

Arguments

:: Extended Integer

lower bound l

-> Extended Integer

upper bound u

-> IntegerInterval

closed interval [l,u]

(<..<=) infix 5

Arguments

:: Extended Integer

lower bound l

-> Extended Integer

upper bound u

-> IntegerInterval

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

(<=..<) infix 5

Arguments

:: Extended Integer

lower bound l

-> Extended Integer

upper bound u

-> IntegerInterval

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

(<..<) infix 5

Arguments

:: Extended Integer

lower bound l

-> Extended Integer

upper bound u

-> IntegerInterval

open interval (l, u)

whole :: IntegerInterval

whole real number line (-∞, ∞)

empty :: IntegerInterval

empty (contradicting) interval

singleton :: Integer -> IntegerInterval

singleton set \[x,x\]

Query

null :: IntegerInterval -> Bool

Is the interval empty?

member :: Integer -> IntegerInterval -> Bool

Is the element in the interval?

notMember :: Integer -> IntegerInterval -> Bool

Is the element not in the interval?

isSubsetOf :: IntegerInterval -> IntegerInterval -> Bool

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

isProperSubsetOf :: IntegerInterval -> IntegerInterval -> Bool

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

lowerBound :: IntegerInterval -> Extended Integer

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

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, Bool)

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, Bool)

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

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

Universal comparison operators

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

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

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

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

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

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

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

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

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

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

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

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

Existential comparison operators

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Combine

intersection :: IntegerInterval -> IntegerInterval -> IntegerInterval

intersection of two intervals

intersections :: [IntegerInterval] -> IntegerInterval

intersection of a list of intervals.

hull :: IntegerInterval -> IntegerInterval -> IntegerInterval

convex hull of two intervals

hulls :: [IntegerInterval] -> IntegerInterval

convex hull of a list of intervals.

Map

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

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

Operations

pickup :: IntegerInterval -> Maybe Integer

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

simplestIntegerWithin :: IntegerInterval -> Maybe Integer

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

Convert the interval to Interval data type.

fromInterval :: Interval Integer -> IntegerInterval

Conversion from Interval data type.

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

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

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

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