Data.Prd.Lattice

Documentation

class Prd a => Lattice a where

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

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

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

Lattice morphism.

Instances

Lattice Bool

Defined in Data.Prd.Lattice

Methods

(\/) :: Bool -> Bool -> Bool

(/\) :: Bool -> Bool -> Bool

fromSubset :: Set Bool -> Bool

Lattice ()

Defined in Data.Prd.Lattice

Methods

(\/) :: () -> () -> ()

(/\) :: () -> () -> ()

fromSubset :: Set () -> ()

Lattice All

Defined in Data.Prd.Lattice

Methods

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

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

fromSubset :: Set All -> All

Lattice Any

Defined in Data.Prd.Lattice

Methods

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

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

fromSubset :: Set Any -> Any

Lattice IntSet

Defined in Data.Prd.Lattice

Methods

(\/) :: IntSet -> IntSet -> IntSet

(/\) :: IntSet -> IntSet -> IntSet

fromSubset :: Set IntSet -> IntSet

Lattice Unsigned

Defined in Data.Dioid.Signed

Methods

(\/) :: Unsigned -> Unsigned -> Unsigned

(/\) :: Unsigned -> Unsigned -> Unsigned

fromSubset :: Set Unsigned -> Unsigned

Lattice a => Lattice (Maybe a)

Defined in Data.Prd.Lattice

Methods

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

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

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

Lattice a => Lattice (Down a)

Defined in Data.Prd.Lattice

Methods

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

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

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

Lattice a => Lattice (IntMap a)

Defined in Data.Prd.Lattice

Methods

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

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

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

Ord a => Lattice (Set a)

Defined in Data.Prd.Lattice

Methods

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

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

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

Ord a => Lattice (Ordered a)

Defined in Data.Prd.Lattice

Methods

(\/) :: Ordered a -> Ordered a -> Ordered a

(/\) :: Ordered a -> Ordered a -> Ordered a

fromSubset :: Set (Ordered a) -> Ordered a

(Lattice a, Lattice b) => Lattice (Either a b)

Defined in Data.Prd.Lattice

Methods

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

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

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

(Lattice a, Lattice b) => Lattice (a, b)

Defined in Data.Prd.Lattice

Methods

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

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

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

(Ord k, Lattice a) => Lattice (Map k a)

Defined in Data.Prd.Lattice

Methods

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

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

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

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

The partial ordering induced by the join-semilattice structure

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

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

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

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

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

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

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

median :: Lattice a => a -> a -> a -> a

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

Constructors

Join

Fields

• unJoin :: a

Instances

Eq a => Eq (Join a)

Defined in Data.Prd.Lattice

Methods

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

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

Data a => Data (Join a)

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)

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)

Defined in Data.Prd.Lattice

Methods

showsPrec :: Int -> Join a -> ShowS

show :: Join a -> String

showList :: [Join a] -> ShowS

Generic (Join a)

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)

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)

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)

Defined in Data.Prd.Lattice

Methods

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

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

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

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

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

type Rep (Join a)

Defined in Data.Prd.Lattice

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

newtype Meet a

Constructors

Meet

Fields

• unMeet :: a

Instances

Eq a => Eq (Meet a)

Defined in Data.Prd.Lattice

Methods

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

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

Data a => Data (Meet a)

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)

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)

Defined in Data.Prd.Lattice

Methods

showsPrec :: Int -> Meet a -> ShowS

show :: Meet a -> String

showList :: [Meet a] -> ShowS

Generic (Meet a)

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)

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)

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)

Defined in Data.Prd.Lattice

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

Orphan instances

Max All

Methods

maximal :: All

Max Any

Methods

maximal :: Any

Min All

Methods

minimal :: All

Min Any

Methods

minimal :: Any