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

Data.Interval

Contents

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

Description

Interval datatype and interval arithmetic.

Unlike the intervals package (http://hackage.haskell.org/package/intervals), this module provides both open and closed intervals and is intended to be used with Rational.

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

Synopsis

data Interval r
module Data.ExtendedReal
data Boundary
- = Open
- | Closed
interval :: Ord r => (Extended r, Boundary) -> (Extended r, Boundary) -> Interval r
(<=..<=) :: Ord r => Extended r -> Extended r -> Interval r
(<..<=) :: Ord r => Extended r -> Extended r -> Interval r
(<=..<) :: Ord r => Extended r -> Extended r -> Interval r
(<..<) :: Ord r => Extended r -> Extended r -> Interval r
whole :: Ord r => Interval r
empty :: Ord r => Interval r
singleton :: Ord r => r -> Interval r
null :: Ord r => Interval r -> Bool
isSingleton :: Ord r => Interval r -> Bool
extractSingleton :: Ord r => Interval r -> Maybe r
member :: Ord r => r -> Interval r -> Bool
notMember :: Ord r => r -> Interval r -> Bool
isSubsetOf :: Ord r => Interval r -> Interval r -> Bool
isProperSubsetOf :: Ord r => Interval r -> Interval r -> Bool
isConnected :: Ord r => Interval r -> Interval r -> Bool
lowerBound :: Interval r -> Extended r
upperBound :: Interval r -> Extended r
lowerBound' :: Interval r -> (Extended r, Boundary)
upperBound' :: Interval r -> (Extended r, Boundary)
width :: (Num r, Ord r) => Interval r -> r
(<!) :: Ord r => Interval r -> Interval r -> Bool
(<=!) :: Ord r => Interval r -> Interval r -> Bool
(==!) :: Ord r => Interval r -> Interval r -> Bool
(>=!) :: Ord r => Interval r -> Interval r -> Bool
(>!) :: Ord r => Interval r -> Interval r -> Bool
(/=!) :: Ord r => Interval r -> Interval r -> Bool
(<?) :: Ord r => Interval r -> Interval r -> Bool
(<=?) :: Ord r => Interval r -> Interval r -> Bool
(==?) :: Ord r => Interval r -> Interval r -> Bool
(>=?) :: Ord r => Interval r -> Interval r -> Bool
(>?) :: Ord r => Interval r -> Interval r -> Bool
(/=?) :: Ord r => Interval r -> Interval r -> Bool
(<??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r)
(<=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r)
(==??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r)
(>=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r)
(>??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r)
(/=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r)
intersection :: forall r. Ord r => Interval r -> Interval r -> Interval r
intersections :: Ord r => [Interval r] -> Interval r
hull :: forall r. Ord r => Interval r -> Interval r -> Interval r
hulls :: Ord r => [Interval r] -> Interval r
mapMonotonic :: (Ord a, Ord b) => (a -> b) -> Interval a -> Interval b
pickup :: (Real r, Fractional r) => Interval r -> Maybe r
simplestRationalWithin :: RealFrac r => Interval r -> Maybe Rational
relate :: Ord r => Interval r -> Interval r -> Relation

Interval type

data Interval r Source #

The intervals (i.e. connected and convex subsets) over a type r.

Instances

Instances details

(Ord r, Data r) => Data (Interval r) 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) -> Interval r -> c (Interval r) # gunfold :: (forall b r0. Data b => c (b -> r0) -> c r0) -> (forall r1. r1 -> c r1) -> Constr -> c (Interval r) # toConstr :: Interval r -> Constr # dataTypeOf :: Interval r -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Interval r)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Interval r)) # gmapT :: (forall b. Data b => b -> b) -> Interval r -> Interval r # gmapQl :: (r0 -> r' -> r0) -> r0 -> (forall d. Data d => d -> r') -> Interval r -> r0 # gmapQr :: forall r0 r'. (r' -> r0 -> r0) -> r0 -> (forall d. Data d => d -> r') -> Interval r -> r0 # gmapQ :: (forall d. Data d => d -> u) -> Interval r -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Interval r -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Interval r -> m (Interval r) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Interval r -> m (Interval r) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Interval r -> m (Interval r) #
(Storable r, Ord r) => Storable (Interval r) Source #
Instance details Defined in Data.Interval.Internal Methods sizeOf :: Interval r -> Int # alignment :: Interval r -> Int # peekElemOff :: Ptr (Interval r) -> Int -> IO (Interval r) # pokeElemOff :: Ptr (Interval r) -> Int -> Interval r -> IO () # peekByteOff :: Ptr b -> Int -> IO (Interval r) # pokeByteOff :: Ptr b -> Int -> Interval r -> IO () # peek :: Ptr (Interval r) -> IO (Interval r) # poke :: Ptr (Interval r) -> Interval r -> IO () #
(RealFrac r, Floating r) => Floating (Interval r) Source #	When results of `tan` or `**` do not form a connected interval, a convex hull is returned instead.
Instance details Defined in Data.Interval Methods pi :: Interval r # exp :: Interval r -> Interval r # log :: Interval r -> Interval r # sqrt :: Interval r -> Interval r # (**) :: Interval r -> Interval r -> Interval r # logBase :: Interval r -> Interval r -> Interval r # sin :: Interval r -> Interval r # cos :: Interval r -> Interval r # tan :: Interval r -> Interval r # asin :: Interval r -> Interval r # acos :: Interval r -> Interval r # atan :: Interval r -> Interval r # sinh :: Interval r -> Interval r # cosh :: Interval r -> Interval r # tanh :: Interval r -> Interval r # asinh :: Interval r -> Interval r # acosh :: Interval r -> Interval r # atanh :: Interval r -> Interval r # log1p :: Interval r -> Interval r # expm1 :: Interval r -> Interval r # log1pexp :: Interval r -> Interval r # log1mexp :: Interval r -> Interval r #
(Num r, Ord r) => Num (Interval r) Source #	When results of `abs` or `signum` do not form a connected interval, a convex hull is returned instead.
Instance details Defined in Data.Interval Methods (+) :: Interval r -> Interval r -> Interval r # (-) :: Interval r -> Interval r -> Interval r # (*) :: Interval r -> Interval r -> Interval r # negate :: Interval r -> Interval r # abs :: Interval r -> Interval r # signum :: Interval r -> Interval r # fromInteger :: Integer -> Interval r #
(Ord r, Read r) => Read (Interval r) Source #
Instance details Defined in Data.Interval Methods readsPrec :: Int -> ReadS (Interval r) # readList :: ReadS [Interval r] # readPrec :: ReadPrec (Interval r) # readListPrec :: ReadPrec [Interval r] #
(Real r, Fractional r) => Fractional (Interval r) Source #	`recip` returns `whole` when 0 is an interior point. Otherwise `recip (recip xs)` equals to `xs` without 0.
Instance details Defined in Data.Interval Methods (/) :: Interval r -> Interval r -> Interval r # recip :: Interval r -> Interval r # fromRational :: Rational -> Interval r #
(Ord r, Show r) => Show (Interval r) Source #
Instance details Defined in Data.Interval Methods showsPrec :: Int -> Interval r -> ShowS # show :: Interval r -> String # showList :: [Interval r] -> ShowS #
NFData r => NFData (Interval r) Source #
Instance details Defined in Data.Interval.Internal Methods rnf :: Interval r -> () #
Eq r => Eq (Interval r) Source #
Instance details Defined in Data.Interval.Internal Methods (==) :: Interval r -> Interval r -> Bool # (/=) :: Interval r -> Interval r -> Bool #
Ord r => Ord (Interval r) Source #	Note that this Ord is derived and not semantically meaningful. The primary intended use case is to allow using `Interval` in maps and sets that require ordering.
Instance details Defined in Data.Interval.Internal Methods compare :: Interval r -> Interval r -> Ordering # (<) :: Interval r -> Interval r -> Bool # (<=) :: Interval r -> Interval r -> Bool # (>) :: Interval r -> Interval r -> Bool # (>=) :: Interval r -> Interval r -> Bool # max :: Interval r -> Interval r -> Interval r # min :: Interval r -> Interval r -> Interval r #
Hashable r => Hashable (Interval r) Source #
Instance details Defined in Data.Interval.Internal Methods hashWithSalt :: Int -> Interval r -> Int # hash :: Interval r -> Int #
Ord r => BoundedJoinSemiLattice (Interval r) Source #
Instance details Defined in Data.Interval Methods bottom :: Interval r #
Ord r => BoundedMeetSemiLattice (Interval r) Source #
Instance details Defined in Data.Interval Methods top :: Interval r #
Ord r => Lattice (Interval r) Source #
Instance details Defined in Data.Interval Methods (\/) :: Interval r -> Interval r -> Interval r # (/\) :: Interval r -> Interval r -> Interval r #

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

