| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Data.Prd.Lattice
Contents
Synopsis
- class Prd a => Lattice a where
- (\/) :: a -> a -> a
- (/\) :: a -> a -> a
- fromSubset :: Min a => Set a -> a
- joinLeq :: Lattice a => a -> a -> Bool
- 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
- meet1 :: (Lattice a, Foldable1 f) => f a -> a
- median :: Lattice a => a -> a -> a -> a
- newtype Join a = Join {
- unJoin :: a
- newtype Meet a = Meet {
- unMeet :: a
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
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 # | |
| Lattice () Source # | |
| Lattice All Source # | |
| Lattice Any Source # | |
| Lattice IntSet Source # | |
| Lattice a => Lattice (Maybe a) Source # | |
| Lattice a => Lattice (Down a) Source # | |
| Lattice a => Lattice (IntMap a) Source # | |
| Ord a => Lattice (Set a) Source # | |
| Ord a => Lattice (Ordered a) Source # | |
| (Lattice a, Lattice b) => Lattice (Either a b) Source # | |
| (Lattice a, Lattice b) => Lattice (a, b) Source # | |
| (Ord k, Lattice a) => Lattice (Map k a) Source # | |
joinLeq :: Lattice a => a -> a -> Bool Source #
The partial ordering induced by the join-semilattice structure
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)
Instances
| Eq a => Eq (Join a) Source # | |
| Data a => Data (Join a) Source # | |
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 # | |
| Show a => Show (Join a) Source # | |
| Generic (Join a) Source # | |
| Lattice a => Semigroup (Join a) Source # | |
| (Lattice a, Min a) => Monoid (Join a) Source # | |
| (Eq a, Lattice a) => Prd (Join a) Source # | |
| type Rep (Join a) Source # | |
Defined in Data.Prd.Lattice | |
Instances
| Eq a => Eq (Meet a) Source # | |
| Data a => Data (Meet a) Source # | |
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 # | |
| Show a => Show (Meet a) Source # | |
| Generic (Meet a) Source # | |
| Lattice a => Semigroup (Meet a) Source # | |
| (Lattice a, Max a) => Monoid (Meet a) Source # | |
| type Rep (Meet a) Source # | |
Defined in Data.Prd.Lattice | |