Copyright	(c) David Janin, 2015
License	see the LICENSE file in the distribution
Maintainer	janin@labri.fr
Stability	experimental
Safe Haskell	Safe
Language	Haskell2010

Duration.Lattice

Description

Basic (complemented complete) lattice class. This does not intend to be a clever generic class for these lattices.

Synopsis

Documentation

class POrd a where Source #

Partially ordered sets

Minimal complete definition

partialCompare | pLeq

Methods

partialCompare :: a -> a -> Maybe Ordering Source #

A partial order relation. Though we do not require Eq a, we should have:

if (Eq a) then (a1 == a2) implies partialCompare a1 a2 == Just EQ

The converse may be false especially when Eq a is a "syntactic" equality as with [a].

pLeq :: a -> a -> Bool Source #

The Boolean version of the partial order.

pOrdEq :: a -> a -> Bool Source #

Derived equality:

pOrdEq a1 a2 = case partialCompare a1 a2 of
                  Just EQ -> True
                  _ -> False

pOrdMin :: [a] -> Maybe a Source #

Gets just the minimum of a list if it exists, nothing otherwise

pOrdMax :: [a] -> Maybe a Source #

Gets just the minimum of a list if it exists, nothing otherwise

pOrdReduceMin :: POrd a => [a] -> [a] Source #

Reduces a list to the antichain of its minimal elements

pOrdReduceMax :: POrd a => [a] -> [a] Source #

Reduces a list to the antichain of its maximal elements

Instances

