{-# LANGUAGE TypeSynonymInstances, FlexibleInstances, DeriveDataTypeable #-} {- | Module : ./CSL/TreePO.hs Description : Handling of tree-like partial ordering relations Copyright : (c) Ewaryst Schulz, DFKI Bremen 2010 License : GPLv2 or higher, see LICENSE.txt Maintainer : ewaryst.schulz@dfki.de Stability : experimental Portability : portable This module defines a basic datatype for tree-like partial orderings such as encountered, e.g., in the set lattice. -} module CSL.TreePO {- ( Incomparable (..) , SetOrdering (..) , SetOrInterval (..) , swapCompare , swapCmp , combineCmp ) -} where import Data.Data import qualified Data.Set as Set {- ---------------------------------------------------------------------- Datatypes for comparison ---------------------------------------------------------------------- -} data Incomparable = Disjoint | Overlap deriving (Incomparable -> Incomparable -> Bool (Incomparable -> Incomparable -> Bool) -> (Incomparable -> Incomparable -> Bool) -> Eq Incomparable forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: Incomparable -> Incomparable -> Bool $c/= :: Incomparable -> Incomparable -> Bool == :: Incomparable -> Incomparable -> Bool $c== :: Incomparable -> Incomparable -> Bool Eq, Int -> Incomparable -> ShowS [Incomparable] -> ShowS Incomparable -> String (Int -> Incomparable -> ShowS) -> (Incomparable -> String) -> ([Incomparable] -> ShowS) -> Show Incomparable forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [Incomparable] -> ShowS $cshowList :: [Incomparable] -> ShowS show :: Incomparable -> String $cshow :: Incomparable -> String showsPrec :: Int -> Incomparable -> ShowS $cshowsPrec :: Int -> Incomparable -> ShowS Show, Typeable, Typeable Incomparable Constr DataType Typeable Incomparable => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Incomparable -> c Incomparable) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Incomparable) -> (Incomparable -> Constr) -> (Incomparable -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Incomparable)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Incomparable)) -> ((forall b. Data b => b -> b) -> Incomparable -> Incomparable) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r) -> (forall u. (forall d. Data d => d -> u) -> Incomparable -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> Incomparable -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable) -> Data Incomparable Incomparable -> Constr Incomparable -> DataType (forall b. Data b => b -> b) -> Incomparable -> Incomparable (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Incomparable -> c Incomparable (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Incomparable forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> Incomparable -> u forall u. (forall d. Data d => d -> u) -> Incomparable -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Incomparable forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Incomparable -> c Incomparable forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Incomparable) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Incomparable) $cOverlap :: Constr $cDisjoint :: Constr $tIncomparable :: DataType gmapMo :: (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable $cgmapMo :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable gmapMp :: (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable $cgmapMp :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable gmapM :: (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable $cgmapM :: forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable gmapQi :: Int -> (forall d. Data d => d -> u) -> Incomparable -> u $cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Incomparable -> u gmapQ :: (forall d. Data d => d -> u) -> Incomparable -> [u] $cgmapQ :: forall u. (forall d. Data d => d -> u) -> Incomparable -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r $cgmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r $cgmapQl :: forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r gmapT :: (forall b. Data b => b -> b) -> Incomparable -> Incomparable $cgmapT :: (forall b. Data b => b -> b) -> Incomparable -> Incomparable dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Incomparable) $cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Incomparable) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c Incomparable) $cdataCast1 :: forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c Incomparable) dataTypeOf :: Incomparable -> DataType $cdataTypeOf :: Incomparable -> DataType toConstr :: Incomparable -> Constr $ctoConstr :: Incomparable -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Incomparable $cgunfold :: forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Incomparable gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Incomparable -> c Incomparable $cgfoldl :: forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Incomparable -> c Incomparable $cp1Data :: Typeable Incomparable Data) data SetOrdering = Comparable Ordering | Incomparable Incomparable deriving (SetOrdering -> SetOrdering -> Bool (SetOrdering -> SetOrdering -> Bool) -> (SetOrdering -> SetOrdering -> Bool) -> Eq SetOrdering forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: SetOrdering -> SetOrdering -> Bool $c/= :: SetOrdering -> SetOrdering -> Bool == :: SetOrdering -> SetOrdering -> Bool $c== :: SetOrdering -> SetOrdering -> Bool Eq, Typeable, Typeable SetOrdering Constr DataType Typeable SetOrdering => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrdering -> c SetOrdering) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c SetOrdering) -> (SetOrdering -> Constr) -> (SetOrdering -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c SetOrdering)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c SetOrdering)) -> ((forall b. Data b => b -> b) -> SetOrdering -> SetOrdering) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r) -> (forall u. (forall d. Data d => d -> u) -> SetOrdering -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> SetOrdering -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering) -> Data SetOrdering SetOrdering -> Constr SetOrdering -> DataType (forall b. Data b => b -> b) -> SetOrdering -> SetOrdering (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrdering -> c SetOrdering (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c SetOrdering forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> SetOrdering -> u forall u. (forall d. Data d => d -> u) -> SetOrdering -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c SetOrdering forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrdering -> c SetOrdering forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c SetOrdering) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c SetOrdering) $cIncomparable :: Constr $cComparable :: Constr $tSetOrdering :: DataType gmapMo :: (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering $cgmapMo :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering gmapMp :: (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering $cgmapMp :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering gmapM :: (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering $cgmapM :: forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering gmapQi :: Int -> (forall d. Data d => d -> u) -> SetOrdering -> u $cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> SetOrdering -> u gmapQ :: (forall d. Data d => d -> u) -> SetOrdering -> [u] $cgmapQ :: forall u. (forall d. Data d => d -> u) -> SetOrdering -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r $cgmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r $cgmapQl :: forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r gmapT :: (forall b. Data b => b -> b) -> SetOrdering -> SetOrdering $cgmapT :: (forall b. Data b => b -> b) -> SetOrdering -> SetOrdering dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c SetOrdering) $cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c SetOrdering) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c SetOrdering) $cdataCast1 :: forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c SetOrdering) dataTypeOf :: SetOrdering -> DataType $cdataTypeOf :: SetOrdering -> DataType toConstr :: SetOrdering -> Constr $ctoConstr :: SetOrdering -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c SetOrdering $cgunfold :: forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c SetOrdering gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrdering -> c SetOrdering $cgfoldl :: forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrdering -> c SetOrdering $cp1Data :: Typeable SetOrdering Data) instance Show SetOrdering where show :: SetOrdering -> String show (Comparable LT) = "<" show (Comparable GT) = ">" show (Comparable EQ) = "=" show (Incomparable x :: Incomparable x) = Incomparable -> String forall a. Show a => a -> String show Incomparable x {- | We represent Intervals with opened or closed end points over a linearly ordered type 'a' as closed intervals over the type '(a, InfDev)', for infinitesimal deviation. - '(x, EpsLeft)' means an epsilon to the left of x - '(x, Zero)' means x - '(x, EpsRight)' means an epsilon to the right of x We have EpsLeft < Zero < EpsRight and the ordering of 'a' lifts to the lexicographical ordering of '(a, InfDev)' which captures well our intended meaning. We inject the type 'a' into the type '(a, InfDev)' by mapping 'x' to '(x, Zero)'. The mapping of intrvals is as follows: A left opened interval starting at x becomes a left closed interval starting at '(x, EpsRight)'. We have: 'forall y > x. (y, _) > (x, EpsRight)', hence in particular '(y, Zero) > (x, EpsRight)' but also '(x, Zero) < (x, EpsRight)' Analogously we represent a right opened one ending at y as a closed one ending at '(x, EpsLeft)'. -} data InfDev = EpsLeft | Zero | EpsRight deriving (InfDev -> InfDev -> Bool (InfDev -> InfDev -> Bool) -> (InfDev -> InfDev -> Bool) -> Eq InfDev forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: InfDev -> InfDev -> Bool $c/= :: InfDev -> InfDev -> Bool == :: InfDev -> InfDev -> Bool $c== :: InfDev -> InfDev -> Bool Eq, Int -> InfDev -> ShowS [InfDev] -> ShowS InfDev -> String (Int -> InfDev -> ShowS) -> (InfDev -> String) -> ([InfDev] -> ShowS) -> Show InfDev forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [InfDev] -> ShowS $cshowList :: [InfDev] -> ShowS show :: InfDev -> String $cshow :: InfDev -> String showsPrec :: Int -> InfDev -> ShowS $cshowsPrec :: Int -> InfDev -> ShowS Show, Typeable, Typeable InfDev Constr DataType Typeable InfDev => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfDev -> c InfDev) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfDev) -> (InfDev -> Constr) -> (InfDev -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c InfDev)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfDev)) -> ((forall b. Data b => b -> b) -> InfDev -> InfDev) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r) -> (forall u. (forall d. Data d => d -> u) -> InfDev -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> InfDev -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev) -> Data InfDev InfDev -> Constr InfDev -> DataType (forall b. Data b => b -> b) -> InfDev -> InfDev (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfDev -> c InfDev (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfDev forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> InfDev -> u forall u. (forall d. Data d => d -> u) -> InfDev -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfDev forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfDev -> c InfDev forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c InfDev) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfDev) $cEpsRight :: Constr $cZero :: Constr $cEpsLeft :: Constr $tInfDev :: DataType gmapMo :: (forall d. Data d => d -> m d) -> InfDev -> m InfDev $cgmapMo :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev gmapMp :: (forall d. Data d => d -> m d) -> InfDev -> m InfDev $cgmapMp :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev gmapM :: (forall d. Data d => d -> m d) -> InfDev -> m InfDev $cgmapM :: forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev gmapQi :: Int -> (forall d. Data d => d -> u) -> InfDev -> u $cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> InfDev -> u gmapQ :: (forall d. Data d => d -> u) -> InfDev -> [u] $cgmapQ :: forall u. (forall d. Data d => d -> u) -> InfDev -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r $cgmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r $cgmapQl :: forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r gmapT :: (forall b. Data b => b -> b) -> InfDev -> InfDev $cgmapT :: (forall b. Data b => b -> b) -> InfDev -> InfDev dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfDev) $cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfDev) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c InfDev) $cdataCast1 :: forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c InfDev) dataTypeOf :: InfDev -> DataType $cdataTypeOf :: InfDev -> DataType toConstr :: InfDev -> Constr $ctoConstr :: InfDev -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfDev $cgunfold :: forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfDev gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfDev -> c InfDev $cgfoldl :: forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfDev -> c InfDev $cp1Data :: Typeable InfDev Data) instance Ord InfDev where compare :: InfDev -> InfDev -> Ordering compare x :: InfDev x y :: InfDev y | InfDev x InfDev -> InfDev -> Bool forall a. Eq a => a -> a -> Bool == InfDev y = Ordering EQ | Bool otherwise = case (InfDev x, InfDev y) of (EpsLeft, _) -> Ordering LT (EpsRight, _) -> Ordering GT _ -> Ordering -> Ordering swapCompare (Ordering -> Ordering) -> Ordering -> Ordering forall a b. (a -> b) -> a -> b $ InfDev -> InfDev -> Ordering forall a. Ord a => a -> a -> Ordering compare InfDev y InfDev x newtype CIType a = CIType (a, InfDev) deriving (CIType a -> CIType a -> Bool (CIType a -> CIType a -> Bool) -> (CIType a -> CIType a -> Bool) -> Eq (CIType a) forall a. Eq a => CIType a -> CIType a -> Bool forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: CIType a -> CIType a -> Bool $c/= :: forall a. Eq a => CIType a -> CIType a -> Bool == :: CIType a -> CIType a -> Bool $c== :: forall a. Eq a => CIType a -> CIType a -> Bool Eq, Int -> CIType a -> ShowS [CIType a] -> ShowS CIType a -> String (Int -> CIType a -> ShowS) -> (CIType a -> String) -> ([CIType a] -> ShowS) -> Show (CIType a) forall a. Show a => Int -> CIType a -> ShowS forall a. Show a => [CIType a] -> ShowS forall a. Show a => CIType a -> String forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [CIType a] -> ShowS $cshowList :: forall a. Show a => [CIType a] -> ShowS show :: CIType a -> String $cshow :: forall a. Show a => CIType a -> String showsPrec :: Int -> CIType a -> ShowS $cshowsPrec :: forall a. Show a => Int -> CIType a -> ShowS Show, Typeable, Typeable (CIType a) Constr DataType Typeable (CIType a) => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> CIType a -> c (CIType a)) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (CIType a)) -> (CIType a -> Constr) -> (CIType a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (CIType a))) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a))) -> ((forall b. Data b => b -> b) -> CIType a -> CIType a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r) -> (forall u. (forall d. Data d => d -> u) -> CIType a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> CIType a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a)) -> Data (CIType a) CIType a -> Constr CIType a -> DataType (forall d. Data d => c (t d)) -> Maybe (c (CIType a)) (forall b. Data b => b -> b) -> CIType a -> CIType a (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> CIType a -> c (CIType a) (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (CIType a) forall a. Data a => Typeable (CIType a) forall a. Data a => CIType a -> Constr forall a. Data a => CIType a -> DataType forall a. Data a => (forall b. Data b => b -> b) -> CIType a -> CIType a forall a u. Data a => Int -> (forall d. Data d => d -> u) -> CIType a -> u forall a u. Data a => (forall d. Data d => d -> u) -> CIType a -> [u] forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (CIType a) forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> CIType a -> c (CIType a) forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (CIType a)) forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a)) forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> CIType a -> u forall u. (forall d. Data d => d -> u) -> CIType a -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (CIType a) forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> CIType a -> c (CIType a) forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (CIType a)) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a)) $cCIType :: Constr $tCIType :: DataType gmapMo :: (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) $cgmapMo :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) gmapMp :: (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) $cgmapMp :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) gmapM :: (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) $cgmapM :: forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a) gmapQi :: Int -> (forall d. Data d => d -> u) -> CIType a -> u $cgmapQi :: forall a u. Data a => Int -> (forall d. Data d => d -> u) -> CIType a -> u gmapQ :: (forall d. Data d => d -> u) -> CIType a -> [u] $cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> CIType a -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r $cgmapQr :: forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r $cgmapQl :: forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r gmapT :: (forall b. Data b => b -> b) -> CIType a -> CIType a $cgmapT :: forall a. Data a => (forall b. Data b => b -> b) -> CIType a -> CIType a dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a)) $cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a)) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (CIType a)) $cdataCast1 :: forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (CIType a)) dataTypeOf :: CIType a -> DataType $cdataTypeOf :: forall a. Data a => CIType a -> DataType toConstr :: CIType a -> Constr $ctoConstr :: forall a. Data a => CIType a -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (CIType a) $cgunfold :: forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (CIType a) gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> CIType a -> c (CIType a) $cgfoldl :: forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> CIType a -> c (CIType a) $cp1Data :: forall a. Data a => Typeable (CIType a) Data) {- | This type with the given ordering is to represent opened/closed intervals over 'a' as closed intervals over '(a, InfDev)' -} instance Ord a => Ord (CIType a) where compare :: CIType a -> CIType a -> Ordering compare (CIType (x :: a x, a :: InfDev a)) (CIType (y :: a y, b :: InfDev b)) = case a -> a -> Ordering forall a. Ord a => a -> a -> Ordering compare a x a y of EQ -> InfDev -> InfDev -> Ordering forall a. Ord a => a -> a -> Ordering compare InfDev a InfDev b res :: Ordering res -> Ordering res -- | A finite set or an interval. True = closed, False = opened interval border. data SetOrInterval a = Set (Set.Set a) | IntVal (a, Bool) (a, Bool) deriving (SetOrInterval a -> SetOrInterval a -> Bool (SetOrInterval a -> SetOrInterval a -> Bool) -> (SetOrInterval a -> SetOrInterval a -> Bool) -> Eq (SetOrInterval a) forall a. Eq a => SetOrInterval a -> SetOrInterval a -> Bool forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: SetOrInterval a -> SetOrInterval a -> Bool $c/= :: forall a. Eq a => SetOrInterval a -> SetOrInterval a -> Bool == :: SetOrInterval a -> SetOrInterval a -> Bool $c== :: forall a. Eq a => SetOrInterval a -> SetOrInterval a -> Bool Eq, Eq (SetOrInterval a) Eq (SetOrInterval a) => (SetOrInterval a -> SetOrInterval a -> Ordering) -> (SetOrInterval a -> SetOrInterval a -> Bool) -> (SetOrInterval a -> SetOrInterval a -> Bool) -> (SetOrInterval a -> SetOrInterval a -> Bool) -> (SetOrInterval a -> SetOrInterval a -> Bool) -> (SetOrInterval a -> SetOrInterval a -> SetOrInterval a) -> (SetOrInterval a -> SetOrInterval a -> SetOrInterval a) -> Ord (SetOrInterval a) SetOrInterval a -> SetOrInterval a -> Bool SetOrInterval a -> SetOrInterval a -> Ordering SetOrInterval a -> SetOrInterval a -> SetOrInterval a forall a. Eq a => (a -> a -> Ordering) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> a) -> (a -> a -> a) -> Ord a forall a. Ord a => Eq (SetOrInterval a) forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Ordering forall a. Ord a => SetOrInterval a -> SetOrInterval a -> SetOrInterval a min :: SetOrInterval a -> SetOrInterval a -> SetOrInterval a $cmin :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> SetOrInterval a max :: SetOrInterval a -> SetOrInterval a -> SetOrInterval a $cmax :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> SetOrInterval a >= :: SetOrInterval a -> SetOrInterval a -> Bool $c>= :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool > :: SetOrInterval a -> SetOrInterval a -> Bool $c> :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool <= :: SetOrInterval a -> SetOrInterval a -> Bool $c<= :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool < :: SetOrInterval a -> SetOrInterval a -> Bool $c< :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Bool compare :: SetOrInterval a -> SetOrInterval a -> Ordering $ccompare :: forall a. Ord a => SetOrInterval a -> SetOrInterval a -> Ordering $cp1Ord :: forall a. Ord a => Eq (SetOrInterval a) Ord, Int -> SetOrInterval a -> ShowS [SetOrInterval a] -> ShowS SetOrInterval a -> String (Int -> SetOrInterval a -> ShowS) -> (SetOrInterval a -> String) -> ([SetOrInterval a] -> ShowS) -> Show (SetOrInterval a) forall a. Show a => Int -> SetOrInterval a -> ShowS forall a. Show a => [SetOrInterval a] -> ShowS forall a. Show a => SetOrInterval a -> String forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [SetOrInterval a] -> ShowS $cshowList :: forall a. Show a => [SetOrInterval a] -> ShowS show :: SetOrInterval a -> String $cshow :: forall a. Show a => SetOrInterval a -> String showsPrec :: Int -> SetOrInterval a -> ShowS $cshowsPrec :: forall a. Show a => Int -> SetOrInterval a -> ShowS Show, Typeable, Typeable (SetOrInterval a) Constr DataType Typeable (SetOrInterval a) => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a)) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SetOrInterval a)) -> (SetOrInterval a -> Constr) -> (SetOrInterval a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a))) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SetOrInterval a))) -> ((forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r) -> (forall u. (forall d. Data d => d -> u) -> SetOrInterval a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a)) -> Data (SetOrInterval a) SetOrInterval a -> Constr SetOrInterval a -> DataType (forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a)) (forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a) (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SetOrInterval a) forall a. (Data a, Ord a) => Typeable (SetOrInterval a) forall a. (Data a, Ord a) => SetOrInterval a -> Constr forall a. (Data a, Ord a) => SetOrInterval a -> DataType forall a. (Data a, Ord a) => (forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a forall a u. (Data a, Ord a) => Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u forall a u. (Data a, Ord a) => (forall d. Data d => d -> u) -> SetOrInterval a -> [u] forall a r r'. (Data a, Ord a) => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r forall a r r'. (Data a, Ord a) => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r forall a (m :: * -> *). (Data a, Ord a, Monad m) => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) forall a (m :: * -> *). (Data a, Ord a, MonadPlus m) => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) forall a (c :: * -> *). (Data a, Ord a) => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SetOrInterval a) forall a (c :: * -> *). (Data a, Ord a) => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a) forall a (t :: * -> *) (c :: * -> *). (Data a, Ord a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a)) forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Ord a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SetOrInterval a)) forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u forall u. (forall d. Data d => d -> u) -> SetOrInterval a -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SetOrInterval a) forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a) forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a)) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SetOrInterval a)) $cIntVal :: Constr $cSet :: Constr $tSetOrInterval :: DataType gmapMo :: (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) $cgmapMo :: forall a (m :: * -> *). (Data a, Ord a, MonadPlus m) => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) gmapMp :: (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) $cgmapMp :: forall a (m :: * -> *). (Data a, Ord a, MonadPlus m) => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) gmapM :: (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) $cgmapM :: forall a (m :: * -> *). (Data a, Ord a, Monad m) => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a) gmapQi :: Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u $cgmapQi :: forall a u. (Data a, Ord a) => Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u gmapQ :: (forall d. Data d => d -> u) -> SetOrInterval a -> [u] $cgmapQ :: forall a u. (Data a, Ord a) => (forall d. Data d => d -> u) -> SetOrInterval a -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r $cgmapQr :: forall a r r'. (Data a, Ord a) => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r $cgmapQl :: forall a r r'. (Data a, Ord a) => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r gmapT :: (forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a $cgmapT :: forall a. (Data a, Ord a) => (forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SetOrInterval a)) $cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Ord a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SetOrInterval a)) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a)) $cdataCast1 :: forall a (t :: * -> *) (c :: * -> *). (Data a, Ord a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a)) dataTypeOf :: SetOrInterval a -> DataType $cdataTypeOf :: forall a. (Data a, Ord a) => SetOrInterval a -> DataType toConstr :: SetOrInterval a -> Constr $ctoConstr :: forall a. (Data a, Ord a) => SetOrInterval a -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SetOrInterval a) $cgunfold :: forall a (c :: * -> *). (Data a, Ord a) => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SetOrInterval a) gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a) $cgfoldl :: forall a (c :: * -> *). (Data a, Ord a) => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a) $cp1Data :: forall a. (Data a, Ord a) => Typeable (SetOrInterval a) Data) -- | A closed interval data ClosedInterval a = ClosedInterval a a deriving (ClosedInterval a -> ClosedInterval a -> Bool (ClosedInterval a -> ClosedInterval a -> Bool) -> (ClosedInterval a -> ClosedInterval a -> Bool) -> Eq (ClosedInterval a) forall a. Eq a => ClosedInterval a -> ClosedInterval a -> Bool forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: ClosedInterval a -> ClosedInterval a -> Bool $c/= :: forall a. Eq a => ClosedInterval a -> ClosedInterval a -> Bool == :: ClosedInterval a -> ClosedInterval a -> Bool $c== :: forall a. Eq a => ClosedInterval a -> ClosedInterval a -> Bool Eq, Eq (ClosedInterval a) Eq (ClosedInterval a) => (ClosedInterval a -> ClosedInterval a -> Ordering) -> (ClosedInterval a -> ClosedInterval a -> Bool) -> (ClosedInterval a -> ClosedInterval a -> Bool) -> (ClosedInterval a -> ClosedInterval a -> Bool) -> (ClosedInterval a -> ClosedInterval a -> Bool) -> (ClosedInterval a -> ClosedInterval a -> ClosedInterval a) -> (ClosedInterval a -> ClosedInterval a -> ClosedInterval a) -> Ord (ClosedInterval a) ClosedInterval a -> ClosedInterval a -> Bool ClosedInterval a -> ClosedInterval a -> Ordering ClosedInterval a -> ClosedInterval a -> ClosedInterval a forall a. Eq a => (a -> a -> Ordering) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> a) -> (a -> a -> a) -> Ord a forall a. Ord a => Eq (ClosedInterval a) forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Ordering forall a. Ord a => ClosedInterval a -> ClosedInterval a -> ClosedInterval a min :: ClosedInterval a -> ClosedInterval a -> ClosedInterval a $cmin :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> ClosedInterval a max :: ClosedInterval a -> ClosedInterval a -> ClosedInterval a $cmax :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> ClosedInterval a >= :: ClosedInterval a -> ClosedInterval a -> Bool $c>= :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool > :: ClosedInterval a -> ClosedInterval a -> Bool $c> :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool <= :: ClosedInterval a -> ClosedInterval a -> Bool $c<= :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool < :: ClosedInterval a -> ClosedInterval a -> Bool $c< :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Bool compare :: ClosedInterval a -> ClosedInterval a -> Ordering $ccompare :: forall a. Ord a => ClosedInterval a -> ClosedInterval a -> Ordering $cp1Ord :: forall a. Ord a => Eq (ClosedInterval a) Ord, Int -> ClosedInterval a -> ShowS [ClosedInterval a] -> ShowS ClosedInterval a -> String (Int -> ClosedInterval a -> ShowS) -> (ClosedInterval a -> String) -> ([ClosedInterval a] -> ShowS) -> Show (ClosedInterval a) forall a. Show a => Int -> ClosedInterval a -> ShowS forall a. Show a => [ClosedInterval a] -> ShowS forall a. Show a => ClosedInterval a -> String forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [ClosedInterval a] -> ShowS $cshowList :: forall a. Show a => [ClosedInterval a] -> ShowS show :: ClosedInterval a -> String $cshow :: forall a. Show a => ClosedInterval a -> String showsPrec :: Int -> ClosedInterval a -> ShowS $cshowsPrec :: forall a. Show a => Int -> ClosedInterval a -> ShowS Show, Typeable, Typeable (ClosedInterval a) Constr DataType Typeable (ClosedInterval a) => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a)) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (ClosedInterval a)) -> (ClosedInterval a -> Constr) -> (ClosedInterval a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a))) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (ClosedInterval a))) -> ((forall b. Data b => b -> b) -> ClosedInterval a -> ClosedInterval a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r) -> (forall u. (forall d. Data d => d -> u) -> ClosedInterval a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a)) -> Data (ClosedInterval a) ClosedInterval a -> Constr ClosedInterval a -> DataType (forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a)) (forall b. Data b => b -> b) -> ClosedInterval a -> ClosedInterval a (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a) (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (ClosedInterval a) forall a. Data a => Typeable (ClosedInterval a) forall a. Data a => ClosedInterval a -> Constr forall a. Data a => ClosedInterval a -> DataType forall a. Data a => (forall b. Data b => b -> b) -> ClosedInterval a -> ClosedInterval a forall a u. Data a => Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u forall a u. Data a => (forall d. Data d => d -> u) -> ClosedInterval a -> [u] forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (ClosedInterval a) forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a) forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a)) forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (ClosedInterval a)) forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u forall u. (forall d. Data d => d -> u) -> ClosedInterval a -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (ClosedInterval a) forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a) forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a)) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (ClosedInterval a)) $cClosedInterval :: Constr $tClosedInterval :: DataType gmapMo :: (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) $cgmapMo :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) gmapMp :: (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) $cgmapMp :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) gmapM :: (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) $cgmapM :: forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a) gmapQi :: Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u $cgmapQi :: forall a u. Data a => Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u gmapQ :: (forall d. Data d => d -> u) -> ClosedInterval a -> [u] $cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> ClosedInterval a -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r $cgmapQr :: forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r $cgmapQl :: forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r gmapT :: (forall b. Data b => b -> b) -> ClosedInterval a -> ClosedInterval a $cgmapT :: forall a. Data a => (forall b. Data b => b -> b) -> ClosedInterval a -> ClosedInterval a dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (ClosedInterval a)) $cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (ClosedInterval a)) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a)) $cdataCast1 :: forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a)) dataTypeOf :: ClosedInterval a -> DataType $cdataTypeOf :: forall a. Data a => ClosedInterval a -> DataType toConstr :: ClosedInterval a -> Constr $ctoConstr :: forall a. Data a => ClosedInterval a -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (ClosedInterval a) $cgunfold :: forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (ClosedInterval a) gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a) $cgfoldl :: forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a) $cp1Data :: forall a. Data a => Typeable (ClosedInterval a) Data) -- | Infinite integers = integers augmented by -Infty and +Infty data InfInt = PosInf | NegInf | FinInt Integer deriving (Int -> InfInt -> ShowS [InfInt] -> ShowS InfInt -> String (Int -> InfInt -> ShowS) -> (InfInt -> String) -> ([InfInt] -> ShowS) -> Show InfInt forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [InfInt] -> ShowS $cshowList :: [InfInt] -> ShowS show :: InfInt -> String $cshow :: InfInt -> String showsPrec :: Int -> InfInt -> ShowS $cshowsPrec :: Int -> InfInt -> ShowS Show, InfInt -> InfInt -> Bool (InfInt -> InfInt -> Bool) -> (InfInt -> InfInt -> Bool) -> Eq InfInt forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: InfInt -> InfInt -> Bool $c/= :: InfInt -> InfInt -> Bool == :: InfInt -> InfInt -> Bool $c== :: InfInt -> InfInt -> Bool Eq, Typeable, Typeable InfInt Constr DataType Typeable InfInt => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfInt -> c InfInt) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfInt) -> (InfInt -> Constr) -> (InfInt -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c InfInt)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfInt)) -> ((forall b. Data b => b -> b) -> InfInt -> InfInt) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r) -> (forall u. (forall d. Data d => d -> u) -> InfInt -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> InfInt -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt) -> Data InfInt InfInt -> Constr InfInt -> DataType (forall b. Data b => b -> b) -> InfInt -> InfInt (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfInt -> c InfInt (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfInt forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> InfInt -> u forall u. (forall d. Data d => d -> u) -> InfInt -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfInt forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfInt -> c InfInt forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c InfInt) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfInt) $cFinInt :: Constr $cNegInf :: Constr $cPosInf :: Constr $tInfInt :: DataType gmapMo :: (forall d. Data d => d -> m d) -> InfInt -> m InfInt $cgmapMo :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt gmapMp :: (forall d. Data d => d -> m d) -> InfInt -> m InfInt $cgmapMp :: forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt gmapM :: (forall d. Data d => d -> m d) -> InfInt -> m InfInt $cgmapM :: forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt gmapQi :: Int -> (forall d. Data d => d -> u) -> InfInt -> u $cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> InfInt -> u gmapQ :: (forall d. Data d => d -> u) -> InfInt -> [u] $cgmapQ :: forall u. (forall d. Data d => d -> u) -> InfInt -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r $cgmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r $cgmapQl :: forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r gmapT :: (forall b. Data b => b -> b) -> InfInt -> InfInt $cgmapT :: (forall b. Data b => b -> b) -> InfInt -> InfInt dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfInt) $cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfInt) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c InfInt) $cdataCast1 :: forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c InfInt) dataTypeOf :: InfInt -> DataType $cdataTypeOf :: InfInt -> DataType toConstr :: InfInt -> Constr $ctoConstr :: InfInt -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfInt $cgunfold :: forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfInt gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfInt -> c InfInt $cgfoldl :: forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfInt -> c InfInt $cp1Data :: Typeable InfInt Data) instance Ord InfInt where compare :: InfInt -> InfInt -> Ordering compare x :: InfInt x y :: InfInt y | InfInt x InfInt -> InfInt -> Bool forall a. Eq a => a -> a -> Bool == InfInt y = Ordering EQ | Bool otherwise = case (InfInt x, InfInt y) of (NegInf, _) -> Ordering LT (PosInf, _) -> Ordering GT (FinInt a :: Integer a, FinInt b :: Integer b) -> Integer -> Integer -> Ordering forall a. Ord a => a -> a -> Ordering compare Integer a Integer b _ -> Ordering -> Ordering swapCompare (Ordering -> Ordering) -> Ordering -> Ordering forall a b. (a -> b) -> a -> b $ InfInt -> InfInt -> Ordering forall a. Ord a => a -> a -> Ordering compare InfInt y InfInt x class Continuous a class Discrete a where nextA :: a -> a prevA :: a -> a intsizeA :: a -> a -> Maybe Integer instance Discrete InfInt where nextA :: InfInt -> InfInt nextA (FinInt a :: Integer a) = Integer -> InfInt FinInt (Integer -> InfInt) -> Integer -> InfInt forall a b. (a -> b) -> a -> b $ Integer a Integer -> Integer -> Integer forall a. Num a => a -> a -> a + 1 nextA x :: InfInt x = InfInt x prevA :: InfInt -> InfInt prevA (FinInt a :: Integer a) = Integer -> InfInt FinInt (Integer -> InfInt) -> Integer -> InfInt forall a b. (a -> b) -> a -> b $ Integer a Integer -> Integer -> Integer forall a. Num a => a -> a -> a - 1 prevA x :: InfInt x = InfInt x intsizeA :: InfInt -> InfInt -> Maybe Integer intsizeA (FinInt a :: Integer a) (FinInt b :: Integer b) = Integer -> Maybe Integer forall a. a -> Maybe a Just (Integer -> Maybe Integer) -> Integer -> Maybe Integer forall a b. (a -> b) -> a -> b $ (1 Integer -> Integer -> Integer forall a. Num a => a -> a -> a +) (Integer -> Integer) -> Integer -> Integer forall a b. (a -> b) -> a -> b $ Integer -> Integer forall a. Num a => a -> a abs (Integer -> Integer) -> Integer -> Integer forall a b. (a -> b) -> a -> b $ Integer b Integer -> Integer -> Integer forall a. Num a => a -> a -> a - Integer a intsizeA _ _ = Maybe Integer forall a. Maybe a Nothing {- ---------------------------------------------------------------------- Comparison facility for sets ---------------------------------------------------------------------- -} {- | Compares closed intervals [l1, r1] and [l2, r2]. Assumes non-singular intervals, i.e., l1 < r1 and l2 < r2. Works only for linearly ordered types. -} cmpClosedInts :: Ord a => ClosedInterval a -- ^ [l1, r1] -> ClosedInterval a -- ^ [l2, r2] -> SetOrdering cmpClosedInts :: ClosedInterval a -> ClosedInterval a -> SetOrdering cmpClosedInts (ClosedInterval l1 :: a l1 r1 :: a r1) (ClosedInterval l2 :: a l2 r2 :: a r2) | a l1 a -> a -> Bool forall a. Eq a => a -> a -> Bool == a l2 Bool -> Bool -> Bool && a r1 a -> a -> Bool forall a. Eq a => a -> a -> Bool == a r2 = Ordering -> SetOrdering Comparable Ordering EQ | a l1 a -> a -> Bool forall a. Ord a => a -> a -> Bool <= a l2 Bool -> Bool -> Bool && a r1 a -> a -> Bool forall a. Ord a => a -> a -> Bool >= a r2 = Ordering -> SetOrdering Comparable Ordering GT | a l1 a -> a -> Bool forall a. Ord a => a -> a -> Bool >= a l2 Bool -> Bool -> Bool && a r1 a -> a -> Bool forall a. Ord a => a -> a -> Bool <= a r2 = Ordering -> SetOrdering Comparable Ordering LT | a r1 a -> a -> Bool forall a. Ord a => a -> a -> Bool < a l2 Bool -> Bool -> Bool || a r2 a -> a -> Bool forall a. Ord a => a -> a -> Bool < a l1 = Incomparable -> SetOrdering Incomparable Incomparable Disjoint | Bool otherwise = Incomparable -> SetOrdering Incomparable Incomparable Overlap {- ---------------------------------------------------------------------- Comparison for discrete types ---------------------------------------------------------------------- -} -- | Membership in 'SetOrInterval' membSoID :: (Discrete a, Ord a) => a -> SetOrInterval a -> Bool membSoID :: a -> SetOrInterval a -> Bool membSoID x :: a x (Set s :: Set a s) = a -> Set a -> Bool forall a. Ord a => a -> Set a -> Bool Set.member a x Set a s membSoID x :: a x i :: SetOrInterval a i = let ClosedInterval a :: a a b :: a b = SetOrInterval a -> ClosedInterval a forall a. (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a setToClosedIntD SetOrInterval a i in a x a -> a -> Bool forall a. Ord a => a -> a -> Bool >= a a Bool -> Bool -> Bool && a x a -> a -> Bool forall a. Ord a => a -> a -> Bool <= a b -- | Checks if the set is empty. nullSoID :: (Discrete a, Ord a) => SetOrInterval a -> Bool nullSoID :: SetOrInterval a -> Bool nullSoID (Set s :: Set a s) = Set a -> Bool forall a. Set a -> Bool Set.null Set a s nullSoID i :: SetOrInterval a i = let ClosedInterval a :: a a b :: a b = SetOrInterval a -> ClosedInterval a forall a. (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a setToClosedIntD SetOrInterval a i in a a a -> a -> Bool forall a. Ord a => a -> a -> Bool > a b {- | If the set is singular, i.e., consists only from one point, then we return this point. Reports error on empty SoI's. -} toSingularD :: (Discrete a, Ord a) => SetOrInterval a -> Maybe a toSingularD :: SetOrInterval a -> Maybe a toSingularD d :: SetOrInterval a d | SetOrInterval a -> Bool forall a. (Discrete a, Ord a) => SetOrInterval a -> Bool nullSoID SetOrInterval a d = String -> Maybe a forall a. HasCallStack => String -> a error "toSingularD: empty set" | Bool otherwise = case SetOrInterval a d of Set s :: Set a s | Set a -> Int forall a. Set a -> Int Set.size Set a s Int -> Int -> Bool forall a. Eq a => a -> a -> Bool == 1 -> a -> Maybe a forall a. a -> Maybe a Just (a -> Maybe a) -> a -> Maybe a forall a b. (a -> b) -> a -> b $ Set a -> a forall a. Set a -> a Set.findMin Set a s | Bool otherwise -> Maybe a forall a. Maybe a Nothing _ -> let ClosedInterval a :: a a b :: a b = SetOrInterval a -> ClosedInterval a forall a. (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a setToClosedIntD SetOrInterval a d in if a a a -> a -> Bool forall a. Eq a => a -> a -> Bool == a b then a -> Maybe a forall a. a -> Maybe a Just a a else Maybe a forall a. Maybe a Nothing -- | Transforms a 'SetOrInterval' to a closed representation setToClosedIntD :: (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a setToClosedIntD :: SetOrInterval a -> ClosedInterval a setToClosedIntD (Set s :: Set a s) = a -> a -> ClosedInterval a forall a. a -> a -> ClosedInterval a ClosedInterval (Set a -> a forall a. Set a -> a Set.findMin Set a s) (a -> ClosedInterval a) -> a -> ClosedInterval a forall a b. (a -> b) -> a -> b $ Set a -> a forall a. Set a -> a Set.findMax Set a s setToClosedIntD (IntVal (l :: a l, bL :: Bool bL) (r :: a r, bR :: Bool bR)) = a -> a -> ClosedInterval a forall a. a -> a -> ClosedInterval a ClosedInterval (if Bool bL then a l else a -> a forall a. Discrete a => a -> a nextA a l) (a -> ClosedInterval a) -> a -> ClosedInterval a forall a b. (a -> b) -> a -> b $ if Bool bR then a r else a -> a forall a. Discrete a => a -> a prevA a r -- | Compare sets over discrete types cmpSoIsD :: (Discrete a, Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsD :: SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsD d1 :: SetOrInterval a d1 d2 :: SetOrInterval a d2 = case (SetOrInterval a -> Maybe a forall a. (Discrete a, Ord a) => SetOrInterval a -> Maybe a toSingularD SetOrInterval a d1, SetOrInterval a -> Maybe a forall a. (Discrete a, Ord a) => SetOrInterval a -> Maybe a toSingularD SetOrInterval a d2) of (Just x1 :: a x1, Just x2 :: a x2) | a x1 a -> a -> Bool forall a. Eq a => a -> a -> Bool == a x2 -> Ordering -> SetOrdering Comparable Ordering EQ | Bool otherwise -> Incomparable -> SetOrdering Incomparable Incomparable Disjoint (Just x :: a x, _) | a -> SetOrInterval a -> Bool forall a. (Discrete a, Ord a) => a -> SetOrInterval a -> Bool membSoID a x SetOrInterval a d2 -> Ordering -> SetOrdering Comparable Ordering LT | Bool otherwise -> Incomparable -> SetOrdering Incomparable Incomparable Disjoint (_, Just x :: a x) | a -> SetOrInterval a -> Bool forall a. (Discrete a, Ord a) => a -> SetOrInterval a -> Bool membSoID a x SetOrInterval a d1 -> Ordering -> SetOrdering Comparable Ordering GT | Bool otherwise -> Incomparable -> SetOrdering Incomparable Incomparable Disjoint _ -> SetOrInterval a -> SetOrInterval a -> SetOrdering forall a. (Discrete a, Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsExD SetOrInterval a d1 SetOrInterval a d2 -- singular cases are dispelled here {- | Compare sets helper function which only works on regular (non-singular) sets -} cmpSoIsExD :: (Discrete a, Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsExD :: SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsExD i1 :: SetOrInterval a i1@(IntVal _ _) i2 :: SetOrInterval a i2@(IntVal _ _) = ClosedInterval a -> ClosedInterval a -> SetOrdering forall a. Ord a => ClosedInterval a -> ClosedInterval a -> SetOrdering cmpClosedInts (SetOrInterval a -> ClosedInterval a forall a. (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a setToClosedIntD SetOrInterval a i1) (ClosedInterval a -> SetOrdering) -> ClosedInterval a -> SetOrdering forall a b. (a -> b) -> a -> b $ SetOrInterval a -> ClosedInterval a forall a. (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a setToClosedIntD SetOrInterval a i2 cmpSoIsExD s1 :: SetOrInterval a s1@(Set _) s2 :: SetOrInterval a s2@(Set _) = SetOrInterval a -> SetOrInterval a -> SetOrdering forall a. Ord a => SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsEx SetOrInterval a s1 SetOrInterval a s2 cmpSoIsExD i1 :: SetOrInterval a i1@(IntVal _ _) s2 :: SetOrInterval a s2@(Set s :: Set a s) = let ci2 :: ClosedInterval a ci2@(ClosedInterval a2 :: a a2 b2 :: a b2) = SetOrInterval a -> ClosedInterval a forall a. (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a setToClosedIntD SetOrInterval a s2 in case ClosedInterval a -> ClosedInterval a -> SetOrdering forall a. Ord a => ClosedInterval a -> ClosedInterval a -> SetOrdering cmpClosedInts (SetOrInterval a -> ClosedInterval a forall a. (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a setToClosedIntD SetOrInterval a i1) ClosedInterval a ci2 of Comparable EQ -> case a -> a -> Maybe Integer forall a. Discrete a => a -> a -> Maybe Integer intsizeA a a2 a b2 of Just dst :: Integer dst | Int -> Integer forall a b. (Integral a, Num b) => a -> b fromIntegral (Set a -> Int forall a. Set a -> Int Set.size Set a s) Integer -> Integer -> Bool forall a. Eq a => a -> a -> Bool == Integer dst -> Ordering -> SetOrdering Comparable Ordering EQ | Bool otherwise -> Ordering -> SetOrdering Comparable Ordering GT -- Nothing means infinite. This is a misuse! _ -> String -> SetOrdering forall a. HasCallStack => String -> a error "cmpSoIsExD: unbounded finite set!" Comparable LT -> Incomparable -> SetOrdering Incomparable (Incomparable -> SetOrdering) -> Incomparable -> SetOrdering forall a b. (a -> b) -> a -> b $ if (a -> Bool) -> [a] -> Bool forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool any (a -> SetOrInterval a -> Bool forall a. (Discrete a, Ord a) => a -> SetOrInterval a -> Bool `membSoID` SetOrInterval a i1) ([a] -> Bool) -> [a] -> Bool forall a b. (a -> b) -> a -> b $ Set a -> [a] forall a. Set a -> [a] Set.toList Set a s then Incomparable Overlap else Incomparable Disjoint so :: SetOrdering so -> SetOrdering so cmpSoIsExD s1 :: SetOrInterval a s1 i2 :: SetOrInterval a i2 = SetOrdering -> SetOrdering swapCmp (SetOrdering -> SetOrdering) -> SetOrdering -> SetOrdering forall a b. (a -> b) -> a -> b $ SetOrInterval a -> SetOrInterval a -> SetOrdering forall a. (Discrete a, Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsExD SetOrInterval a i2 SetOrInterval a s1 {- ---------------------------------------------------------------------- Comparison for continuous types ---------------------------------------------------------------------- -} -- | Membership in 'SetOrInterval' membSoI :: Ord a => a -> SetOrInterval a -> Bool membSoI :: a -> SetOrInterval a -> Bool membSoI x :: a x (Set s :: Set a s) = a -> Set a -> Bool forall a. Ord a => a -> Set a -> Bool Set.member a x Set a s membSoI x :: a x i :: SetOrInterval a i = let ClosedInterval a :: CIType a a b :: CIType a b = SetOrInterval a -> ClosedInterval (CIType a) forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a) setToClosedInt SetOrInterval a i x' :: CIType a x' = (a, InfDev) -> CIType a forall a. (a, InfDev) -> CIType a CIType (a x, InfDev Zero) in CIType a x' CIType a -> CIType a -> Bool forall a. Ord a => a -> a -> Bool >= CIType a a Bool -> Bool -> Bool && CIType a x' CIType a -> CIType a -> Bool forall a. Ord a => a -> a -> Bool <= CIType a b {- | Checks if the set is empty. Only for continuous types. -} nullSoI :: (Continuous a, Ord a) => SetOrInterval a -> Bool nullSoI :: SetOrInterval a -> Bool nullSoI (Set s :: Set a s) = Set a -> Bool forall a. Set a -> Bool Set.null Set a s nullSoI (IntVal (a :: a a, bA :: Bool bA) (b :: a b, bB :: Bool bB)) = a a a -> a -> Bool forall a. Eq a => a -> a -> Bool == a b Bool -> Bool -> Bool && Bool -> Bool not (Bool bA Bool -> Bool -> Bool && Bool bB) {- | If the set is singular, i.e., consists only from one point, then we return this point. Reports error on empty SoI's. Only for continuous types. -} toSingular :: (Continuous a, Ord a) => SetOrInterval a -> Maybe a toSingular :: SetOrInterval a -> Maybe a toSingular d :: SetOrInterval a d | SetOrInterval a -> Bool forall a. (Continuous a, Ord a) => SetOrInterval a -> Bool nullSoI SetOrInterval a d = String -> Maybe a forall a. HasCallStack => String -> a error "toSingular: empty set" | Bool otherwise = case SetOrInterval a d of Set s :: Set a s | Set a -> Int forall a. Set a -> Int Set.size Set a s Int -> Int -> Bool forall a. Eq a => a -> a -> Bool == 1 -> a -> Maybe a forall a. a -> Maybe a Just (a -> Maybe a) -> a -> Maybe a forall a b. (a -> b) -> a -> b $ Set a -> a forall a. Set a -> a Set.findMin Set a s | Bool otherwise -> Maybe a forall a. Maybe a Nothing IntVal (a :: a a, _) (b :: a b, _) | a a a -> a -> Bool forall a. Eq a => a -> a -> Bool == a b -> a -> Maybe a forall a. a -> Maybe a Just a a | Bool otherwise -> Maybe a forall a. Maybe a Nothing {- | Transforms a 'SetOrInterval' to a closed representation Only for continuous types. -} setToClosedInt :: Ord a => SetOrInterval a -> ClosedInterval (CIType a) setToClosedInt :: SetOrInterval a -> ClosedInterval (CIType a) setToClosedInt (Set s :: Set a s) = CIType a -> CIType a -> ClosedInterval (CIType a) forall a. a -> a -> ClosedInterval a ClosedInterval ((a, InfDev) -> CIType a forall a. (a, InfDev) -> CIType a CIType (Set a -> a forall a. Set a -> a Set.findMin Set a s, InfDev Zero)) (CIType a -> ClosedInterval (CIType a)) -> CIType a -> ClosedInterval (CIType a) forall a b. (a -> b) -> a -> b $ (a, InfDev) -> CIType a forall a. (a, InfDev) -> CIType a CIType (Set a -> a forall a. Set a -> a Set.findMax Set a s, InfDev Zero) setToClosedInt (IntVal (l :: a l, bL :: Bool bL) (r :: a r, bR :: Bool bR)) = CIType a -> CIType a -> ClosedInterval (CIType a) forall a. a -> a -> ClosedInterval a ClosedInterval ((a, InfDev) -> CIType a forall a. (a, InfDev) -> CIType a CIType (a l, if Bool bL then InfDev Zero else InfDev EpsRight)) (CIType a -> ClosedInterval (CIType a)) -> CIType a -> ClosedInterval (CIType a) forall a b. (a -> b) -> a -> b $ (a, InfDev) -> CIType a forall a. (a, InfDev) -> CIType a CIType (a r, if Bool bR then InfDev Zero else InfDev EpsLeft) -- | Compare sets over continuous types cmpSoIs :: (Continuous a, Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIs :: SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIs d1 :: SetOrInterval a d1 d2 :: SetOrInterval a d2 = case (SetOrInterval a -> Maybe a forall a. (Continuous a, Ord a) => SetOrInterval a -> Maybe a toSingular SetOrInterval a d1, SetOrInterval a -> Maybe a forall a. (Continuous a, Ord a) => SetOrInterval a -> Maybe a toSingular SetOrInterval a d2) of (Just x1 :: a x1, Just x2 :: a x2) | a x1 a -> a -> Bool forall a. Eq a => a -> a -> Bool == a x2 -> Ordering -> SetOrdering Comparable Ordering EQ | Bool otherwise -> Incomparable -> SetOrdering Incomparable Incomparable Disjoint (Just x :: a x, _) | a -> SetOrInterval a -> Bool forall a. Ord a => a -> SetOrInterval a -> Bool membSoI a x SetOrInterval a d2 -> Ordering -> SetOrdering Comparable Ordering LT | Bool otherwise -> Incomparable -> SetOrdering Incomparable Incomparable Disjoint (_, Just x :: a x) | a -> SetOrInterval a -> Bool forall a. Ord a => a -> SetOrInterval a -> Bool membSoI a x SetOrInterval a d1 -> Ordering -> SetOrdering Comparable Ordering GT | Bool otherwise -> Incomparable -> SetOrdering Incomparable Incomparable Disjoint _ -> SetOrInterval a -> SetOrInterval a -> SetOrdering forall a. Ord a => SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsEx SetOrInterval a d1 SetOrInterval a d2 -- singular cases are dispelled here {- | Compare sets helper function which only works on regular (non-singular) sets -} cmpSoIsEx :: (Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsEx :: SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsEx (Set s1 :: Set a s1) (Set s2 :: Set a s2) | Set a s1 Set a -> Set a -> Bool forall a. Eq a => a -> a -> Bool == Set a s2 = Ordering -> SetOrdering Comparable Ordering EQ | Set a s1 Set a -> Set a -> Bool forall a. Ord a => Set a -> Set a -> Bool `Set.isSubsetOf` Set a s2 = Ordering -> SetOrdering Comparable Ordering LT | Set a s2 Set a -> Set a -> Bool forall a. Ord a => Set a -> Set a -> Bool `Set.isSubsetOf` Set a s1 = Ordering -> SetOrdering Comparable Ordering GT | Set a -> Bool forall a. Set a -> Bool Set.null (Set a -> Bool) -> Set a -> Bool forall a b. (a -> b) -> a -> b $ Set a -> Set a -> Set a forall a. Ord a => Set a -> Set a -> Set a Set.intersection Set a s1 Set a s2 = Incomparable -> SetOrdering Incomparable Incomparable Disjoint | Bool otherwise = Incomparable -> SetOrdering Incomparable Incomparable Overlap cmpSoIsEx i1 :: SetOrInterval a i1@(IntVal _ _) i2 :: SetOrInterval a i2@(IntVal _ _) = ClosedInterval (CIType a) -> ClosedInterval (CIType a) -> SetOrdering forall a. Ord a => ClosedInterval a -> ClosedInterval a -> SetOrdering cmpClosedInts (SetOrInterval a -> ClosedInterval (CIType a) forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a) setToClosedInt SetOrInterval a i1) (ClosedInterval (CIType a) -> SetOrdering) -> ClosedInterval (CIType a) -> SetOrdering forall a b. (a -> b) -> a -> b $ SetOrInterval a -> ClosedInterval (CIType a) forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a) setToClosedInt SetOrInterval a i2 cmpSoIsEx i1 :: SetOrInterval a i1@(IntVal _ _) s2 :: SetOrInterval a s2@(Set s :: Set a s) = case ClosedInterval (CIType a) -> ClosedInterval (CIType a) -> SetOrdering forall a. Ord a => ClosedInterval a -> ClosedInterval a -> SetOrdering cmpClosedInts (SetOrInterval a -> ClosedInterval (CIType a) forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a) setToClosedInt SetOrInterval a i1) (ClosedInterval (CIType a) -> SetOrdering) -> ClosedInterval (CIType a) -> SetOrdering forall a b. (a -> b) -> a -> b $ SetOrInterval a -> ClosedInterval (CIType a) forall a. Ord a => SetOrInterval a -> ClosedInterval (CIType a) setToClosedInt SetOrInterval a s2 of Comparable EQ -> Ordering -> SetOrdering Comparable Ordering GT Comparable LT -> Incomparable -> SetOrdering Incomparable (Incomparable -> SetOrdering) -> Incomparable -> SetOrdering forall a b. (a -> b) -> a -> b $ if (a -> Bool) -> [a] -> Bool forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool any (a -> SetOrInterval a -> Bool forall a. Ord a => a -> SetOrInterval a -> Bool `membSoI` SetOrInterval a i1) ([a] -> Bool) -> [a] -> Bool forall a b. (a -> b) -> a -> b $ Set a -> [a] forall a. Set a -> [a] Set.toList Set a s then Incomparable Overlap else Incomparable Disjoint so :: SetOrdering so -> SetOrdering so cmpSoIsEx s1 :: SetOrInterval a s1 i2 :: SetOrInterval a i2 = SetOrdering -> SetOrdering swapCmp (SetOrdering -> SetOrdering) -> SetOrdering -> SetOrdering forall a b. (a -> b) -> a -> b $ SetOrInterval a -> SetOrInterval a -> SetOrdering forall a. Ord a => SetOrInterval a -> SetOrInterval a -> SetOrdering cmpSoIsEx SetOrInterval a i2 SetOrInterval a s1 {- ---------------------------------------------------------------------- Combining comparison results ---------------------------------------------------------------------- -} swapCompare :: Ordering -> Ordering swapCompare :: Ordering -> Ordering swapCompare GT = Ordering LT swapCompare LT = Ordering GT swapCompare x :: Ordering x = Ordering x swapCmp :: SetOrdering -> SetOrdering swapCmp :: SetOrdering -> SetOrdering swapCmp (Comparable x :: Ordering x) = Ordering -> SetOrdering Comparable (Ordering -> SetOrdering) -> Ordering -> SetOrdering forall a b. (a -> b) -> a -> b $ Ordering -> Ordering swapCompare Ordering x swapCmp x :: SetOrdering x = SetOrdering x {- | We combine the comparison outcome of the individual parameters with the following (symmetrical => commutative) table: > \ | > < = O D > ------------- > > | > O > O D > < | < < O D > = | = O D > O | O D > D | D > > , where > > > | < | = | O | D > --------------------------------------------- > RightOf | LeftOf | Equal | Overlap | Disjoint The purpose of this table is to use it for cartesian products as follows Let A', A'' \subset A B', B'' \subset B In order to get the comparison result for A' x B' and A'' x B'' we compare A' and A'' as well as B' and B'' and combine the results with the above table. Note that for empty sets the comparable results <,>,= are preferred over the disjoint result. -} combineCmp :: SetOrdering -> SetOrdering -> SetOrdering combineCmp :: SetOrdering -> SetOrdering -> SetOrdering combineCmp x :: SetOrdering x y :: SetOrdering y | SetOrdering x SetOrdering -> SetOrdering -> Bool forall a. Eq a => a -> a -> Bool == SetOrdering y = SetOrdering x -- idempotence | Bool otherwise = case (SetOrdering x, SetOrdering y) of (_, Incomparable Disjoint) -> Incomparable -> SetOrdering Incomparable Incomparable Disjoint (Incomparable Overlap, _) -> Incomparable -> SetOrdering Incomparable Incomparable Overlap (Comparable EQ, _) -> SetOrdering y -- neutral element (Comparable GT, Comparable LT) -> Incomparable -> SetOrdering Incomparable Incomparable Overlap _ -> SetOrdering -> SetOrdering -> SetOrdering combineCmp SetOrdering y SetOrdering x -- commutative (should capture all cases)