Safe Haskell	None
Language	Haskell2010

Semilattice

Synopsis

class Join s where
class Meet s where
newtype Order a = Order {
- getOrder :: a
}

Documentation

class Join s where #

A join semilattice is an idempotent commutative semigroup.

Minimal complete definition

(\/)

Methods

(\/) :: s -> s -> s infixr 6 #

The join operation.

Laws:

Idempotence:

x \/ x = x

Associativity:

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

Commutativity:

a \/ b = b \/ a

Additionally, if s has a Lower bound, then lowerBound must be its identity:

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

If s has an Upper bound, then upperBound must be its absorbing element:

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

Instances

Join Bool	Boolean disjunction forms a semilattice. Idempotence: x \/ x == (x :: Bool) Associativity: a \/ (b \/ c) == (a \/ b) \/ (c :: Bool) Commutativity: a \/ b == b \/ (a :: Bool) Identity: lowerBound \/ a == (a :: Bool) Absorption: upperBound \/ a == (upperBound :: Bool)
Instance details Defined in Data.Semilattice.Join Methods (\/) :: Bool -> Bool -> Bool #
Join Ordering	Orderings form a semilattice. Idempotence: x \/ x == (x :: Ordering) Associativity: a \/ (b \/ c) == (a \/ b) \/ (c :: Ordering) Commutativity: a \/ b == b \/ (a :: Ordering) Identity: lowerBound \/ a == (a :: Ordering) Absorption: upperBound \/ a == (upperBound :: Ordering)
Instance details Defined in Data.Semilattice.Join Methods (\/) :: Ordering -> Ordering -> Ordering #
Join ()
Instance details Defined in Data.Semilattice.Join Methods (\/) :: () -> () -> () #
Join IntSet	IntSet union forms a semilattice. Idempotence: x \/ x == (x :: IntSet) Associativity: a \/ (b \/ c) == (a \/ b) \/ (c :: IntSet) Commutativity: a \/ b == b \/ (a :: IntSet) Identity: lowerBound \/ a == (a :: IntSet)
Instance details Defined in Data.Semilattice.Join Methods (\/) :: IntSet -> IntSet -> IntSet #
Ord a => Join (Max a)	The least upperBound bound gives rise to a join semilattice. Idempotence: x \/ x == (x :: Max Int) Associativity: a \/ (b \/ c) == (a \/ b) \/ (c :: Max Int) Commutativity: a \/ b == b \/ (a :: Max Int) Identity: lowerBound \/ a == (a :: Max Int) Absorption: upperBound \/ a == (upperBound :: Max Int)
Instance details Defined in Data.Semilattice.Join Methods (\/) :: Max a -> Max a -> Max a #
Join a => Join (IntMap a)	IntMap union with `Join`able 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)) Identity: lowerBound \/ a == (a :: IntMap (Set Char))
Instance details Defined in Data.Semilattice.Join Methods (\/) :: IntMap a -> IntMap a -> IntMap a #
Ord a => Join (Set a)	Set union 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) Identity: lowerBound \/ a == (a :: Set Char)
Instance details Defined in Data.Semilattice.Join Methods (\/) :: Set a -> Set a -> Set a #
(Eq a, Hashable a) => Join (HashSet a)	HashSet union 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) Identity: lowerBound \/ a == (a :: HashSet Char)
Instance details Defined in Data.Semilattice.Join Methods (\/) :: HashSet a -> HashSet a -> HashSet a #
Ord a => Join (Order a)	Total `Ord`erings give rise to a join semilattice satisfying: Idempotence: Order x \/ Order x == Order x Associativity: Order a \/ (Order b \/ Order c) == (Order a \/ Order b) \/ Order c Commutativity: Order a \/ Order b == Order b \/ Order a Identity: lowerBound \/ Order a == Order (a :: Int) Absorption: upperBound \/ Order a == (upperBound :: Order Int) Distributivity: Order a \/ Order b /\ Order c == (Order a \/ Order b) /\ (Order a \/ Order c)
Instance details Defined in Data.Semilattice.Order Methods (\/) :: Order a -> Order a -> Order a #
Join a => Join (Joining a)
Instance details Defined in Data.Semilattice.Join Methods (\/) :: Joining a -> Joining a -> Joining a #
Join a => Join (LessThan a)
Instance details Defined in Data.Semilattice.Join Methods (\/) :: LessThan a -> LessThan a -> LessThan a #
Join b => Join (a -> b)	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) -> lowerBound \/ a ~= (a :: Int -> Bool) Absorption: \ (Fn a) -> upperBound \/ a ~= (upperBound :: Int -> Bool)
Instance details Defined in Data.Semilattice.Join Methods (\/) :: (a -> b) -> (a -> b) -> a -> b #
(Eq k, Hashable k, Join a) => Join (HashMap k a)	HashMap union with `Join`able 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)) Identity: lowerBound \/ a == (a :: HashMap Char (Set Char))
Instance details Defined in Data.Semilattice.Join Methods (\/) :: HashMap k a -> HashMap k a -> HashMap k a #
(Ord k, Join a) => Join (Map k a)	Map union with `Join`able 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)) Identity: lowerBound \/ a == (a :: Map Char (Set Char))
Instance details Defined in Data.Semilattice.Join Methods (\/) :: Map k a -> Map k a -> Map k a #