POrd Char Source #	A total order on Char is a partial order
Methods partialCompare :: Char -> Char -> Maybe Ordering Source # pLeq :: Char -> Char -> Bool Source # pOrdEq :: Char -> Char -> Bool Source # pOrdMin :: [Char] -> Maybe Char Source # pOrdMax :: [Char] -> Maybe Char Source # pOrdReduceMin :: [Char] -> [Char] Source # pOrdReduceMax :: [Char] -> [Char] Source #
POrd Int Source #	A total order on Int is a partial order
Methods partialCompare :: Int -> Int -> Maybe Ordering Source # pLeq :: Int -> Int -> Bool Source # pOrdEq :: Int -> Int -> Bool Source # pOrdMin :: [Int] -> Maybe Int Source # pOrdMax :: [Int] -> Maybe Int Source # pOrdReduceMin :: [Int] -> [Int] Source # pOrdReduceMax :: [Int] -> [Int] Source #
POrd Integer Source #	A total order on Integer is a partial order
Methods partialCompare :: Integer -> Integer -> Maybe Ordering Source # pLeq :: Integer -> Integer -> Bool Source # pOrdEq :: Integer -> Integer -> Bool Source # pOrdMin :: [Integer] -> Maybe Integer Source # pOrdMax :: [Integer] -> Maybe Integer Source # pOrdReduceMin :: [Integer] -> [Integer] Source # pOrdReduceMax :: [Integer] -> [Integer] Source #
POrd Rational Source #	A total order on Rational is a partial order
Methods partialCompare :: Rational -> Rational -> Maybe Ordering Source # pLeq :: Rational -> Rational -> Bool Source # pOrdEq :: Rational -> Rational -> Bool Source # pOrdMin :: [Rational] -> Maybe Rational Source # pOrdMax :: [Rational] -> Maybe Rational Source # pOrdReduceMin :: [Rational] -> [Rational] Source # pOrdReduceMax :: [Rational] -> [Rational] Source #
POrd () Source #	A total order on () is a partial order
Methods partialCompare :: () -> () -> Maybe Ordering Source # pLeq :: () -> () -> Bool Source # pOrdEq :: () -> () -> Bool Source # pOrdMin :: [()] -> Maybe () Source # pOrdMax :: [()] -> Maybe () Source # pOrdReduceMin :: [()] -> [()] Source # pOrdReduceMax :: [()] -> [()] Source #
POrd Void Source #
Methods partialCompare :: Void -> Void -> Maybe Ordering Source # pLeq :: Void -> Void -> Bool Source # pOrdEq :: Void -> Void -> Bool Source # pOrdMin :: [Void] -> Maybe Void Source # pOrdMax :: [Void] -> Maybe Void Source # pOrdReduceMin :: [Void] -> [Void] Source # pOrdReduceMax :: [Void] -> [Void] Source #
POrd Midi Source #	Definition of porder in midi
Methods partialCompare :: Midi -> Midi -> Maybe Ordering Source # pLeq :: Midi -> Midi -> Bool Source # pOrdEq :: Midi -> Midi -> Bool Source # pOrdMin :: [Midi] -> Maybe Midi Source # pOrdMax :: [Midi] -> Maybe Midi Source # pOrdReduceMin :: [Midi] -> [Midi] Source # pOrdReduceMax :: [Midi] -> [Midi] Source #
(Eq d, POrd v) => POrd [Atom d iv v] Source #
Methods partialCompare :: [Atom d iv v] -> [Atom d iv v] -> Maybe Ordering Source # pLeq :: [Atom d iv v] -> [Atom d iv v] -> Bool Source # pOrdEq :: [Atom d iv v] -> [Atom d iv v] -> Bool Source # pOrdMin :: [[Atom d iv v]] -> Maybe [Atom d iv v] Source # pOrdMax :: [[Atom d iv v]] -> Maybe [Atom d iv v] Source # pOrdReduceMin :: [[Atom d iv v]] -> [[Atom d iv v]] Source # pOrdReduceMax :: [[Atom d iv v]] -> [[Atom d iv v]] Source #
POrd a => POrd (Complete a) Source #
Methods partialCompare :: Complete a -> Complete a -> Maybe Ordering Source # pLeq :: Complete a -> Complete a -> Bool Source # pOrdEq :: Complete a -> Complete a -> Bool Source # pOrdMin :: [Complete a] -> Maybe (Complete a) Source # pOrdMax :: [Complete a] -> Maybe (Complete a) Source # pOrdReduceMin :: [Complete a] -> [Complete a] Source # pOrdReduceMax :: [Complete a] -> [Complete a] Source #
POrd a => POrd (Max a) Source #	Derived partial order
Methods partialCompare :: Max a -> Max a -> Maybe Ordering Source # pLeq :: Max a -> Max a -> Bool Source # pOrdEq :: Max a -> Max a -> Bool Source # pOrdMin :: [Max a] -> Maybe (Max a) Source # pOrdMax :: [Max a] -> Maybe (Max a) Source # pOrdReduceMin :: [Max a] -> [Max a] Source # pOrdReduceMax :: [Max a] -> [Max a] Source #
POrd a => POrd (Min a) Source #	Min completion as a pOrd.
Methods partialCompare :: Min a -> Min a -> Maybe Ordering Source # pLeq :: Min a -> Min a -> Bool Source # pOrdEq :: Min a -> Min a -> Bool Source # pOrdMin :: [Min a] -> Maybe (Min a) Source # pOrdMax :: [Min a] -> Maybe (Min a) Source # pOrdReduceMin :: [Min a] -> [Min a] Source # pOrdReduceMax :: [Min a] -> [Min a] Source #
(POrd a, POrd b) => POrd (Either a b) Source #	Derived partial order for Either
Methods partialCompare :: Either a b -> Either a b -> Maybe Ordering Source # pLeq :: Either a b -> Either a b -> Bool Source # pOrdEq :: Either a b -> Either a b -> Bool Source # pOrdMin :: [Either a b] -> Maybe (Either a b) Source # pOrdMax :: [Either a b] -> Maybe (Either a b) Source # pOrdReduceMin :: [Either a b] -> [Either a b] Source # pOrdReduceMax :: [Either a b] -> [Either a b] Source #
(POrd a, POrd b) => POrd (a, b) Source #	Derived partial order for Product
Methods partialCompare :: (a, b) -> (a, b) -> Maybe Ordering Source # pLeq :: (a, b) -> (a, b) -> Bool Source # pOrdEq :: (a, b) -> (a, b) -> Bool Source # pOrdMin :: [(a, b)] -> Maybe (a, b) Source # pOrdMax :: [(a, b)] -> Maybe (a, b) Source # pOrdReduceMin :: [(a, b)] -> [(a, b)] Source # pOrdReduceMax :: [(a, b)] -> [(a, b)] Source #
(Num d, Ord d, Ord i) => POrd (Affine d i) Source #	Semantical partial order (with positive variables)
Methods partialCompare :: Affine d i -> Affine d i -> Maybe Ordering Source # pLeq :: Affine d i -> Affine d i -> Bool Source # pOrdEq :: Affine d i -> Affine d i -> Bool Source # pOrdMin :: [Affine d i] -> Maybe (Affine d i) Source # pOrdMax :: [Affine d i] -> Maybe (Affine d i) Source # pOrdReduceMin :: [Affine d i] -> [Affine d i] Source # pOrdReduceMax :: [Affine d i] -> [Affine d i] Source #
(Num d, Ord d, Ord i) => POrd (Duration d i) Source #
Methods partialCompare :: Duration d i -> Duration d i -> Maybe Ordering Source # pLeq :: Duration d i -> Duration d i -> Bool Source # pOrdEq :: Duration d i -> Duration d i -> Bool Source # pOrdMin :: [Duration d i] -> Maybe (Duration d i) Source # pOrdMax :: [Duration d i] -> Maybe (Duration d i) Source # pOrdReduceMin :: [Duration d i] -> [Duration d i] Source # pOrdReduceMax :: [Duration d i] -> [Duration d i] Source #
(Eq d, POrd v) => POrd (Atom d iv v) Source #	Derived `natural` partial order.
Methods partialCompare :: Atom d iv v -> Atom d iv v -> Maybe Ordering Source # pLeq :: Atom d iv v -> Atom d iv v -> Bool Source # pOrdEq :: Atom d iv v -> Atom d iv v -> Bool Source # pOrdMin :: [Atom d iv v] -> Maybe (Atom d iv v) Source # pOrdMax :: [Atom d iv v] -> Maybe (Atom d iv v) Source # pOrdReduceMin :: [Atom d iv v] -> [Atom d iv v] Source # pOrdReduceMax :: [Atom d iv v] -> [Atom d iv v] Source #
(Num d, Eq d, POrd d, POrd v) => POrd (DQ d iv v) Source #	Derived `natural` partial order, possibly unfolding recursive definitions.
Methods partialCompare :: DQ d iv v -> DQ d iv v -> Maybe Ordering Source # pLeq :: DQ d iv v -> DQ d iv v -> Bool Source # pOrdEq :: DQ d iv v -> DQ d iv v -> Bool Source # pOrdMin :: [DQ d iv v] -> Maybe (DQ d iv v) Source # pOrdMax :: [DQ d iv v] -> Maybe (DQ d iv v) Source # pOrdReduceMin :: [DQ d iv v] -> [DQ d iv v] Source # pOrdReduceMax :: [DQ d iv v] -> [DQ d iv v] Source #
(Num d, Eq d, POrd d, POrd v) => POrd (QList d iv v) Source #	Derived `natural` partial order, possibly unfolding recursive definitions.
Methods partialCompare :: QList d iv v -> QList d iv v -> Maybe Ordering Source # pLeq :: QList d iv v -> QList d iv v -> Bool Source # pOrdEq :: QList d iv v -> QList d iv v -> Bool Source # pOrdMin :: [QList d iv v] -> Maybe (QList d iv v) Source # pOrdMax :: [QList d iv v] -> Maybe (QList d iv v) Source # pOrdReduceMin :: [QList d iv v] -> [QList d iv v] Source # pOrdReduceMax :: [QList d iv v] -> [QList d iv v] Source #
(Num d, Eq d, POrd d, POrd v) => POrd (Tile d iv v) Source #	Derived `natural` partial order, unfolds recursive definitions.
Methods partialCompare :: Tile d iv v -> Tile d iv v -> Maybe Ordering Source # pLeq :: Tile d iv v -> Tile d iv v -> Bool Source # pOrdEq :: Tile d iv v -> Tile d iv v -> Bool Source # pOrdMin :: [Tile d iv v] -> Maybe (Tile d iv v) Source # pOrdMax :: [Tile d iv v] -> Maybe (Tile d iv v) Source # pOrdReduceMin :: [Tile d iv v] -> [Tile d iv v] Source # pOrdReduceMax :: [Tile d iv v] -> [Tile d iv v] Source #

