connections-0.0.2: Partial orders & Galois connections.

Safe HaskellSafe
LanguageHaskell2010

Data.Prd.Lattice

Contents

Synopsis

Documentation

class Prd a => Lattice a where Source #

Lattices.

A lattice is a partially ordered set in which every two elements have a unique join (least upper bound or supremum) and a unique meet (greatest lower bound or infimum).

See http://en.wikipedia.org/wiki/Lattice_(order) and http://en.wikipedia.org/wiki/Absorption_law.

Laws

x \/ maximal ≡ x

Corollary

x \/ maximal
  ≡⟨ identity ⟩
(x \/ maximal) /\ maximal
  ≡⟨ absorption ⟩
maximal
x \/ minimal ≡ x

Corollary

x /\ minimal
  ≡⟨ identity ⟩
(x /\ minimal) \/ minimal
  ≡⟨ absorption ⟩
minimal

Associativity

x \/ (y \/ z) ≡ (x \/ y) \/ z
x /\ (y /\ z) ≡ (x /\ y) /\ z

Commutativity

x \/ y ≡ y \/ x
x /\ y ≡ y /\ x

Idempotency

x \/ x ≡ x
x /\ x ≡ x

Absorption

(x \/ y) /\ y ≡ y
(x /\ y) \/ y ≡ y

Minimal complete definition

(\/), (/\)

Methods

(\/) :: a -> a -> a infixr 5 Source #

(/\) :: a -> a -> a infixr 6 Source #

fromSubset :: Min a => Set a -> a Source #

Lattice morphism.

Instances
Lattice Bool Source # 
Instance details

Defined in Data.Prd.Lattice

Lattice () Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: () -> () -> () Source #

(/\) :: () -> () -> () Source #

fromSubset :: Set () -> () Source #

Lattice All Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: All -> All -> All Source #

(/\) :: All -> All -> All Source #

fromSubset :: Set All -> All Source #

Lattice Any Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: Any -> Any -> Any Source #

(/\) :: Any -> Any -> Any Source #

fromSubset :: Set Any -> Any Source #

Lattice IntSet Source # 
Instance details

Defined in Data.Prd.Lattice