:: Ord r
=> (Extended r, Boundary)	lower bound and whether it is included
-> (Extended r, Boundary)	upper bound and whether it is included
-> Interval r

smart constructor for Interval

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

Arguments

:: Ord r
=> Extended r	lower bound `l`
-> Extended r	upper bound `u`
-> Interval r

closed interval [l,u]

(<..<=) infix 5 Source #

Arguments

:: Ord r
=> Extended r	lower bound `l`
-> Extended r	upper bound `u`
-> Interval r

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

(<=..<) infix 5 Source #

Arguments

:: Ord r
=> Extended r	lower bound `l`
-> Extended r	upper bound `u`
-> Interval r

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

(<..<) infix 5 Source #

Arguments

:: Ord r
=> Extended r	lower bound `l`
-> Extended r	upper bound `u`
-> Interval r

open interval (l, u)

whole :: Ord r => Interval r Source #

whole real number line (-∞, ∞)

empty :: Ord r => Interval r Source #

empty (contradicting) interval

singleton :: Ord r => r -> Interval r Source #

singleton set [x,x]

Query

null :: Ord r => Interval r -> Bool Source #

Is the interval empty?

isSingleton :: Ord r => Interval r -> Bool Source #

Is the interval single point?

Since: 2.0.0

extractSingleton :: Ord r => Interval r -> Maybe r Source #