class POrd d => Lattice d where Source #

Complemented complete lattices

Minimal complete definition

meet, compl

Methods

meet :: [d] -> d Source #

Least upper bound

x pLeq y if, and only if, x = meet [x,y]

We also have, thanks to the instance of POrd [a]

if l1 pLeq l2 then meet l1 pLeq l2

however, the converse may not hold.

join :: [d] -> d Source #

Greatest lower bound

x pLeq y if, and only if, y = join [x,y]

compl :: d -> d Source #

Complement, should satisfy the equations

partialCompare x y == partialCompare (compl y) (compl x)

and

join [l] == compl (meet [map compl l]), meet [l] == compl (join [map compl l])

top :: d Source #

Greatest value

top == meet[]

and

top == compl bot

bot :: d Source #

Least value

bot == join []

and

bot == compl top

Instances

Lattice Integer Source #	Without top and bot
Methods meet :: [Integer] -> Integer Source # join :: [Integer] -> Integer Source # compl :: Integer -> Integer Source # top :: Integer Source # bot :: Integer Source #
Lattice Rational Source #	Without top and bot
Methods meet :: [Rational] -> Rational Source # join :: [Rational] -> Rational Source # compl :: Rational -> Rational Source # top :: Rational Source # bot :: Rational Source #
(Lattice a, Lattice b) => Lattice (Complete (Either a b)) Source #	Derived lattice for Either
Methods meet :: [Complete (Either a b)] -> Complete (Either a b) Source # join :: [Complete (Either a b)] -> Complete (Either a b) Source # compl :: Complete (Either a b) -> Complete (Either a b) Source # top :: Complete (Either a b) Source # bot :: Complete (Either a b) Source #
(Num a, Ord a, POrd a) => Lattice (Complete a) Source #	Extending Lattice
Methods meet :: [Complete a] -> Complete a Source # join :: [Complete a] -> Complete a Source # compl :: Complete a -> Complete a Source # top :: Complete a Source # bot :: Complete a Source #
(POrd a, Num a) => Lattice (MinMax a) Source #	Derived Lattice instance
Methods meet :: [MinMax a] -> MinMax a Source # join :: [MinMax a] -> MinMax a Source # compl :: MinMax a -> MinMax a Source # top :: MinMax a Source # bot :: MinMax a Source #
(Lattice a, Lattice b) => Lattice (a, b) Source #	Derived lattice for Product
Methods meet :: [(a, b)] -> (a, b) Source # join :: [(a, b)] -> (a, b) Source # compl :: (a, b) -> (a, b) Source # top :: (a, b) Source # bot :: (a, b) Source #
(Num d, Ord d, Ord i) => Lattice (Duration d i) Source #
Methods meet :: [Duration d i] -> Duration d i Source # join :: [Duration d i] -> Duration d i Source # compl :: Duration d i -> Duration d i Source # top :: Duration d i Source # bot :: Duration d i Source #