Lattice a => Lattice (Maybe a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: Maybe a -> Maybe a -> Maybe a Source #

(/\) :: Maybe a -> Maybe a -> Maybe a Source #

fromSubset :: Set (Maybe a) -> Maybe a Source #

Lattice a => Lattice (Down a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: Down a -> Down a -> Down a Source #

(/\) :: Down a -> Down a -> Down a Source #

fromSubset :: Set (Down a) -> Down a Source #

Lattice a => Lattice (IntMap a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: IntMap a -> IntMap a -> IntMap a Source #

(/\) :: IntMap a -> IntMap a -> IntMap a Source #

fromSubset :: Set (IntMap a) -> IntMap a Source #

Ord a => Lattice (Set a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: Set a -> Set a -> Set a Source #

(/\) :: Set a -> Set a -> Set a Source #

fromSubset :: Set (Set a) -> Set a Source #

Ord a => Lattice (Ordered a) Source # 
Instance details

Defined in Data.Prd.Lattice

(Lattice a, Lattice b) => Lattice (Either a b) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: Either a b -> Either a b -> Either a b Source #

(/\) :: Either a b -> Either a b -> Either a b Source #

fromSubset :: Set (Either a b) -> Either a b Source #

(Lattice a, Lattice b) => Lattice (a, b) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: (a, b) -> (a, b) -> (a, b) Source #

(/\) :: (a, b) -> (a, b) -> (a, b) Source #

fromSubset :: Set (a, b) -> (a, b) Source #

(Ord k, Lattice a) => Lattice (Map k a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(\/) :: Map k a -> Map k a -> Map k a Source #

(/\) :: Map k a -> Map k a -> Map k a Source #

fromSubset :: Set (Map k a) -> Map k a Source #

joinLeq :: Lattice a => a -> a -> Bool Source #

The partial ordering induced by the join-semilattice structure

meetLeq :: Lattice a => a -> a -> Bool Source #

join :: (Min a, Lattice a, Foldable f) => f a -> a Source #

meet :: (Max a, Lattice a, Foldable f) => f a -> a Source #

join1 :: (Lattice a, Foldable1 f) => f a -> a Source #

The join of at a list of join-semilattice elements (of length at least one)

meet1 :: (Lattice a, Foldable1 f) => f a -> a Source #

The meet of at a list of meet-semilattice elements (of length at least one)

median :: Lattice a => a -> a -> a -> a Source #

Birkhoff's self-dual ternary median operation.

TODO: require a Dioid instance.

 median x x y ≡ x
 median x y z ≡ median z x y
 median x y z ≡  median x z y
 median (median x w y) w z ≡ median x w (median y w z)

newtype Join a Source #

Constructors

Join 

Fields

Instances
Eq a => Eq (Join a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(==) :: Join a -> Join a -> Bool #

(/=) :: Join a -> Join a -> Bool #

Data a => Data (Join a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

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

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

toConstr :: Join a -> Constr #

dataTypeOf :: Join a -> DataType #

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

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

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

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

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

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

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

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

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

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

Ord a => Ord (Join a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

compare :: Join a -> Join a -> Ordering #

(<) :: Join a -> Join a -> Bool #

(<=) :: Join a -> Join a -> Bool #

(>) :: Join a -> Join a -> Bool #

(>=) :: Join a -> Join a -> Bool #

max :: Join a -> Join a -> Join a #

min :: Join a -> Join a -> Join a #

Show a => Show (Join a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

showsPrec :: Int -> Join a -> ShowS #

show :: Join a -> String #

showList :: [Join a] -> ShowS #

Generic (Join a) Source # 
Instance details

Defined in Data.Prd.Lattice

Associated Types

type Rep (Join a) :: Type -> Type #

Methods

from :: Join a -> Rep (Join a) x #

to :: Rep (Join a) x -> Join a #

Lattice a => Semigroup (Join a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(<>) :: Join a -> Join a -> Join a #

sconcat :: NonEmpty (Join a) -> Join a #

stimes :: Integral b => b -> Join a -> Join a #

(Lattice a, Min a) => Monoid (Join a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

mempty :: Join a #

mappend :: Join a -> Join a -> Join a #

mconcat :: [Join a] -> Join a #

(Eq a, Lattice a) => Prd (Join a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(<~) :: Join a -> Join a -> Bool Source #

(>~) :: Join a -> Join a -> Bool Source #

(=~) :: Join a -> Join a -> Bool Source #

(?~) :: Join a -> Join a -> Bool Source #

pcompare :: Join a -> Join a -> Maybe Ordering Source #

type Rep (Join a) Source # 
Instance details

Defined in Data.Prd.Lattice

type Rep (Join a) = D1 (MetaData "Join" "Data.Prd.Lattice" "connections-0.0.2-3bGTwkYWIphGQUrhB8xvK6" True) (C1 (MetaCons "Join" PrefixI True) (S1 (MetaSel (Just "unJoin") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

newtype Meet a Source #

Constructors

Meet 

Fields

Instances
Eq a => Eq (Meet a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(==) :: Meet a -> Meet a -> Bool #

(/=) :: Meet a -> Meet a -> Bool #

Data a => Data (Meet a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

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

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

toConstr :: Meet a -> Constr #

dataTypeOf :: Meet a -> DataType #

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

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

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

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

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

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

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

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

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

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

Ord a => Ord (Meet a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

compare :: Meet a -> Meet a -> Ordering #

(<) :: Meet a -> Meet a -> Bool #

(<=) :: Meet a -> Meet a -> Bool #

(>) :: Meet a -> Meet a -> Bool #

(>=) :: Meet a -> Meet a -> Bool #

max :: Meet a -> Meet a -> Meet a #

min :: Meet a -> Meet a -> Meet a #

Show a => Show (Meet a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

showsPrec :: Int -> Meet a -> ShowS #

show :: Meet a -> String #

showList :: [Meet a] -> ShowS #

Generic (Meet a) Source # 
Instance details

Defined in Data.Prd.Lattice

Associated Types

type Rep (Meet a) :: Type -> Type #

Methods

from :: Meet a -> Rep (Meet a) x #

to :: Rep (Meet a) x -> Meet a #

Lattice a => Semigroup (Meet a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

(<>) :: Meet a -> Meet a -> Meet a #

sconcat :: NonEmpty (Meet a) -> Meet a #

stimes :: Integral b => b -> Meet a -> Meet a #

(Lattice a, Max a) => Monoid (Meet a) Source # 
Instance details

Defined in Data.Prd.Lattice

Methods

mempty :: Meet a #

mappend :: Meet a -> Meet a -> Meet a #

mconcat :: [Meet a] -> Meet a #

type Rep (Meet a) Source # 
Instance details

Defined in Data.Prd.Lattice

type Rep (Meet a) = D1 (MetaData "Meet" "Data.Prd.Lattice" "connections-0.0.2-3bGTwkYWIphGQUrhB8xvK6" True) (C1 (MetaCons "Meet" PrefixI True) (S1 (MetaSel (Just "unMeet") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

Orphan instances

Max All Source # 
Instance details

Methods

maximal :: All Source #

Max Any Source # 
Instance details

Methods

maximal :: Any Source #

Min All Source # 
Instance details

Methods

minimal :: All Source #

Min Any Source # 
Instance details

Methods

minimal :: Any Source #