class Meet s where #

A meet semilattice is an idempotent commutative semigroup.

Minimal complete definition

(/\)

Methods

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

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

Meet Bool	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 details Defined in Data.Semilattice.Meet Methods (/\) :: Bool -> Bool -> Bool #
Meet Ordering	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 details Defined in Data.Semilattice.Meet Methods (/\) :: Ordering -> Ordering -> Ordering #
Meet ()
Instance details Defined in Data.Semilattice.Meet Methods (/\) :: () -> () -> () #
Meet IntSet	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 details Defined in Data.Semilattice.Meet Methods (/\) :: IntSet -> IntSet -> IntSet #
Ord a => Meet (Min a)	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 details Defined in Data.Semilattice.Meet Methods (/\) :: Min a -> Min a -> Min a #
Meet a => Meet (IntMap a)	IntMap union with `Meet`able 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 details Defined in Data.Semilattice.Meet Methods (/\) :: IntMap a -> IntMap a -> IntMap a #
Ord a => Meet (Set a)	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 details Defined in Data.Semilattice.Meet Methods (/\) :: Set a -> Set a -> Set a #
(Eq a, Hashable a) => Meet (HashSet a)	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 details Defined in Data.Semilattice.Meet Methods (/\) :: HashSet a -> HashSet a -> HashSet a #
Ord a => Meet (Order a)	Total `Ord`erings give rise to a meet semilattice satisfying: Idempotence: Order x /\ Order x == Order x Associativity: Order a /\ (Order b /\ Order c) == (Order a /\ Order b) /\ Order c Commutativity: Order a /\ Order b == Order b /\ Order a Identity: 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 details Defined in Data.Semilattice.Order Methods (/\) :: Order a -> Order a -> Order a #
Meet a => Meet (Meeting a)
Instance details Defined in Data.Semilattice.Meet Methods (/\) :: Meeting a -> Meeting a -> Meeting a #
Meet a => Meet (GreaterThan a)
Instance details Defined in Data.Semilattice.Meet Methods (/\) :: GreaterThan a -> GreaterThan a -> GreaterThan a #
Meet b => Meet (a -> b)	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 details Defined in Data.Semilattice.Meet Methods (/\) :: (a -> b) -> (a -> b) -> a -> b #
(Eq k, Hashable k, Meet a) => Meet (HashMap k a)	HashMap union with `Meet`able 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 details Defined in Data.Semilattice.Meet Methods (/\) :: HashMap k a -> HashMap k a -> HashMap k a #
(Ord k, Meet a) => Meet (Map k a)	Map union with `Meet`able 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 details Defined in Data.Semilattice.Meet Methods (/\) :: Map k a -> Map k a -> Map k a #

newtype Order a #

A Join- and Meet-semilattice for any total Ordering.

Constructors

Order
Fields getOrder :: a

Instances