If the interval is a single point, return this point.

Since: 2.1.0

member :: Ord r => r -> Interval r -> Bool Source #

Is the element in the interval?

notMember :: Ord r => r -> Interval r -> Bool Source #

Is the element not in the interval?

isSubsetOf :: Ord r => Interval r -> Interval r -> Bool Source #

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

isProperSubsetOf :: Ord r => Interval r -> Interval r -> Bool Source #

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

isConnected :: Ord r => Interval r -> Interval r -> Bool Source #

Does the union of two range form a connected set?

Since: 1.3.0

lowerBound :: Interval r -> Extended r 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 :: Interval r -> Extended r 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 may or may not be a member of the interval.

lowerBound' :: Interval r -> (Extended r, Boundary) Source #

Lower endpoint (i.e. greatest lower bound) of the interval, together with Boundary information. The result is convenient to use as an argument for interval.

upperBound' :: Interval r -> (Extended r, Boundary) Source #

Upper endpoint (i.e. least upper bound) of the interval, together with Boundary information. The result is convenient to use as an argument for interval.

width :: (Num r, Ord r) => Interval r -> r Source #

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

Universal comparison operators

(<!) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

(<=!) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

(==!) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

(>=!) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

(>!) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

(/=!) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

Since: 1.0.1

Existential comparison operators

(<?) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

(<=?) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

(==?) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

Since: 1.0.0

(>=?) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

(>?) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

(/=?) :: Ord r => Interval r -> Interval r -> Bool infix 4 Source #

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

Since: 1.0.1

Existential comparison operators that produce witnesses (experimental)

