semilattices-0.0.0.2: Semilattices

Data.Semilattice.Meet

Description

Join semilattices, related to Lower and Upper.

Synopsis

# Documentation

class Meet s where Source #

A meet semilattice is an idempotent commutative semigroup.

Minimal complete definition

(/\)

Methods

(/\) :: s -> s -> s infixr 7 Source #

The meet operation.

Laws:

Idempotence:

x /\ x = x


Associativity:

a /\ (b /\ c) = (a /\ b) /\ c


Commutativity:

a /\ b = b /\ a


Additionally, if s has an Upper bound, then upperBound must be its identity:

upperBound /\ a = a
a /\ upperBound = a


If s has a Lower bound, then lowerBound must be its absorbing element:

lowerBound /\ a = lowerBound
a /\ lowerBound = lowerBound

Instances
 Source # Boolean conjunction forms a semilattice.Idempotence:x /\ x == (x :: Bool)Associativity:a /\ (b /\ c) == (a /\ b) /\ (c :: Bool)Commutativity:a /\ b == b /\ (a :: Bool)Identity:upperBound /\ a == (a :: Bool)Absorption:lowerBound /\ a == (lowerBound :: Bool) Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: Bool -> Bool -> Bool Source # Source # Orderings form a semilattice.Idempotence:x /\ x == (x :: Ordering)Associativity:a /\ (b /\ c) == (a /\ b) /\ (c :: Ordering)Commutativity:a /\ b == b /\ (a :: Ordering)Identity:upperBound /\ a == (a :: Ordering)Absorption:lowerBound /\ a == (lowerBound :: Ordering) Instance detailsDefined in Data.Semilattice.Meet Methods Meet () Source # Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: () -> () -> () Source # Source # IntSet intersection forms a semilattice.Idempotence:x /\ x == (x :: IntSet)Associativity:a /\ (b /\ c) == (a /\ b) /\ (c :: IntSet)Commutativity:a /\ b == b /\ (a :: IntSet)Absorption:lowerBound /\ a == (lowerBound :: IntSet) Instance detailsDefined in Data.Semilattice.Meet Methods Ord a => Meet (Min a) Source # The greatest lowerBound bound gives rise to a meet semilattice.Idempotence:x /\ x == (x :: Min Int)Associativity:a /\ (b /\ c) == (a /\ b) /\ (c :: Min Int)Commutativity:a /\ b == b /\ (a :: Min Int)Identity:upperBound /\ a == (a :: Min Int)Absorption:lowerBound /\ a == (lowerBound :: Min Int) Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: Min a -> Min a -> Min a Source # Meet a => Meet (IntMap a) Source # IntMap union with Meetable values forms a semilattice.Idempotence:x /\ x == (x :: IntMap (Set Char))Associativity:a /\ (b /\ c) == (a /\ b) /\ (c :: IntMap (Set Char))Commutativity:a /\ b == b /\ (a :: IntMap (Set Char))Absorption:lowerBound /\ a == (lowerBound :: IntMap (Set Char)) Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: IntMap a -> IntMap a -> IntMap a Source # Ord a => Meet (Set a) Source # Set intersection forms a semilattice.Idempotence:x /\ x == (x :: Set Char)Associativity:a /\ (b /\ c) == (a /\ b) /\ (c :: Set Char)Commutativity:a /\ b == b /\ (a :: Set Char)Absorption:lowerBound /\ a == (lowerBound :: Set Char) Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: Set a -> Set a -> Set a Source # (Eq a, Hashable a) => Meet (HashSet a) Source # HashSet intersection forms a semilattice.Idempotence:x /\ x == (x :: HashSet Char)Associativity:a /\ (b /\ c) == (a /\ b) /\ (c :: HashSet Char)Commutativity:a /\ b == b /\ (a :: HashSet Char)Absorption:lowerBound /\ a == (lowerBound :: HashSet Char) Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: HashSet a -> HashSet a -> HashSet a Source # Meet a => Meet (GreaterThan a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: GreaterThan a -> GreaterThan a -> GreaterThan a Source # Meet a => Meet (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: Meeting a -> Meeting a -> Meeting a Source # Join a => Meet (Tumble a) Source # Instance detailsDefined in Data.Semilattice.Tumble Methods(/\) :: Tumble a -> Tumble a -> Tumble a Source # Ord a => Meet (Order a) Source # Total Orderings give rise to a meet semilattice satisfying:Idempotence:Order x /\ Order x == Order xAssociativity:Order a /\ (Order b /\ Order c) == (Order a /\ Order b) /\ Order cCommutativity:Order a /\ Order b == Order b /\ Order aIdentity:upperBound /\ Order a == Order (a :: Int)Absorption:lowerBound /\ Order a == (lowerBound :: Order Int)Distributivity:Order a /\ (Order b \/ Order c) == Order a /\ Order b \/ Order a /\ Order c Instance detailsDefined in Data.Semilattice.Order Methods(/\) :: Order a -> Order a -> Order a Source # Meet b => Meet (a -> b) Source # Functions with semilattice codomains form a semilattice.Idempotence:\ (Fn x) -> x /\ x ~= (x :: Int -> Bool)Associativity:\ (Fn a) (Fn b) (Fn c) -> a /\ (b /\ c) ~= (a /\ b) /\ (c :: Int -> Bool)Commutativity:\ (Fn a) (Fn b) -> a /\ b ~= b /\ (a :: Int -> Bool)Identity:\ (Fn a) -> upperBound /\ a ~= (a :: Int -> Bool)Absorption:\ (Fn a) -> lowerBound /\ a ~= (lowerBound :: Int -> Bool) Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: (a -> b) -> (a -> b) -> a -> b Source # (Ord k, Meet a) => Meet (Map k a) Source # Map union with Meetable values forms a semilattice.Idempotence:x /\ x == (x :: Map Char (Set Char))Associativity:a /\ (b /\ c) == (a /\ b) /\ (c :: Map Char (Set Char))Commutativity:a /\ b == b /\ (a :: Map Char (Set Char))Absorption:lowerBound /\ a == (lowerBound :: Map Char (Set Char)) Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: Map k a -> Map k a -> Map k a Source # (Eq k, Hashable k, Meet a) => Meet (HashMap k a) Source # HashMap union with Meetable values forms a semilattice.Idempotence:x /\ x == (x :: HashMap Char (Set Char))Associativity:a /\ (b /\ c) == (a /\ b) /\ (c :: HashMap Char (Set Char))Commutativity:a /\ b == b /\ (a :: HashMap Char (Set Char))Absorption:lowerBound /\ a == (lowerBound :: HashMap Char (Set Char)) Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: HashMap k a -> HashMap k a -> HashMap k a Source #