Functor Order
Instance details Defined in Data.Semilattice.Order Methods fmap :: (a -> b) -> Order a -> Order b # (<$) :: a -> Order b -> Order a #
Foldable Order
Instance details Defined in Data.Semilattice.Order Methods fold :: Monoid m => Order m -> m # foldMap :: Monoid m => (a -> m) -> Order a -> m # foldr :: (a -> b -> b) -> b -> Order a -> b # foldr' :: (a -> b -> b) -> b -> Order a -> b # foldl :: (b -> a -> b) -> b -> Order a -> b # foldl' :: (b -> a -> b) -> b -> Order a -> b # foldr1 :: (a -> a -> a) -> Order a -> a # foldl1 :: (a -> a -> a) -> Order a -> a # toList :: Order a -> [a] # null :: Order a -> Bool # length :: Order a -> Int # elem :: Eq a => a -> Order a -> Bool # maximum :: Ord a => Order a -> a # minimum :: Ord a => Order a -> a # sum :: Num a => Order a -> a # product :: Num a => Order a -> a #
Traversable Order
Instance details Defined in Data.Semilattice.Order Methods traverse :: Applicative f => (a -> f b) -> Order a -> f (Order b) # sequenceA :: Applicative f => Order (f a) -> f (Order a) # mapM :: Monad m => (a -> m b) -> Order a -> m (Order b) # sequence :: Monad m => Order (m a) -> m (Order a) #
Bounded a => Bounded (Order a)
Instance details Defined in Data.Semilattice.Order Methods minBound :: Order a # maxBound :: Order a #
Enum a => Enum (Order a)
Instance details Defined in Data.Semilattice.Order Methods succ :: Order a -> Order a # pred :: Order a -> Order a # toEnum :: Int -> Order a # fromEnum :: Order a -> Int # enumFrom :: Order a -> [Order a] # enumFromThen :: Order a -> Order a -> [Order a] # enumFromTo :: Order a -> Order a -> [Order a] # enumFromThenTo :: Order a -> Order a -> Order a -> [Order a] #
Eq a => Eq (Order a)
Instance details Defined in Data.Semilattice.Order Methods (==) :: Order a -> Order a -> Bool # (/=) :: Order a -> Order a -> Bool #
Num a => Num (Order a)
Instance details Defined in Data.Semilattice.Order Methods (+) :: Order a -> Order a -> Order a # (-) :: Order a -> Order a -> Order a # (*) :: Order a -> Order a -> Order a # negate :: Order a -> Order a # abs :: Order a -> Order a # signum :: Order a -> Order a # fromInteger :: Integer -> Order a #
Ord a => Ord (Order a)
Instance details Defined in Data.Semilattice.Order Methods compare :: Order a -> Order a -> Ordering # (<) :: Order a -> Order a -> Bool # (<=) :: Order a -> Order a -> Bool # (>) :: Order a -> Order a -> Bool # (>=) :: Order a -> Order a -> Bool # max :: Order a -> Order a -> Order a # min :: Order a -> Order a -> Order a #
Read a => Read (Order a)
Instance details Defined in Data.Semilattice.Order Methods readsPrec :: Int -> ReadS (Order a) # readList :: ReadS [Order a] # readPrec :: ReadPrec (Order a) # readListPrec :: ReadPrec [Order a] #
Show a => Show (Order a)
Instance details Defined in Data.Semilattice.Order Methods showsPrec :: Int -> Order a -> ShowS # show :: Order a -> String # showList :: [Order a] -> ShowS #
Ord a => Meet (Order a)	Total `Ord`erings give rise to a meet semilattice satisfying: Idempotence: Order x /\ Order x == Order x Associativity: Order a /\ (Order b /\ Order c) == (Order a /\ Order b) /\ Order c Commutativity: Order a /\ Order b == Order b /\ Order a Identity: 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 details Defined in Data.Semilattice.Order Methods (/\) :: Order a -> Order a -> Order a #
Upper a => Upper (Order a)
Instance details Defined in Data.Semilattice.Order Methods upperBound :: Order a #
Ord a => Join (Order a)	Total `Ord`erings give rise to a join semilattice satisfying: Idempotence: Order x \/ Order x == Order x Associativity: Order a \/ (Order b \/ Order c) == (Order a \/ Order b) \/ Order c Commutativity: Order a \/ Order b == Order b \/ Order a Identity: lowerBound \/ Order a == Order (a :: Int) Absorption: upperBound \/ Order a == (upperBound :: Order Int) Distributivity: Order a \/ Order b /\ Order c == (Order a \/ Order b) /\ (Order a \/ Order c)
Instance details Defined in Data.Semilattice.Order Methods (\/) :: Order a -> Order a -> Order a #
Lower a => Lower (Order a)
Instance details Defined in Data.Semilattice.Order Methods lowerBound :: Order a #