connections-0.0.2.1: Partial orders & Galois connections.

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

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 :: Minimal a => Set a -> a Source #

Lattice morphism.

Instances
 Source # Instance detailsDefined in Data.Prd.Lattice Methods(\/) :: Bool -> Bool -> Bool Source #(/\) :: Bool -> Bool -> Bool Source # Lattice () Source # Instance detailsDefined in Data.Prd.Lattice Methods(\/) :: () -> () -> () Source #(/\) :: () -> () -> () Source #fromSubset :: Set () -> () Source # Source # Instance detailsDefined in Data.Prd.Lattice Methods(\/) :: All -> All -> All Source #(/\) :: All -> All -> All Source # Source # Instance detailsDefined in Data.Prd.Lattice Methods(\/) :: Any -> Any -> Any Source #(/\) :: Any -> Any -> Any Source # Source # Instance detailsDefined in Data.Prd.Lattice Methods Lattice a => Lattice (Maybe a) Source # Instance detailsDefined 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 detailsDefined 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 detailsDefined 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 detailsDefined 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 detailsDefined in Data.Prd.Lattice Methods(\/) :: Ordered a -> Ordered a -> Ordered a Source #(/\) :: Ordered a -> Ordered a -> Ordered a Source #fromSubset :: Set (Ordered a) -> Ordered a Source # (Lattice a, Lattice b) => Lattice (Either a b) Source # Instance detailsDefined 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 detailsDefined 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 detailsDefined 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 :: (Minimal a, Lattice a, Foldable f) => f a -> a Source #

meet :: (Maximal 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.

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 FieldsunJoin :: a
Instances
 Eq a => Eq (Join a) Source # Instance detailsDefined in Data.Prd.Lattice Methods(==) :: Join a -> Join a -> Bool #(/=) :: Join a -> Join a -> Bool # Data a => Data (Join a) Source # Instance detailsDefined in Data.Prd.Lattice Methodsgfoldl :: (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 detailsDefined in Data.Prd.Lattice Methodscompare :: 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 detailsDefined in Data.Prd.Lattice MethodsshowsPrec :: Int -> Join a -> ShowS #show :: Join a -> String #showList :: [Join a] -> ShowS # Generic (Join a) Source # Instance detailsDefined in Data.Prd.Lattice Associated Typestype Rep (Join a) :: Type -> Type # Methodsfrom :: Join a -> Rep (Join a) x #to :: Rep (Join a) x -> Join a # Lattice a => Semigroup (Join a) Source # Instance detailsDefined 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, Minimal a) => Monoid (Join a) Source # Instance detailsDefined in Data.Prd.Lattice Methodsmempty :: Join a #mappend :: Join a -> Join a -> Join a #mconcat :: [Join a] -> Join a # (Eq a, Lattice a) => Prd (Join a) Source # Instance detailsDefined 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 detailsDefined in Data.Prd.Lattice type Rep (Join a) = D1 (MetaData "Join" "Data.Prd.Lattice" "connections-0.0.2.1-409JT1VTQIKEBkLJX6J8hV" True) (C1 (MetaCons "Join" PrefixI True) (S1 (MetaSel (Just "unJoin") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

newtype Meet a Source #

Constructors

 Meet FieldsunMeet :: a
Instances
 Eq a => Eq (Meet a) Source # Instance detailsDefined in Data.Prd.Lattice Methods(==) :: Meet a -> Meet a -> Bool #(/=) :: Meet a -> Meet a -> Bool # Data a => Data (Meet a) Source # Instance detailsDefined in Data.Prd.Lattice Methodsgfoldl :: (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 detailsDefined in Data.Prd.Lattice Methodscompare :: 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 detailsDefined in Data.Prd.Lattice MethodsshowsPrec :: Int -> Meet a -> ShowS #show :: Meet a -> String #showList :: [Meet a] -> ShowS # Generic (Meet a) Source # Instance detailsDefined in Data.Prd.Lattice Associated Typestype Rep (Meet a) :: Type -> Type # Methodsfrom :: Meet a -> Rep (Meet a) x #to :: Rep (Meet a) x -> Meet a # Lattice a => Semigroup (Meet a) Source # Instance detailsDefined 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, Maximal a) => Monoid (Meet a) Source # Instance detailsDefined in Data.Prd.Lattice Methodsmempty :: Meet a #mappend :: Meet a -> Meet a -> Meet a #mconcat :: [Meet a] -> Meet a # type Rep (Meet a) Source # Instance detailsDefined in Data.Prd.Lattice type Rep (Meet a) = D1 (MetaData "Meet" "Data.Prd.Lattice" "connections-0.0.2.1-409JT1VTQIKEBkLJX6J8hV" True) (C1 (MetaCons "Meet" PrefixI True) (S1 (MetaSel (Just "unMeet") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

Orphan instances

 Source # Instance details Methods Source # Instance details Methods Source # Instance details Methods Source # Instance details Methods