newtype Meeting a Source #

A Semigroup for any Meet semilattice.

If the semilattice has an Upper bound, there is additionally a Monoid instance.

Constructors

 Meeting FieldsgetMeeting :: a
Instances
 Source # Instance detailsDefined in Data.Semilattice.Meet Methodsfmap :: (a -> b) -> Meeting a -> Meeting b #(<$) :: a -> Meeting b -> Meeting a # Source # Instance detailsDefined in Data.Semilattice.Meet Methodsfold :: Monoid m => Meeting m -> m #foldMap :: Monoid m => (a -> m) -> Meeting a -> m #foldr :: (a -> b -> b) -> b -> Meeting a -> b #foldr' :: (a -> b -> b) -> b -> Meeting a -> b #foldl :: (b -> a -> b) -> b -> Meeting a -> b #foldl' :: (b -> a -> b) -> b -> Meeting a -> b #foldr1 :: (a -> a -> a) -> Meeting a -> a #foldl1 :: (a -> a -> a) -> Meeting a -> a #toList :: Meeting a -> [a] #null :: Meeting a -> Bool #length :: Meeting a -> Int #elem :: Eq a => a -> Meeting a -> Bool #maximum :: Ord a => Meeting a -> a #minimum :: Ord a => Meeting a -> a #sum :: Num a => Meeting a -> a #product :: Num a => Meeting a -> a # Source # Instance detailsDefined in Data.Semilattice.Meet Methodstraverse :: Applicative f => (a -> f b) -> Meeting a -> f (Meeting b) #sequenceA :: Applicative f => Meeting (f a) -> f (Meeting a) #mapM :: Monad m => (a -> m b) -> Meeting a -> m (Meeting b) #sequence :: Monad m => Meeting (m a) -> m (Meeting a) # Bounded a => Bounded (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods Enum a => Enum (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet Methodssucc :: Meeting a -> Meeting a #pred :: Meeting a -> Meeting a #toEnum :: Int -> Meeting a #fromEnum :: Meeting a -> Int #enumFrom :: Meeting a -> [Meeting a] #enumFromThen :: Meeting a -> Meeting a -> [Meeting a] #enumFromTo :: Meeting a -> Meeting a -> [Meeting a] #enumFromThenTo :: Meeting a -> Meeting a -> Meeting a -> [Meeting a] # Eq a => Eq (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods(==) :: Meeting a -> Meeting a -> Bool #(/=) :: Meeting a -> Meeting a -> Bool # Num a => Num (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods(+) :: Meeting a -> Meeting a -> Meeting a #(-) :: Meeting a -> Meeting a -> Meeting a #(*) :: Meeting a -> Meeting a -> Meeting a #negate :: Meeting a -> Meeting a #abs :: Meeting a -> Meeting a #signum :: Meeting a -> Meeting a # Ord a => Ord (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet Methodscompare :: Meeting a -> Meeting a -> Ordering #(<) :: Meeting a -> Meeting a -> Bool #(<=) :: Meeting a -> Meeting a -> Bool #(>) :: Meeting a -> Meeting a -> Bool #(>=) :: Meeting a -> Meeting a -> Bool #max :: Meeting a -> Meeting a -> Meeting a #min :: Meeting a -> Meeting a -> Meeting a # Read a => Read (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet MethodsreadsPrec :: Int -> ReadS (Meeting a) # Show a => Show (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet MethodsshowsPrec :: Int -> Meeting a -> ShowS #show :: Meeting a -> String #showList :: [Meeting a] -> ShowS # Meet a => Semigroup (Meeting a) Source # Meeting <> is associative.Meeting a <> (Meeting b <> Meeting c) == (Meeting a <> Meeting b) <> Meeting (c :: IntSet) Instance detailsDefined in Data.Semilattice.Meet Methods(<>) :: Meeting a -> Meeting a -> Meeting a #sconcat :: NonEmpty (Meeting a) -> Meeting a #stimes :: Integral b => b -> Meeting a -> Meeting a # (Upper a, Meet a) => Monoid (Meeting a) Source # Meeting mempty is the left- and right-identity.let (l, r) = (mappend mempty (Meeting x), mappend (Meeting x) mempty) in l == Meeting x && r == Meeting (x :: Bool) Instance detailsDefined in Data.Semilattice.Meet Methodsmappend :: Meeting a -> Meeting a -> Meeting a #mconcat :: [Meeting a] -> Meeting a # Upper a => Upper (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods Meet a => Meet (Meeting a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: Meeting a -> Meeting a -> Meeting a Source # newtype GreaterThan a Source # Meet semilattices give rise to a partial Ordering. Constructors  GreaterThan FieldsgetGreaterThan :: a Instances  Source # Instance detailsDefined in Data.Semilattice.Meet Methodsfmap :: (a -> b) -> GreaterThan a -> GreaterThan b #(<$) :: a -> GreaterThan b -> GreaterThan a # Source # Instance detailsDefined in Data.Semilattice.Meet Methodsfold :: Monoid m => GreaterThan m -> m #foldMap :: Monoid m => (a -> m) -> GreaterThan a -> m #foldr :: (a -> b -> b) -> b -> GreaterThan a -> b #foldr' :: (a -> b -> b) -> b -> GreaterThan a -> b #foldl :: (b -> a -> b) -> b -> GreaterThan a -> b #foldl' :: (b -> a -> b) -> b -> GreaterThan a -> b #foldr1 :: (a -> a -> a) -> GreaterThan a -> a #foldl1 :: (a -> a -> a) -> GreaterThan a -> a #toList :: GreaterThan a -> [a] #null :: GreaterThan a -> Bool #length :: GreaterThan a -> Int #elem :: Eq a => a -> GreaterThan a -> Bool #maximum :: Ord a => GreaterThan a -> a #minimum :: Ord a => GreaterThan a -> a #sum :: Num a => GreaterThan a -> a #product :: Num a => GreaterThan a -> a # Source # Instance detailsDefined in Data.Semilattice.Meet Methodstraverse :: Applicative f => (a -> f b) -> GreaterThan a -> f (GreaterThan b) #sequenceA :: Applicative f => GreaterThan (f a) -> f (GreaterThan a) #mapM :: Monad m => (a -> m b) -> GreaterThan a -> m (GreaterThan b) #sequence :: Monad m => GreaterThan (m a) -> m (GreaterThan a) # Enum a => Enum (GreaterThan a) Source # Instance detailsDefined in Data.Semilattice.Meet Methodssucc :: GreaterThan a -> GreaterThan a #pred :: GreaterThan a -> GreaterThan a #fromEnum :: GreaterThan a -> Int #enumFrom :: GreaterThan a -> [GreaterThan a] #enumFromThen :: GreaterThan a -> GreaterThan a -> [GreaterThan a] #enumFromTo :: GreaterThan a -> GreaterThan a -> [GreaterThan a] #enumFromThenTo :: GreaterThan a -> GreaterThan a -> GreaterThan a -> [GreaterThan a] # Eq a => Eq (GreaterThan a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods(==) :: GreaterThan a -> GreaterThan a -> Bool #(/=) :: GreaterThan a -> GreaterThan a -> Bool # Num a => Num (GreaterThan a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods(+) :: GreaterThan a -> GreaterThan a -> GreaterThan a #(-) :: GreaterThan a -> GreaterThan a -> GreaterThan a #(*) :: GreaterThan a -> GreaterThan a -> GreaterThan a #abs :: GreaterThan a -> GreaterThan a # (Eq a, Meet a) => Ord (GreaterThan a) Source # NB: This is not in general a total ordering. Instance detailsDefined in Data.Semilattice.Meet Methodscompare :: GreaterThan a -> GreaterThan a -> Ordering #(<) :: GreaterThan a -> GreaterThan a -> Bool #(<=) :: GreaterThan a -> GreaterThan a -> Bool #(>) :: GreaterThan a -> GreaterThan a -> Bool #(>=) :: GreaterThan a -> GreaterThan a -> Bool #max :: GreaterThan a -> GreaterThan a -> GreaterThan a #min :: GreaterThan a -> GreaterThan a -> GreaterThan a # Read a => Read (GreaterThan a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods Show a => Show (GreaterThan a) Source # Instance detailsDefined in Data.Semilattice.Meet MethodsshowsPrec :: Int -> GreaterThan a -> ShowS #show :: GreaterThan a -> String #showList :: [GreaterThan a] -> ShowS # Meet a => Meet (GreaterThan a) Source # Instance detailsDefined in Data.Semilattice.Meet Methods(/\) :: GreaterThan a -> GreaterThan a -> GreaterThan a Source #