data Complete a Source #

A rather adhoc completion of a partially ordered or an ordered type

Constructors

Top
Bot
Value a

Instances

Eq a => Eq (Complete a) Source #
Methods (==) :: Complete a -> Complete a -> Bool # (/=) :: Complete a -> Complete a -> Bool #
(Ord a, Fractional a) => Fractional (Complete a) Source #	Extending Fractional (Yet all adhoc)
Methods (/) :: Complete a -> Complete a -> Complete a # recip :: Complete a -> Complete a # fromRational :: Rational -> Complete a #
(Ord a, Num a) => Num (Complete a) Source #	Extending Num (Yet all adhoc)
Methods (+) :: Complete a -> Complete a -> Complete a # (-) :: Complete a -> Complete a -> Complete a # (*) :: Complete a -> Complete a -> Complete a # negate :: Complete a -> Complete a # abs :: Complete a -> Complete a # signum :: Complete a -> Complete a # fromInteger :: Integer -> Complete a #
Ord a => Ord (Complete a) Source #	Extending Ord
Methods compare :: Complete a -> Complete a -> Ordering # (<) :: Complete a -> Complete a -> Bool # (<=) :: Complete a -> Complete a -> Bool # (>) :: Complete a -> Complete a -> Bool # (>=) :: Complete a -> Complete a -> Bool # max :: Complete a -> Complete a -> Complete a # min :: Complete a -> Complete a -> Complete a #
Show a => Show (Complete a) Source #
Methods showsPrec :: Int -> Complete a -> ShowS # show :: Complete a -> String # showList :: [Complete a] -> ShowS #
POrd a => POrd (Complete a) Source #
Methods partialCompare :: Complete a -> Complete a -> Maybe Ordering Source # pLeq :: Complete a -> Complete a -> Bool Source # pOrdEq :: Complete a -> Complete a -> Bool Source # pOrdMin :: [Complete a] -> Maybe (Complete a) Source # pOrdMax :: [Complete a] -> Maybe (Complete a) Source # pOrdReduceMin :: [Complete a] -> [Complete a] Source # pOrdReduceMax :: [Complete a] -> [Complete a] Source #
(Lattice a, Lattice b) => Lattice (Complete (Either a b)) Source #	Derived lattice for Either
Methods meet :: [Complete (Either a b)] -> Complete (Either a b) Source # join :: [Complete (Either a b)] -> Complete (Either a b) Source # compl :: Complete (Either a b) -> Complete (Either a b) Source # top :: Complete (Either a b) Source # bot :: Complete (Either a b) Source #
(Num a, Ord a, POrd a) => Lattice (Complete a) Source #	Extending Lattice
Methods meet :: [Complete a] -> Complete a Source # join :: [Complete a] -> Complete a Source # compl :: Complete a -> Complete a Source # top :: Complete a Source # bot :: Complete a Source #