Copyright  (c) Ewaryst Schulz, DFKI Bremen 2010 

License  GPLv2 or higher, see LICENSE.txt 
Maintainer  ewaryst.schulz@dfki.de 
Stability  experimental 
Portability  portable 
Safe Haskell  SafeInferred 
This module defines a basic datatype for treelike partial orderings such as encountered, e.g., in the set lattice.
 data Incomparable
 data SetOrdering
 data InfDev
 newtype CIType a = CIType (a, InfDev)
 data SetOrInterval a
 data ClosedInterval a = ClosedInterval a a
 data InfInt
 class Continuous a
 class Discrete a where
 cmpClosedInts :: Ord a => ClosedInterval a > ClosedInterval a > SetOrdering
 membSoID :: (Discrete a, Ord a) => a > SetOrInterval a > Bool
 nullSoID :: (Discrete a, Ord a) => SetOrInterval a > Bool
 toSingularD :: (Discrete a, Ord a) => SetOrInterval a > Maybe a
 setToClosedIntD :: (Discrete a, Ord a) => SetOrInterval a > ClosedInterval a
 cmpSoIsD :: (Discrete a, Ord a) => SetOrInterval a > SetOrInterval a > SetOrdering
 cmpSoIsExD :: (Discrete a, Ord a) => SetOrInterval a > SetOrInterval a > SetOrdering
 membSoI :: Ord a => a > SetOrInterval a > Bool
 nullSoI :: (Continuous a, Ord a) => SetOrInterval a > Bool
 toSingular :: (Continuous a, Ord a) => SetOrInterval a > Maybe a
 setToClosedInt :: Ord a => SetOrInterval a > ClosedInterval (CIType a)
 cmpSoIs :: (Continuous a, Ord a) => SetOrInterval a > SetOrInterval a > SetOrdering
 cmpSoIsEx :: Ord a => SetOrInterval a > SetOrInterval a > SetOrdering
 swapCompare :: Ordering > Ordering
 swapCmp :: SetOrdering > SetOrdering
 combineCmp :: SetOrdering > SetOrdering > SetOrdering
Documentation
data Incomparable
data SetOrdering
data InfDev
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)'.
newtype CIType a
data SetOrInterval a
A finite set or an interval. True = closed, False = opened interval border.
Eq a => Eq (SetOrInterval a)  
(Data a, Ord a) => Data (SetOrInterval a)  
Ord a => Ord (SetOrInterval a)  
Show a => Show (SetOrInterval a)  
(Ord a, ShATermConvertible a) => ShATermConvertible (SetOrInterval a)  
(Ord a, Pretty a) => Pretty (SetOrInterval a)  
Typeable (* > *) SetOrInterval 
data ClosedInterval a
A closed interval
ClosedInterval a a 
Eq a => Eq (ClosedInterval a)  
Data a => Data (ClosedInterval a)  
Ord a => Ord (ClosedInterval a)  
Show a => Show (ClosedInterval a)  
ShATermConvertible a => ShATermConvertible (ClosedInterval a)  
Pretty a => Pretty (ClosedInterval a)  
Typeable (* > *) ClosedInterval 
data InfInt
Infinite integers = integers augmented by Infty and +Infty
class Continuous a
class Discrete a where
:: Ord a  
=> ClosedInterval a 

> ClosedInterval a 

> SetOrdering 
Compares closed intervals [l1, r1] and [l2, r2]. Assumes nonsingular intervals, i.e., l1 < r1 and l2 < r2. Works only for linearly ordered types.
membSoID :: (Discrete a, Ord a) => a > SetOrInterval a > Bool
Membership in SetOrInterval
nullSoID :: (Discrete a, Ord a) => SetOrInterval a > Bool
Checks if the set is empty.
toSingularD :: (Discrete a, Ord a) => SetOrInterval a > Maybe a
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
Transforms a SetOrInterval
to a closed representation
cmpSoIsD :: (Discrete a, Ord a) => SetOrInterval a > SetOrInterval a > SetOrdering
Compare sets over discrete types
cmpSoIsExD :: (Discrete a, Ord a) => SetOrInterval a > SetOrInterval a > SetOrdering
Compare sets helper function which only works on regular (nonsingular) sets
membSoI :: Ord a => a > SetOrInterval a > Bool
Membership in SetOrInterval
nullSoI :: (Continuous a, Ord a) => SetOrInterval a > Bool
Checks if the set is empty. Only for continuous types.
toSingular :: (Continuous a, Ord a) => SetOrInterval a > Maybe a
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)
Transforms a SetOrInterval
to a closed representation
Only for continuous types.
cmpSoIs :: (Continuous a, Ord a) => SetOrInterval a > SetOrInterval a > SetOrdering
Compare sets over continuous types
cmpSoIsEx :: Ord a => SetOrInterval a > SetOrInterval a > SetOrdering
Compare sets helper function which only works on regular (nonsingular) sets
swapCompare :: Ordering > Ordering
swapCmp :: SetOrdering > SetOrdering
combineCmp :: SetOrdering > SetOrdering > SetOrdering
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.