-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Interval datatype, interval arithmetic and interval-based containers -- -- Interval datatype, interval arithmetic and interval-based containers -- for Haskell. Unlike the intervals package -- (http://hackage.haskell.org/package/intervals), this package -- provides both open and closed intervals and is intended to be used -- with exact number types such as Rational and Integer. @package data-interval @version 1.3.0 -- | 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). module Data.Interval -- | The intervals (i.e. connected and convex subsets) over real -- numbers R. data Interval r -- | Endpoints of intervals -- | Deprecated: EndPoint is deprecated. Please use Extended -- instead. type EndPoint r = Extended r -- | smart constructor for Interval interval :: (Ord r) => (Extended r, Bool) -> (Extended r, Bool) -> Interval r -- | closed interval [l,u] (<=..<=) :: (Ord r) => Extended r -> Extended r -> Interval r infix 5 <=..<= -- | left-open right-closed interval (l,u] (<..<=) :: (Ord r) => Extended r -> Extended r -> Interval r infix 5 <..<= -- | left-closed right-open interval [l, u) (<=..<) :: (Ord r) => Extended r -> Extended r -> Interval r infix 5 <=..< -- | open interval (l, u) (<..<) :: (Ord r) => Extended r -> Extended r -> Interval r infix 5 <..< -- | whole real number line (-∞, ∞) whole :: Ord r => Interval r -- | empty (contradicting) interval empty :: Ord r => Interval r -- | singleton set <math> singleton :: Ord r => r -> Interval r -- | Is the interval empty? null :: Ord r => Interval r -> Bool -- | Is the element in the interval? member :: Ord r => r -> Interval r -> Bool -- | Is the element not in the interval? notMember :: Ord r => r -> Interval r -> Bool -- | Is this a subset? (i1 `isSubsetOf` i2) tells whether -- i1 is a subset of i2. isSubsetOf :: Ord r => Interval r -> Interval r -> Bool -- | Is this a proper subset? (i.e. a subset but not equal). isProperSubsetOf :: Ord r => Interval r -> Interval r -> Bool -- | Does the union of two range form a connected set? -- -- Since 1.3.0 isConnected :: Ord r => Interval r -> Interval r -> Bool -- | Lower endpoint (i.e. greatest lower bound) of the interval. -- -- lowerBound :: Interval r -> Extended r -- | Upper endpoint (i.e. least upper bound) of the interval. -- -- upperBound :: Interval r -> Extended r -- | lowerBound of the interval and whether it is included in the -- interval. The result is convenient to use as an argument for -- interval. lowerBound' :: Interval r -> (Extended r, Bool) -- | upperBound of the interval and whether it is included in the -- interval. The result is convenient to use as an argument for -- interval. upperBound' :: Interval r -> (Extended r, Bool) -- | Width of a interval. Width of an unbounded interval is -- undefined. width :: (Num r, Ord r) => Interval r -> r -- | For all x in X, y in Y. x -- < y? ( Interval r -> Interval r -> Bool infix 4 x in X, y in Y. x -- <= y? (<=!) :: Ord r => Interval r -> Interval r -> Bool infix 4 <=! -- | For all x in X, y in Y. x -- == y? (==!) :: Ord r => Interval r -> Interval r -> Bool infix 4 ==! -- | For all x in X, y in Y. x -- >= y? (>=!) :: Ord r => Interval r -> Interval r -> Bool infix 4 >=! -- | For all x in X, y in Y. x -- > y? (>!) :: Ord r => Interval r -> Interval r -> Bool infix 4 >! -- | For all x in X, y in Y. x -- /= y? -- -- Since 1.0.1 (/=!) :: Ord r => Interval r -> Interval r -> Bool infix 4 /=! -- | Does there exist an x in X, y in Y -- such that x < y? ( Interval r -> Interval r -> Bool infix 4 x in X, y in Y -- such that x <= y? (<=?) :: Ord r => Interval r -> Interval r -> Bool infix 4 <=? -- | 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 ==? -- | Does there exist an x in X, y in Y -- such that x >= y? (>=?) :: Ord r => Interval r -> Interval r -> Bool infix 4 >=? -- | Does there exist an x in X, y in Y -- such that x > y? (>?) :: Ord r => Interval r -> Interval r -> Bool infix 4 >? -- | Does there exist an x in X, y in Y -- such that x /= y? -- -- Since 1.0.1 (/=?) :: Ord r => Interval r -> Interval r -> Bool infix 4 /=? -- | Does there exist an x in X, y in Y -- such that x < y? -- -- Since 1.0.0 ( Interval r -> Interval r -> Maybe (r, r) infix 4 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 <=?? -- | 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 ==?? -- | 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 >=?? -- | 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 >?? -- | Does there exist an x in X, y in Y -- such that x /= y? -- -- Since 1.0.1 (/=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 /=?? -- | intersection of two intervals intersection :: forall r. Ord r => Interval r -> Interval r -> Interval r -- | intersection of a list of intervals. -- -- Since 0.6.0 intersections :: Ord r => [Interval r] -> Interval r -- | convex hull of two intervals hull :: forall r. Ord r => Interval r -> Interval r -> Interval r -- | convex hull of a list of intervals. -- -- Since 0.6.0 hulls :: Ord r => [Interval r] -> Interval r -- | mapMonotonic f i is the image of i under f, -- where f must be a strict monotone function. mapMonotonic :: (Ord a, Ord b) => (a -> b) -> Interval a -> Interval b -- | pick up an element from the interval if the interval is not empty. pickup :: (Real r, Fractional r) => Interval r -> Maybe r -- | simplestRationalWithin returns the simplest rational number -- within the interval. -- -- A rational number y is said to be simpler than another -- y' if -- -- -- -- (see also approxRational) -- -- Since 0.4.0 simplestRationalWithin :: RealFrac r => Interval r -> Maybe Rational instance GHC.Classes.Eq r => GHC.Classes.Eq (Data.Interval.Interval r) instance Control.DeepSeq.NFData r => Control.DeepSeq.NFData (Data.Interval.Interval r) instance Data.Hashable.Class.Hashable r => Data.Hashable.Class.Hashable (Data.Interval.Interval r) instance GHC.Classes.Ord r => Algebra.Lattice.JoinSemiLattice (Data.Interval.Interval r) instance GHC.Classes.Ord r => Algebra.Lattice.MeetSemiLattice (Data.Interval.Interval r) instance GHC.Classes.Ord r => Algebra.Lattice.Lattice (Data.Interval.Interval r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedJoinSemiLattice (Data.Interval.Interval r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedMeetSemiLattice (Data.Interval.Interval r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedLattice (Data.Interval.Interval r) instance (GHC.Classes.Ord r, GHC.Show.Show r) => GHC.Show.Show (Data.Interval.Interval r) instance (GHC.Classes.Ord r, GHC.Read.Read r) => GHC.Read.Read (Data.Interval.Interval r) instance (GHC.Classes.Ord r, Data.Data.Data r) => Data.Data.Data (Data.Interval.Interval r) instance (GHC.Num.Num r, GHC.Classes.Ord r) => GHC.Num.Num (Data.Interval.Interval r) instance (GHC.Real.Real r, GHC.Real.Fractional r) => GHC.Real.Fractional (Data.Interval.Interval r) -- | Interval datatype and interval arithmetic. module Data.IntervalSet -- | A set comprising zero or more non-empty, disconnected -- intervals. -- -- Any connected intervals are merged together, and empty intervals are -- ignored. data IntervalSet r -- | Endpoints of intervals -- | Deprecated: EndPoint is deprecated. Please use Extended -- instead. type EndPoint r = Extended r -- | whole real number line (-∞, ∞) whole :: Ord r => IntervalSet r -- | empty interval set empty :: Ord r => IntervalSet r -- | single interval singleton :: Ord r => Interval r -> IntervalSet r -- | Is the interval set empty? null :: IntervalSet r -> Bool -- | Is the element in the interval set? member :: Ord r => r -> IntervalSet r -> Bool -- | Is the element not in the interval set? notMember :: Ord r => r -> IntervalSet r -> Bool -- | Is this a subset? (is1 `isSubsetOf` is2) tells whether -- is1 is a subset of is2. isSubsetOf :: Ord r => IntervalSet r -> IntervalSet r -> Bool -- | Is this a proper subset? (i.e. a subset but not equal). isProperSubsetOf :: Ord r => IntervalSet r -> IntervalSet r -> Bool -- | convex hull of a set of intervals. span :: Ord r => IntervalSet r -> Interval r -- | Complement the interval set. complement :: Ord r => IntervalSet r -> IntervalSet r -- | Insert a new interval into the interval set. insert :: Ord r => Interval r -> IntervalSet r -> IntervalSet r -- | Delete an interval from the interval set. delete :: Ord r => Interval r -> IntervalSet r -> IntervalSet r -- | union of two interval sets union :: Ord r => IntervalSet r -> IntervalSet r -> IntervalSet r -- | union of a list of interval sets unions :: Ord r => [IntervalSet r] -> IntervalSet r -- | intersection of two interval sets intersection :: Ord r => IntervalSet r -> IntervalSet r -> IntervalSet r -- | intersection of a list of interval sets intersections :: Ord r => [IntervalSet r] -> IntervalSet r -- | difference of two interval sets difference :: Ord r => IntervalSet r -> IntervalSet r -> IntervalSet r -- | Build a interval set from a list of intervals. fromList :: Ord r => [Interval r] -> IntervalSet r -- | Convert a interval set into a list of intervals. toList :: Ord r => IntervalSet r -> [Interval r] -- | Convert a interval set into a list of intervals in ascending order. toAscList :: Ord r => IntervalSet r -> [Interval r] -- | Convert a interval set into a list of intervals in descending order. toDescList :: Ord r => IntervalSet r -> [Interval r] -- | Build a map from an ascending list of intervals. The precondition -- is not checked. fromAscList :: Ord r => [Interval r] -> IntervalSet r instance GHC.Classes.Eq r => GHC.Classes.Eq (Data.IntervalSet.IntervalSet r) instance (GHC.Classes.Ord r, GHC.Show.Show r) => GHC.Show.Show (Data.IntervalSet.IntervalSet r) instance (GHC.Classes.Ord r, GHC.Read.Read r) => GHC.Read.Read (Data.IntervalSet.IntervalSet r) instance (GHC.Classes.Ord r, Data.Data.Data r) => Data.Data.Data (Data.IntervalSet.IntervalSet r) instance Control.DeepSeq.NFData r => Control.DeepSeq.NFData (Data.IntervalSet.IntervalSet r) instance Data.Hashable.Class.Hashable r => Data.Hashable.Class.Hashable (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Algebra.Lattice.JoinSemiLattice (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Algebra.Lattice.MeetSemiLattice (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Algebra.Lattice.Lattice (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedJoinSemiLattice (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedMeetSemiLattice (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedLattice (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => GHC.Base.Monoid (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Data.Semigroup.Semigroup (Data.IntervalSet.IntervalSet r) instance (GHC.Num.Num r, GHC.Classes.Ord r) => GHC.Num.Num (Data.IntervalSet.IntervalSet r) instance (GHC.Real.Real r, GHC.Real.Fractional r) => GHC.Real.Fractional (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => GHC.Exts.IsList (Data.IntervalSet.IntervalSet r) -- | Mapping from intervals to values. -- -- API of this module is strict in the keys, but lazy in the values. If -- you need value-strict maps, use Data.IntervalMap.Strict -- instead. The IntervalMap type itself is shared between the lazy -- and strict modules, meaning that the same IntervalMap value can -- be passed to functions in both modules (although that is rarely -- needed). -- -- These modules are intended to be imported qualified, to avoid name -- clashes with Prelude functions, e.g. -- -- 
--   import Data.IntervalMap.Lazy (IntervalMap)
--   import qualified Data.IntervalMap.Lazy as IntervalMap
--
module Data.IntervalMap.Lazy -- | A Map from non-empty, disjoint intervals over k to values a. -- -- Unlike IntervalSet, IntervalMap never merge adjacent -- mappings, even if adjacent intervals are connected and mapped to the -- same value. data IntervalMap r a -- | Endpoints of intervals -- | Deprecated: EndPoint is deprecated. Please use Extended -- instead. type EndPoint r = Extended r -- | Find the value at a key. Calls error when the element can not -- be found. (!) :: Ord k => IntervalMap k a -> k -> a infixl 9 ! -- | Same as difference. (\\) :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a infixl 9 \\ -- | Is the map empty? null :: Ord k => IntervalMap k a -> Bool -- | Is the key a member of the map? See also notMember. member :: Ord k => k -> IntervalMap k a -> Bool -- | Is the key not a member of the map? See also member. notMember :: Ord k => k -> IntervalMap k a -> Bool -- | Lookup the value at a key in the map. -- -- The function will return the corresponding value as (Just -- value), or Nothing if the key isn't in the map. lookup :: Ord k => k -> IntervalMap k a -> Maybe a -- | The expression (findWithDefault def k map) returns the -- value at key k or returns default value def when the -- key is not in the map. findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a -- | convex hull of key intervals. span :: Ord k => IntervalMap k a -> Interval k -- | The map that maps whole range of k to a. whole :: Ord k => a -> IntervalMap k a -- | The empty map. empty :: Ord k => IntervalMap k a -- | A map with a single interval. singleton :: Ord k => Interval k -> a -> IntervalMap k a -- | insert a new key and value in the map. If the key is already present -- in the map, the associated value is replaced with the supplied value. insert :: Ord k => Interval k -> a -> IntervalMap k a -> IntervalMap k a -- | Insert with a function, combining new value and old value. -- insertWith f key value mp will insert the pair -- (interval, value) into mp. If the interval overlaps with -- existing entries, the value for the entry is replace with (f -- new_value old_value). insertWith :: Ord k => (a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a -- | Delete an interval and its value from the map. When the interval does -- not overlap with the map, the original map is returned. delete :: Ord k => Interval k -> IntervalMap k a -> IntervalMap k a -- | Update a value at a specific interval with the result of the provided -- function. When the interval does not overlatp with the map, the -- original map is returned. adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (update f i map) updates the value -- x at i (if it is in the map). If (f x) is -- Nothing, the element is deleted. If it is (Just -- y), the key i is bound to the new value y. update :: Ord k => (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (alter f i map) alters the value -- x at i, or absence thereof. alter can be used -- to insert, delete, or update a value in a IntervalMap. alter :: Ord k => (Maybe a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (union t1 t2) takes the left-biased -- union of t1 and t2. It prefers t1 when -- overlapping keys are encountered, union :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | Union with a combining function. unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | The union of a list of maps: (unions == foldl -- union empty). unions :: Ord k => [IntervalMap k a] -> IntervalMap k a -- | The union of a list of maps, with a combining operation: -- (unionsWith f == foldl (unionWith f) -- empty). unionsWith :: Ord k => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a -- | Intersection of two maps. Return data in the first map for the keys -- existing in both maps. intersection :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | Intersection with a combining function. intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c -- | Return elements of the first map not existing in the second map. difference :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a -- | Map a function over all values in the map. map :: (a -> b) -> IntervalMap k a -> IntervalMap k b -- | mapKeys f s is the map obtained by applying -- f to each key of s. f must be strictly -- monotonic. That is, for any values x and y, if -- x < y then f x < f y. mapKeysMonotonic :: forall k1 k2 a. (Ord k1, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a -- | Return all elements of the map in the ascending order of their keys. elems :: IntervalMap k a -> [a] -- | Return all keys of the map in ascending order. Subject to list keys :: IntervalMap k a -> [Interval k] -- | An alias for toAscList. Return all key/value pairs in the map -- in ascending key order. assocs :: IntervalMap k a -> [(Interval k, a)] -- | The set of all keys of the map. keysSet :: Ord k => IntervalMap k a -> IntervalSet k -- | Build a map from a list of key/value pairs. If the list contains more -- than one value for the same key, the last value for the key is -- retained. fromList :: Ord k => [(Interval k, a)] -> IntervalMap k a -- | Build a map from a list of key/value pairs with a combining function. fromListWith :: Ord k => (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a -- | Convert the map to a list of key/value pairs. toList :: IntervalMap k a -> [(Interval k, a)] -- | Convert the map to a list of key/value pairs where the keys are in -- ascending order. toAscList :: IntervalMap k a -> [(Interval k, a)] -- | Convert the map to a list of key/value pairs where the keys are in -- descending order. toDescList :: IntervalMap k a -> [(Interval k, a)] -- | Filter all values that satisfy some predicate. filter :: Ord k => (a -> Bool) -> IntervalMap k a -> IntervalMap k a -- | The expression (split i map) is a triple -- (map1,map2,map3) where the keys in map1 are smaller -- than i, the keys in map2 are included in i, -- and the keys in map3 are larger than i. split :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a, IntervalMap k a) -- | This function is defined as (isSubmapOf = -- isSubmapOfBy (==)). isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool -- | The expression (isSubmapOfBy f t1 t2) returns -- True if all keys in t1 are in tree t2, and -- when f returns True when applied to their respective -- values. isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool -- | Is this a proper submap? (ie. a submap but not equal). Defined as -- (isProperSubmapOf = isProperSubmapOfBy (==)). isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool -- | Is this a proper submap? (ie. a submap but not equal). The expression -- (isProperSubmapOfBy f m1 m2) returns True when -- m1 and m2 are not equal, all keys in m1 are -- in m2, and when f returns True when applied -- to their respective values. isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool -- | Mapping from intervals to values. -- -- API of this module is strict in both the keys and the values. If you -- need value-lazy maps, use Data.IntervalMap.Lazy instead. The -- IntervalMap type itself is shared between the lazy and strict -- modules, meaning that the same IntervalMap value can be passed -- to functions in both modules (although that is rarely needed). -- -- These modules are intended to be imported qualified, to avoid name -- clashes with Prelude functions, e.g. -- -- 
--   import Data.IntervalMap.Strict (IntervalMap)
--   import qualified Data.IntervalMap.Strict as IntervalMap
--
module Data.IntervalMap.Strict -- | A Map from non-empty, disjoint intervals over k to values a. -- -- Unlike IntervalSet, IntervalMap never merge adjacent -- mappings, even if adjacent intervals are connected and mapped to the -- same value. data IntervalMap r a -- | Endpoints of intervals -- | Deprecated: EndPoint is deprecated. Please use Extended -- instead. type EndPoint r = Extended r -- | Find the value at a key. Calls error when the element can not -- be found. (!) :: Ord k => IntervalMap k a -> k -> a infixl 9 ! -- | Same as difference. (\\) :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a infixl 9 \\ -- | Is the map empty? null :: Ord k => IntervalMap k a -> Bool -- | Is the key a member of the map? See also notMember. member :: Ord k => k -> IntervalMap k a -> Bool -- | Is the key not a member of the map? See also member. notMember :: Ord k => k -> IntervalMap k a -> Bool -- | Lookup the value at a key in the map. -- -- The function will return the corresponding value as (Just -- value), or Nothing if the key isn't in the map. lookup :: Ord k => k -> IntervalMap k a -> Maybe a -- | The expression (findWithDefault def k map) returns the -- value at key k or returns default value def when the -- key is not in the map. findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a -- | convex hull of key intervals. span :: Ord k => IntervalMap k a -> Interval k -- | The map that maps whole range of k to a. whole :: Ord k => a -> IntervalMap k a -- | The empty map. empty :: Ord k => IntervalMap k a -- | A map with a single interval. singleton :: Ord k => Interval k -> a -> IntervalMap k a -- | insert a new key and value in the map. If the key is already present -- in the map, the associated value is replaced with the supplied value. insert :: Ord k => Interval k -> a -> IntervalMap k a -> IntervalMap k a -- | Insert with a function, combining new value and old value. -- insertWith f key value mp will insert the pair -- (interval, value) into mp. If the interval overlaps with -- existing entries, the value for the entry is replace with (f -- new_value old_value). insertWith :: Ord k => (a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a -- | Delete an interval and its value from the map. When the interval does -- not overlap with the map, the original map is returned. delete :: Ord k => Interval k -> IntervalMap k a -> IntervalMap k a -- | Update a value at a specific interval with the result of the provided -- function. When the interval does not overlatp with the map, the -- original map is returned. adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (update f i map) updates the value -- x at i (if it is in the map). If (f x) is -- Nothing, the element is deleted. If it is (Just -- y), the key i is bound to the new value y. update :: Ord k => (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (alter f i map) alters the value -- x at i, or absence thereof. alter can be used -- to insert, delete, or update a value in a IntervalMap. alter :: Ord k => (Maybe a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (union t1 t2) takes the left-biased -- union of t1 and t2. It prefers t1 when -- overlapping keys are encountered, union :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | Union with a combining function. unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | The union of a list of maps: (unions == foldl -- union empty). unions :: Ord k => [IntervalMap k a] -> IntervalMap k a -- | The union of a list of maps, with a combining operation: -- (unionsWith f == foldl (unionWith f) -- empty). unionsWith :: Ord k => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a -- | Intersection of two maps. Return data in the first map for the keys -- existing in both maps. intersection :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | Intersection with a combining function. intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c -- | Return elements of the first map not existing in the second map. difference :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a -- | Map a function over all values in the map. map :: (a -> b) -> IntervalMap k a -> IntervalMap k b -- | mapKeys f s is the map obtained by applying -- f to each key of s. f must be strictly -- monotonic. That is, for any values x and y, if -- x < y then f x < f y. mapKeysMonotonic :: forall k1 k2 a. (Ord k1, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a -- | Return all elements of the map in the ascending order of their keys. elems :: IntervalMap k a -> [a] -- | Return all keys of the map in ascending order. Subject to list keys :: IntervalMap k a -> [Interval k] -- | An alias for toAscList. Return all key/value pairs in the map -- in ascending key order. assocs :: IntervalMap k a -> [(Interval k, a)] -- | The set of all keys of the map. keysSet :: Ord k => IntervalMap k a -> IntervalSet k -- | Build a map from a list of key/value pairs. If the list contains more -- than one value for the same key, the last value for the key is -- retained. fromList :: Ord k => [(Interval k, a)] -> IntervalMap k a -- | Build a map from a list of key/value pairs with a combining function. fromListWith :: Ord k => (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a -- | Convert the map to a list of key/value pairs. toList :: IntervalMap k a -> [(Interval k, a)] -- | Convert the map to a list of key/value pairs where the keys are in -- ascending order. toAscList :: IntervalMap k a -> [(Interval k, a)] -- | Convert the map to a list of key/value pairs where the keys are in -- descending order. toDescList :: IntervalMap k a -> [(Interval k, a)] -- | Filter all values that satisfy some predicate. filter :: Ord k => (a -> Bool) -> IntervalMap k a -> IntervalMap k a -- | The expression (split i map) is a triple -- (map1,map2,map3) where the keys in map1 are smaller -- than i, the keys in map2 are included in i, -- and the keys in map3 are larger than i. split :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a, IntervalMap k a) -- | This function is defined as (isSubmapOf = -- isSubmapOfBy (==)). isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool -- | The expression (isSubmapOfBy f t1 t2) returns -- True if all keys in t1 are in tree t2, and -- when f returns True when applied to their respective -- values. isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool -- | Is this a proper submap? (ie. a submap but not equal). Defined as -- (isProperSubmapOf = isProperSubmapOfBy (==)). isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool -- | Is this a proper submap? (ie. a submap but not equal). The expression -- (isProperSubmapOfBy f m1 m2) returns True when -- m1 and m2 are not equal, all keys in m1 are -- in m2, and when f returns True when applied -- to their respective values. isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool -- | 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). module Data.IntegerInterval -- | The intervals (i.e. connected and convex subsets) over integers -- (Z). data IntegerInterval -- | smart constructor for IntegerInterval interval :: (Extended Integer, Bool) -> (Extended Integer, Bool) -> IntegerInterval -- | closed interval [l,u] (<=..<=) :: Extended Integer -> Extended Integer -> IntegerInterval infix 5 <=..<= -- | left-open right-closed interval (l,u] (<..<=) :: Extended Integer -> Extended Integer -> IntegerInterval infix 5 <..<= -- | left-closed right-open interval [l, u) (<=..<) :: Extended Integer -> Extended Integer -> IntegerInterval infix 5 <=..< -- | open interval (l, u) (<..<) :: Extended Integer -> Extended Integer -> IntegerInterval infix 5 <..< -- | whole real number line (-∞, ∞) whole :: IntegerInterval -- | empty (contradicting) interval empty :: IntegerInterval -- | singleton set <math> singleton :: Integer -> IntegerInterval -- | Is the interval empty? null :: IntegerInterval -> Bool -- | Is the element in the interval? member :: Integer -> IntegerInterval -> Bool -- | Is the element not in the interval? notMember :: Integer -> IntegerInterval -> Bool -- | Is this a subset? (i1 `isSubsetOf` i2) tells whether -- i1 is a subset of i2. isSubsetOf :: IntegerInterval -> IntegerInterval -> Bool -- | Is this a proper subset? (i.e. a subset but not equal). isProperSubsetOf :: IntegerInterval -> IntegerInterval -> Bool -- | Lower endpoint (i.e. greatest lower bound) of the interval. -- -- lowerBound :: IntegerInterval -> Extended Integer -- | Upper endpoint (i.e. least upper bound) of the interval. -- -- upperBound :: IntegerInterval -> Extended Integer -- | lowerBound of the interval and whether it is included in the -- interval. The result is convenient to use as an argument for -- interval. lowerBound' :: 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. upperBound' :: IntegerInterval -> (Extended Integer, Bool) -- | Width of a interval. Width of an unbounded interval is -- undefined. width :: IntegerInterval -> Integer -- | For all x in X, y in Y. x -- < y? ( IntegerInterval -> Bool infix 4 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 /=! -- | Does there exist an x in X, y in Y -- such that x < y? ( IntegerInterval -> Bool infix 4 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? ( IntegerInterval -> Maybe (Integer, Integer) infix 4 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 /=?? -- | intersection of two intervals intersection :: IntegerInterval -> IntegerInterval -> IntegerInterval -- | intersection of a list of intervals. intersections :: [IntegerInterval] -> IntegerInterval -- | convex hull of two intervals hull :: IntegerInterval -> IntegerInterval -> IntegerInterval -- | convex hull of a list of intervals. hulls :: [IntegerInterval] -> IntegerInterval -- | mapMonotonic f i is the image of i under f, -- where f must be a strict monotone function. mapMonotonic :: (Integer -> Integer) -> IntegerInterval -> IntegerInterval -- | pick up an element from the interval if the interval is not empty. pickup :: IntegerInterval -> Maybe Integer -- | simplestIntegerWithin returns the simplest rational number -- within the interval. -- -- An integer y is said to be simpler than another -- y' if -- -- -- -- (see also approxRational and simplestRationalWithin) simplestIntegerWithin :: IntegerInterval -> Maybe Integer -- | Convert the interval to Interval data type. toInterval :: Real r => IntegerInterval -> Interval r -- | Conversion from Interval data type. fromInterval :: Interval Integer -> IntegerInterval -- | Given a Interval I over R, compute the smallest -- IntegerInterval J such that I ⊆ J. fromIntervalOver :: RealFrac r => Interval r -> IntegerInterval -- | Given a Interval I over R, compute the largest -- IntegerInterval J such that J ⊆ I. fromIntervalUnder :: RealFrac r => Interval r -> IntegerInterval instance GHC.Classes.Eq Data.IntegerInterval.IntegerInterval instance Control.DeepSeq.NFData Data.IntegerInterval.IntegerInterval instance Data.Hashable.Class.Hashable Data.IntegerInterval.IntegerInterval instance Algebra.Lattice.JoinSemiLattice Data.IntegerInterval.IntegerInterval instance Algebra.Lattice.MeetSemiLattice Data.IntegerInterval.IntegerInterval instance Algebra.Lattice.Lattice Data.IntegerInterval.IntegerInterval instance Algebra.Lattice.BoundedJoinSemiLattice Data.IntegerInterval.IntegerInterval instance Algebra.Lattice.BoundedMeetSemiLattice Data.IntegerInterval.IntegerInterval instance Algebra.Lattice.BoundedLattice Data.IntegerInterval.IntegerInterval instance GHC.Show.Show Data.IntegerInterval.IntegerInterval instance GHC.Read.Read Data.IntegerInterval.IntegerInterval instance Data.Data.Data Data.IntegerInterval.IntegerInterval instance GHC.Num.Num Data.IntegerInterval.IntegerInterval