(<??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 Source #

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

Since: 1.0.0

(<=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 Source #

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

Since: 1.0.0

(==??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 Source #

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

Since: 1.0.0

(>=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 Source #

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

Since: 1.0.0

(>??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 Source #

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

Since: 1.0.0

(/=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 Source #

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

Since: 1.0.1

Combine

intersection :: forall r. Ord r => Interval r -> Interval r -> Interval r Source #

intersection of two intervals

intersections :: Ord r => [Interval r] -> Interval r Source #

intersection of a list of intervals.

Since: 0.6.0

hull :: forall r. Ord r => Interval r -> Interval r -> Interval r Source #

convex hull of two intervals

hulls :: Ord r => [Interval r] -> Interval r Source #

convex hull of a list of intervals.

Since: 0.6.0

Map

mapMonotonic :: (Ord a, Ord b) => (a -> b) -> Interval a -> Interval b Source #

mapMonotonic f i is the image of i under f, where f must be a strict monotone function, preserving negative and positive infinities.

Operations

pickup :: (Real r, Fractional r) => Interval r -> Maybe r Source #

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

simplestRationalWithin :: RealFrac r => Interval r -> Maybe Rational Source #

simplestRationalWithin returns the simplest rational number within the interval.

A rational number y is said to be simpler than another y' if

abs (numerator y) <= abs (numerator y'), and
denominator y <= denominator y'.

(see also approxRational)

Since: 0.4.0

Intervals relation

relate :: Ord r => Interval r -> Interval r -> Relation Source #

Computes how two intervals are related according to the Relation classification

Orphan instances

(RealFrac r, Floating r) => Floating (Interval r) Source #	When results of `tan` or `**` do not form a connected interval, a convex hull is returned instead.
Instance details Methods pi :: Interval r # exp :: Interval r -> Interval r # log :: Interval r -> Interval r # sqrt :: Interval r -> Interval r # (**) :: Interval r -> Interval r -> Interval r # logBase :: Interval r -> Interval r -> Interval r # sin :: Interval r -> Interval r # cos :: Interval r -> Interval r # tan :: Interval r -> Interval r # asin :: Interval r -> Interval r # acos :: Interval r -> Interval r # atan :: Interval r -> Interval r # sinh :: Interval r -> Interval r # cosh :: Interval r -> Interval r # tanh :: Interval r -> Interval r # asinh :: Interval r -> Interval r # acosh :: Interval r -> Interval r # atanh :: Interval r -> Interval r # log1p :: Interval r -> Interval r # expm1 :: Interval r -> Interval r # log1pexp :: Interval r -> Interval r # log1mexp :: Interval r -> Interval r #
(Num r, Ord r) => Num (Interval r) Source #	When results of `abs` or `signum` do not form a connected interval, a convex hull is returned instead.
Instance details Methods (+) :: Interval r -> Interval r -> Interval r # (-) :: Interval r -> Interval r -> Interval r # (*) :: Interval r -> Interval r -> Interval r # negate :: Interval r -> Interval r # abs :: Interval r -> Interval r # signum :: Interval r -> Interval r # fromInteger :: Integer -> Interval r #
(Ord r, Read r) => Read (Interval r) Source #
Instance details Methods readsPrec :: Int -> ReadS (Interval r) # readList :: ReadS [Interval r] # readPrec :: ReadPrec (Interval r) # readListPrec :: ReadPrec [Interval r] #
(Real r, Fractional r) => Fractional (Interval r) Source #	`recip` returns `whole` when 0 is an interior point. Otherwise `recip (recip xs)` equals to `xs` without 0.
Instance details Methods (/) :: Interval r -> Interval r -> Interval r # recip :: Interval r -> Interval r # fromRational :: Rational -> Interval r #
(Ord r, Show r) => Show (Interval r) Source #
Instance details Methods showsPrec :: Int -> Interval r -> ShowS # show :: Interval r -> String # showList :: [Interval r] -> ShowS #
Ord r => BoundedJoinSemiLattice (Interval r) Source #
Instance details Methods bottom :: Interval r #
Ord r => BoundedMeetSemiLattice (Interval r) Source #
Instance details Methods top :: Interval r #
Ord r => Lattice (Interval r) Source #
Instance details Methods (\/) :: Interval r -> Interval r -> Interval r # (/\) :: Interval r -> Interval r -> Interval r #