Hets - the Heterogeneous Tool Set

Copyright(c) Ewaryst Schulz DFKI Bremen 2010
LicenseGPLv2 or higher, see LICENSE.txt
Maintainerewaryst.schulz@dfki.de
Stabilityexperimental
Portabilityportable
Safe HaskellSafe

CSL.TreePO

Description

This module defines a basic datatype for tree-like partial orderings such as encountered, e.g., in the set lattice.

Synopsis

Documentation

data Incomparable Source #

Constructors

Disjoint 
Overlap 

Instances

Eq Incomparable Source # 

Methods

(==) :: Incomparable -> Incomparable -> Bool

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

Data Incomparable Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Incomparable -> c Incomparable

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c Incomparable

toConstr :: Incomparable -> Constr

dataTypeOf :: Incomparable -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c Incomparable)

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c Incomparable)

gmapT :: (forall b. Data b => b -> b) -> Incomparable -> Incomparable

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Incomparable -> r

gmapQ :: (forall d. Data d => d -> u) -> Incomparable -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> Incomparable -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Incomparable -> m Incomparable

Show Incomparable Source # 

Methods

showsPrec :: Int -> Incomparable -> ShowS

show :: Incomparable -> String

showList :: [Incomparable] -> ShowS

data SetOrdering Source #

Constructors

Comparable Ordering 
Incomparable Incomparable 

Instances

Eq SetOrdering Source # 

Methods

(==) :: SetOrdering -> SetOrdering -> Bool

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

Data SetOrdering Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrdering -> c SetOrdering

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c SetOrdering

toConstr :: SetOrdering -> Constr

dataTypeOf :: SetOrdering -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c SetOrdering)

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c SetOrdering)

gmapT :: (forall b. Data b => b -> b) -> SetOrdering -> SetOrdering

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrdering -> r

gmapQ :: (forall d. Data d => d -> u) -> SetOrdering -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> SetOrdering -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SetOrdering -> m SetOrdering

Show SetOrdering Source # 

Methods

showsPrec :: Int -> SetOrdering -> ShowS

show :: SetOrdering -> String

showList :: [SetOrdering] -> ShowS

data InfDev Source #

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)'.

Constructors

EpsLeft 
Zero 
EpsRight 

Instances

Eq InfDev Source # 

Methods

(==) :: InfDev -> InfDev -> Bool

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

Data InfDev Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfDev -> c InfDev

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfDev

toConstr :: InfDev -> Constr

dataTypeOf :: InfDev -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c InfDev)

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfDev)

gmapT :: (forall b. Data b => b -> b) -> InfDev -> InfDev

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfDev -> r

gmapQ :: (forall d. Data d => d -> u) -> InfDev -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> InfDev -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> InfDev -> m InfDev

Ord InfDev Source # 

Methods

compare :: InfDev -> InfDev -> Ordering

(<) :: InfDev -> InfDev -> Bool

(<=) :: InfDev -> InfDev -> Bool

(>) :: InfDev -> InfDev -> Bool

(>=) :: InfDev -> InfDev -> Bool

max :: InfDev -> InfDev -> InfDev

min :: InfDev -> InfDev -> InfDev

Show InfDev Source # 

Methods

showsPrec :: Int -> InfDev -> ShowS

show :: InfDev -> String

showList :: [InfDev] -> ShowS

newtype CIType a Source #

Constructors

CIType (a, InfDev) 

Instances

Eq a => Eq (CIType a) Source # 

Methods

(==) :: CIType a -> CIType a -> Bool

(/=) :: CIType a -> CIType a -> Bool

Data a => Data (CIType a) Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> CIType a -> c (CIType a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (CIType a)

toConstr :: CIType a -> Constr

dataTypeOf :: CIType a -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c (CIType a))

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (CIType a))

gmapT :: (forall b. Data b => b -> b) -> CIType a -> CIType a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> CIType a -> r

gmapQ :: (forall d. Data d => d -> u) -> CIType a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> CIType a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> CIType a -> m (CIType a)

Ord a => Ord (CIType a) Source #

This type with the given ordering is to represent opened/closed intervals over a as closed intervals over '(a, InfDev)'

Methods

compare :: CIType a -> CIType a -> Ordering

(<) :: CIType a -> CIType a -> Bool

(<=) :: CIType a -> CIType a -> Bool

(>) :: CIType a -> CIType a -> Bool

(>=) :: CIType a -> CIType a -> Bool

max :: CIType a -> CIType a -> CIType a

min :: CIType a -> CIType a -> CIType a

Show a => Show (CIType a) Source # 

Methods

showsPrec :: Int -> CIType a -> ShowS

show :: CIType a -> String

showList :: [CIType a] -> ShowS

data SetOrInterval a Source #

A finite set or an interval. True = closed, False = opened interval border.

Constructors

Set (Set a) 
IntVal (a, Bool) (a, Bool) 

Instances

Eq a => Eq (SetOrInterval a) Source # 

Methods

(==) :: SetOrInterval a -> SetOrInterval a -> Bool

(/=) :: SetOrInterval a -> SetOrInterval a -> Bool

(Ord a, Data a) => Data (SetOrInterval a) Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SetOrInterval a -> c (SetOrInterval a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SetOrInterval a)

toConstr :: SetOrInterval a -> Constr

dataTypeOf :: SetOrInterval a -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c (SetOrInterval a))

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SetOrInterval a))

gmapT :: (forall b. Data b => b -> b) -> SetOrInterval a -> SetOrInterval a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SetOrInterval a -> r

gmapQ :: (forall d. Data d => d -> u) -> SetOrInterval a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> SetOrInterval a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SetOrInterval a -> m (SetOrInterval a)

Ord a => Ord (SetOrInterval a) Source # 
Show a => Show (SetOrInterval a) Source # 

Methods

showsPrec :: Int -> SetOrInterval a -> ShowS

show :: SetOrInterval a -> String

showList :: [SetOrInterval a] -> ShowS

data ClosedInterval a Source #

A closed interval

Constructors

ClosedInterval a a 

Instances

Eq a => Eq (ClosedInterval a) Source # 

Methods

(==) :: ClosedInterval a -> ClosedInterval a -> Bool

(/=) :: ClosedInterval a -> ClosedInterval a -> Bool

Data a => Data (ClosedInterval a) Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ClosedInterval a -> c (ClosedInterval a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (ClosedInterval a)

toConstr :: ClosedInterval a -> Constr

dataTypeOf :: ClosedInterval a -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c (ClosedInterval a))

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (ClosedInterval a))

gmapT :: (forall b. Data b => b -> b) -> ClosedInterval a -> ClosedInterval a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ClosedInterval a -> r

gmapQ :: (forall d. Data d => d -> u) -> ClosedInterval a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> ClosedInterval a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> ClosedInterval a -> m (ClosedInterval a)

Ord a => Ord (ClosedInterval a) Source # 
Show a => Show (ClosedInterval a) Source # 

Methods

showsPrec :: Int -> ClosedInterval a -> ShowS

show :: ClosedInterval a -> String

showList :: [ClosedInterval a] -> ShowS

data InfInt Source #

Infinite integers = integers augmented by -Infty and +Infty

Constructors

PosInf 
NegInf 
FinInt Integer 

Instances

Eq InfInt Source # 

Methods

(==) :: InfInt -> InfInt -> Bool

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

Data InfInt Source # 

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InfInt -> c InfInt

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InfInt

toConstr :: InfInt -> Constr

dataTypeOf :: InfInt -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c InfInt)

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InfInt)

gmapT :: (forall b. Data b => b -> b) -> InfInt -> InfInt

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InfInt -> r

gmapQ :: (forall d. Data d => d -> u) -> InfInt -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> InfInt -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> InfInt -> m InfInt

Ord InfInt Source # 

Methods

compare :: InfInt -> InfInt -> Ordering

(<) :: InfInt -> InfInt -> Bool

(<=) :: InfInt -> InfInt -> Bool

(>) :: InfInt -> InfInt -> Bool

(>=) :: InfInt -> InfInt -> Bool

max :: InfInt -> InfInt -> InfInt

min :: InfInt -> InfInt -> InfInt

Show InfInt Source # 

Methods

showsPrec :: Int -> InfInt -> ShowS

show :: InfInt -> String

showList :: [InfInt] -> ShowS

Discrete InfInt Source # 

Methods

nextA :: InfInt -> InfInt Source #

prevA :: InfInt -> InfInt Source #

intsizeA :: InfInt -> InfInt -> Maybe Integer Source #

class Discrete a where Source #

Minimal complete definition

nextA, prevA, intsizeA

Methods

nextA :: a -> a Source #

prevA :: a -> a Source #

intsizeA :: a -> a -> Maybe Integer Source #

Instances

cmpClosedInts Source #

Arguments

:: Ord a 
=> ClosedInterval a
l1, r1
-> ClosedInterval a
l2, r2
-> SetOrdering 

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.

membSoID :: (Discrete a, Ord a) => a -> SetOrInterval a -> Bool Source #

Membership in SetOrInterval

nullSoID :: (Discrete a, Ord a) => SetOrInterval a -> Bool Source #

Checks if the set is empty.

toSingularD :: (Discrete a, Ord a) => SetOrInterval a -> Maybe a Source #

If the set is singular, i.e., consists only from one point, then we return this point. Reports error on empty SoI's.

setToClosedIntD :: (Discrete a, Ord a) => SetOrInterval a -> ClosedInterval a Source #

Transforms a SetOrInterval to a closed representation

cmpSoIsD :: (Discrete a, Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering Source #

Compare sets over discrete types

cmpSoIsExD :: (Discrete a, Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering Source #

Compare sets helper function which only works on regular (non-singular) sets

membSoI :: Ord a => a -> SetOrInterval a -> Bool Source #

Membership in SetOrInterval

nullSoI :: (Continuous a, Ord a) => SetOrInterval a -> Bool Source #

Checks if the set is empty. Only for continuous types.

toSingular :: (Continuous a, Ord a) => SetOrInterval a -> Maybe a Source #

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.

setToClosedInt :: Ord a => SetOrInterval a -> ClosedInterval (CIType a) Source #

Transforms a SetOrInterval to a closed representation Only for continuous types.

cmpSoIs :: (Continuous a, Ord a) => SetOrInterval a -> SetOrInterval a -> SetOrdering Source #

Compare sets over continuous types

cmpSoIsEx :: Ord a => SetOrInterval a -> SetOrInterval a -> SetOrdering Source #

Compare sets helper function which only works on regular (non-singular) sets

swapCompare :: Ordering -> Ordering Source #

combineCmp :: SetOrdering -> SetOrdering -> SetOrdering Source #

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.