{-# LANGUAGE DeriveTraversable, GeneralizedNewtypeDeriving #-}
-- | Join semilattices, related to 'Data.Semilattice.Lower.Lower' and 'Upper'.
module Data.Semilattice.Meet
( Meet(..)
, Meeting(..)
, GreaterThan(..)
) where

import Data.Hashable
import Data.HashMap.Lazy as HashMap
import Data.HashSet as HashSet
import Data.IntMap as IntMap
import Data.IntSet as IntSet
import Data.Map as Map
import Data.Semigroup
import Data.Semilattice.Upper
import Data.Set as Set

-- | A meet semilattice is an idempotent commutative semigroup.
class Meet s where
  -- | 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 'Data.Semilattice.Lower.Lower' bound, then 'Data.Semilattice.Lower.lowerBound' must be its absorbing element:
  --
  -- @
  -- 'Data.Semilattice.Lower.lowerBound' '/\' a = 'Data.Semilattice.Lower.lowerBound'
  -- a '/\' 'Data.Semilattice.Lower.lowerBound' = 'Data.Semilattice.Lower.lowerBound'
  -- @
  (/\) :: s -> s -> s

  infixr 7 /\


-- Prelude

instance Meet () where
  _ /\ :: () -> () -> ()
/\ _ = ()

-- | Boolean conjunction forms a semilattice.
--
--   Idempotence:
--
--   prop> x /\ x == (x :: Bool)
--
--   Associativity:
--
--   prop> a /\ (b /\ c) == (a /\ b) /\ (c :: Bool)
--
--   Commutativity:
--
--   prop> a /\ b == b /\ (a :: Bool)
--
--   Identity:
--
--   prop> upperBound /\ a == (a :: Bool)
--
--   Absorption:
--
--   prop> lowerBound /\ a == (lowerBound :: Bool)
instance Meet Bool where
  /\ :: Bool -> Bool -> Bool
(/\) = Bool -> Bool -> Bool
(&&)

-- | Orderings form a semilattice.
--
--   Idempotence:
--
--   prop> x /\ x == (x :: Ordering)
--
--   Associativity:
--
--   prop> a /\ (b /\ c) == (a /\ b) /\ (c :: Ordering)
--
--   Commutativity:
--
--   prop> a /\ b == b /\ (a :: Ordering)
--
--   Identity:
--
--   prop> upperBound /\ a == (a :: Ordering)
--
--   Absorption:
--
--   prop> lowerBound /\ a == (lowerBound :: Ordering)
instance Meet Ordering where
  LT /\ :: Ordering -> Ordering -> Ordering
/\ _ = Ordering
LT
  _ /\ LT = Ordering
LT
  GT /\ b :: Ordering
b = Ordering
b
  a :: Ordering
a /\ GT = Ordering
a
  _ /\ _ = Ordering
EQ

-- | Functions with semilattice codomains form a semilattice.
--
--   Idempotence:
--
--   prop> \ (Fn x) -> x /\ x ~= (x :: Int -> Bool)
--
--   Associativity:
--
--   prop> \ (Fn a) (Fn b) (Fn c) -> a /\ (b /\ c) ~= (a /\ b) /\ (c :: Int -> Bool)
--
--   Commutativity:
--
--   prop> \ (Fn a) (Fn b) -> a /\ b ~= b /\ (a :: Int -> Bool)
--
--   Identity:
--
--   prop> \ (Fn a) -> upperBound /\ a ~= (a :: Int -> Bool)
--
--   Absorption:
--
--   prop> \ (Fn a) -> lowerBound /\ a ~= (lowerBound :: Int -> Bool)
instance Meet b => Meet (a -> b) where
  f :: a -> b
f /\ :: (a -> b) -> (a -> b) -> a -> b
/\ g :: a -> b
g = b -> b -> b
forall s. Meet s => s -> s -> s
(/\) (b -> b -> b) -> (a -> b) -> a -> b -> b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> b
f (a -> b -> b) -> (a -> b) -> a -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> a -> b
g


-- Data.Semigroup

-- | The greatest lowerBound bound gives rise to a meet semilattice.
--
--   Idempotence:
--
--   prop> x /\ x == (x :: Min Int)
--
--   Associativity:
--
--   prop> a /\ (b /\ c) == (a /\ b) /\ (c :: Min Int)
--
--   Commutativity:
--
--   prop> a /\ b == b /\ (a :: Min Int)
--
--   Identity:
--
--   prop> upperBound /\ a == (a :: Min Int)
--
--   Absorption:
--
--   prop> lowerBound /\ a == (lowerBound :: Min Int)
instance Ord a => Meet (Min a) where
  /\ :: Min a -> Min a -> Min a
(/\) = Min a -> Min a -> Min a
forall a. Semigroup a => a -> a -> a
(<>)


-- containers

-- | IntMap union with 'Meet'able values forms a semilattice.
--
--   Idempotence:
--
--   prop> x /\ x == (x :: IntMap (Set Char))
--
--   Associativity:
--
--   prop> a /\ (b /\ c) == (a /\ b) /\ (c :: IntMap (Set Char))
--
--   Commutativity:
--
--   prop> a /\ b == b /\ (a :: IntMap (Set Char))
--
--   Absorption:
--
--   prop> lowerBound /\ a == (lowerBound :: IntMap (Set Char))
instance Meet a => Meet (IntMap a) where
  /\ :: IntMap a -> IntMap a -> IntMap a
(/\) = (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
forall a b c. (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
IntMap.intersectionWith a -> a -> a
forall s. Meet s => s -> s -> s
(/\)

-- | IntSet intersection forms a semilattice.
--
--   Idempotence:
--
--   prop> x /\ x == (x :: IntSet)
--
--   Associativity:
--
--   prop> a /\ (b /\ c) == (a /\ b) /\ (c :: IntSet)
--
--   Commutativity:
--
--   prop> a /\ b == b /\ (a :: IntSet)
--
--   Absorption:
--
--   prop> lowerBound /\ a == (lowerBound :: IntSet)
instance Meet IntSet where
  /\ :: IntSet -> IntSet -> IntSet
(/\) = IntSet -> IntSet -> IntSet
IntSet.intersection

-- | Map union with 'Meet'able values forms a semilattice.
--
--   Idempotence:
--
--   prop> x /\ x == (x :: Map Char (Set Char))
--
--   Associativity:
--
--   prop> a /\ (b /\ c) == (a /\ b) /\ (c :: Map Char (Set Char))
--
--   Commutativity:
--
--   prop> a /\ b == b /\ (a :: Map Char (Set Char))
--
--   Absorption:
--
--   prop> lowerBound /\ a == (lowerBound :: Map Char (Set Char))
instance (Ord k, Meet a) => Meet (Map k a) where
  /\ :: Map k a -> Map k a -> Map k a
(/\) = (a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a b c.
Ord k =>
(a -> b -> c) -> Map k a -> Map k b -> Map k c
Map.intersectionWith a -> a -> a
forall s. Meet s => s -> s -> s
(/\)

-- | Set intersection forms a semilattice.
--
--   Idempotence:
--
--   prop> x /\ x == (x :: Set Char)
--
--   Associativity:
--
--   prop> a /\ (b /\ c) == (a /\ b) /\ (c :: Set Char)
--
--   Commutativity:
--
--   prop> a /\ b == b /\ (a :: Set Char)
--
--   Absorption:
--
--   prop> lowerBound /\ a == (lowerBound :: Set Char)
instance Ord a => Meet (Set a) where
  /\ :: Set a -> Set a -> Set a
(/\) = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
Set.intersection


-- unordered-containers

-- | HashMap union with 'Meet'able values forms a semilattice.
--
--   Idempotence:
--
--   prop> x /\ x == (x :: HashMap Char (Set Char))
--
--   Associativity:
--
--   prop> a /\ (b /\ c) == (a /\ b) /\ (c :: HashMap Char (Set Char))
--
--   Commutativity:
--
--   prop> a /\ b == b /\ (a :: HashMap Char (Set Char))
--
--   Absorption:
--
--   prop> lowerBound /\ a == (lowerBound :: HashMap Char (Set Char))
instance (Eq k, Hashable k, Meet a) => Meet (HashMap k a) where
  /\ :: HashMap k a -> HashMap k a -> HashMap k a
(/\) = (a -> a -> a) -> HashMap k a -> HashMap k a -> HashMap k a
forall k v1 v2 v3.
(Eq k, Hashable k) =>
(v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3
HashMap.intersectionWith a -> a -> a
forall s. Meet s => s -> s -> s
(/\)

-- | HashSet intersection forms a semilattice.
--
--   Idempotence:
--
--   prop> x /\ x == (x :: HashSet Char)
--
--   Associativity:
--
--   prop> a /\ (b /\ c) == (a /\ b) /\ (c :: HashSet Char)
--
--   Commutativity:
--
--   prop> a /\ b == b /\ (a :: HashSet Char)
--
--   Absorption:
--
--   prop> lowerBound /\ a == (lowerBound :: HashSet Char)
instance (Eq a, Hashable a) => Meet (HashSet a) where
  /\ :: HashSet a -> HashSet a -> HashSet a
(/\) = HashSet a -> HashSet a -> HashSet a
forall a. (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
HashSet.intersection


-- | A 'Semigroup' for any 'Meet' semilattice.
--
--   If the semilattice has an 'Upper' bound, there is additionally a 'Monoid' instance.
newtype Meeting a = Meeting { Meeting a -> a
getMeeting :: a }
  deriving (Meeting a
Meeting a -> Meeting a -> Bounded (Meeting a)
forall a. a -> a -> Bounded a
forall a. Bounded a => Meeting a
maxBound :: Meeting a
$cmaxBound :: forall a. Bounded a => Meeting a
minBound :: Meeting a
$cminBound :: forall a. Bounded a => Meeting a
Bounded, Int -> Meeting a
Meeting a -> Int
Meeting a -> [Meeting a]
Meeting a -> Meeting a
Meeting a -> Meeting a -> [Meeting a]
Meeting a -> Meeting a -> Meeting a -> [Meeting a]
(Meeting a -> Meeting a)
-> (Meeting a -> Meeting a)
-> (Int -> Meeting a)
-> (Meeting a -> Int)
-> (Meeting a -> [Meeting a])
-> (Meeting a -> Meeting a -> [Meeting a])
-> (Meeting a -> Meeting a -> [Meeting a])
-> (Meeting a -> Meeting a -> Meeting a -> [Meeting a])
-> Enum (Meeting a)
forall a. Enum a => Int -> Meeting a
forall a. Enum a => Meeting a -> Int
forall a. Enum a => Meeting a -> [Meeting a]
forall a. Enum a => Meeting a -> Meeting a
forall a. Enum a => Meeting a -> Meeting a -> [Meeting a]
forall a.
Enum a =>
Meeting a -> Meeting a -> Meeting a -> [Meeting a]
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
enumFromThenTo :: Meeting a -> Meeting a -> Meeting a -> [Meeting a]
$cenumFromThenTo :: forall a.
Enum a =>
Meeting a -> Meeting a -> Meeting a -> [Meeting a]
enumFromTo :: Meeting a -> Meeting a -> [Meeting a]
$cenumFromTo :: forall a. Enum a => Meeting a -> Meeting a -> [Meeting a]
enumFromThen :: Meeting a -> Meeting a -> [Meeting a]
$cenumFromThen :: forall a. Enum a => Meeting a -> Meeting a -> [Meeting a]
enumFrom :: Meeting a -> [Meeting a]
$cenumFrom :: forall a. Enum a => Meeting a -> [Meeting a]
fromEnum :: Meeting a -> Int
$cfromEnum :: forall a. Enum a => Meeting a -> Int
toEnum :: Int -> Meeting a
$ctoEnum :: forall a. Enum a => Int -> Meeting a
pred :: Meeting a -> Meeting a
$cpred :: forall a. Enum a => Meeting a -> Meeting a
succ :: Meeting a -> Meeting a
$csucc :: forall a. Enum a => Meeting a -> Meeting a
Enum, Meeting a -> Meeting a -> Bool
(Meeting a -> Meeting a -> Bool)
-> (Meeting a -> Meeting a -> Bool) -> Eq (Meeting a)
forall a. Eq a => Meeting a -> Meeting a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Meeting a -> Meeting a -> Bool
$c/= :: forall a. Eq a => Meeting a -> Meeting a -> Bool
== :: Meeting a -> Meeting a -> Bool
$c== :: forall a. Eq a => Meeting a -> Meeting a -> Bool
Eq, Meeting a -> Bool
(a -> m) -> Meeting a -> m
(a -> b -> b) -> b -> Meeting a -> b
(forall m. Monoid m => Meeting m -> m)
-> (forall m a. Monoid m => (a -> m) -> Meeting a -> m)
-> (forall m a. Monoid m => (a -> m) -> Meeting a -> m)
-> (forall a b. (a -> b -> b) -> b -> Meeting a -> b)
-> (forall a b. (a -> b -> b) -> b -> Meeting a -> b)
-> (forall b a. (b -> a -> b) -> b -> Meeting a -> b)
-> (forall b a. (b -> a -> b) -> b -> Meeting a -> b)
-> (forall a. (a -> a -> a) -> Meeting a -> a)
-> (forall a. (a -> a -> a) -> Meeting a -> a)
-> (forall a. Meeting a -> [a])
-> (forall a. Meeting a -> Bool)
-> (forall a. Meeting a -> Int)
-> (forall a. Eq a => a -> Meeting a -> Bool)
-> (forall a. Ord a => Meeting a -> a)
-> (forall a. Ord a => Meeting a -> a)
-> (forall a. Num a => Meeting a -> a)
-> (forall a. Num a => Meeting a -> a)
-> Foldable Meeting
forall a. Eq a => a -> Meeting a -> Bool
forall a. Num a => Meeting a -> a
forall a. Ord a => Meeting a -> a
forall m. Monoid m => Meeting m -> m
forall a. Meeting a -> Bool
forall a. Meeting a -> Int
forall a. Meeting a -> [a]
forall a. (a -> a -> a) -> Meeting a -> a
forall m a. Monoid m => (a -> m) -> Meeting a -> m
forall b a. (b -> a -> b) -> b -> Meeting a -> b
forall a b. (a -> b -> b) -> b -> Meeting a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: Meeting a -> a
$cproduct :: forall a. Num a => Meeting a -> a
sum :: Meeting a -> a
$csum :: forall a. Num a => Meeting a -> a
minimum :: Meeting a -> a
$cminimum :: forall a. Ord a => Meeting a -> a
maximum :: Meeting a -> a
$cmaximum :: forall a. Ord a => Meeting a -> a
elem :: a -> Meeting a -> Bool
$celem :: forall a. Eq a => a -> Meeting a -> Bool
length :: Meeting a -> Int
$clength :: forall a. Meeting a -> Int
null :: Meeting a -> Bool
$cnull :: forall a. Meeting a -> Bool
toList :: Meeting a -> [a]
$ctoList :: forall a. Meeting a -> [a]
foldl1 :: (a -> a -> a) -> Meeting a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Meeting a -> a
foldr1 :: (a -> a -> a) -> Meeting a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Meeting a -> a
foldl' :: (b -> a -> b) -> b -> Meeting a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Meeting a -> b
foldl :: (b -> a -> b) -> b -> Meeting a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Meeting a -> b
foldr' :: (a -> b -> b) -> b -> Meeting a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Meeting a -> b
foldr :: (a -> b -> b) -> b -> Meeting a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Meeting a -> b
foldMap' :: (a -> m) -> Meeting a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Meeting a -> m
foldMap :: (a -> m) -> Meeting a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Meeting a -> m
fold :: Meeting m -> m
$cfold :: forall m. Monoid m => Meeting m -> m
Foldable, a -> Meeting b -> Meeting a
(a -> b) -> Meeting a -> Meeting b
(forall a b. (a -> b) -> Meeting a -> Meeting b)
-> (forall a b. a -> Meeting b -> Meeting a) -> Functor Meeting
forall a b. a -> Meeting b -> Meeting a
forall a b. (a -> b) -> Meeting a -> Meeting b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Meeting b -> Meeting a
$c<$ :: forall a b. a -> Meeting b -> Meeting a
fmap :: (a -> b) -> Meeting a -> Meeting b
$cfmap :: forall a b. (a -> b) -> Meeting a -> Meeting b
Functor, Meeting a -> Meeting a -> Meeting a
(Meeting a -> Meeting a -> Meeting a) -> Meet (Meeting a)
forall a. Meet a => Meeting a -> Meeting a -> Meeting a
forall s. (s -> s -> s) -> Meet s
/\ :: Meeting a -> Meeting a -> Meeting a
$c/\ :: forall a. Meet a => Meeting a -> Meeting a -> Meeting a
Meet, Integer -> Meeting a
Meeting a -> Meeting a
Meeting a -> Meeting a -> Meeting a
(Meeting a -> Meeting a -> Meeting a)
-> (Meeting a -> Meeting a -> Meeting a)
-> (Meeting a -> Meeting a -> Meeting a)
-> (Meeting a -> Meeting a)
-> (Meeting a -> Meeting a)
-> (Meeting a -> Meeting a)
-> (Integer -> Meeting a)
-> Num (Meeting a)
forall a. Num a => Integer -> Meeting a
forall a. Num a => Meeting a -> Meeting a
forall a. Num a => Meeting a -> Meeting a -> Meeting a
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
fromInteger :: Integer -> Meeting a
$cfromInteger :: forall a. Num a => Integer -> Meeting a
signum :: Meeting a -> Meeting a
$csignum :: forall a. Num a => Meeting a -> Meeting a
abs :: Meeting a -> Meeting a
$cabs :: forall a. Num a => Meeting a -> Meeting a
negate :: Meeting a -> Meeting a
$cnegate :: forall a. Num a => Meeting a -> Meeting a
* :: Meeting a -> Meeting a -> Meeting a
$c* :: forall a. Num a => Meeting a -> Meeting a -> Meeting a
- :: Meeting a -> Meeting a -> Meeting a
$c- :: forall a. Num a => Meeting a -> Meeting a -> Meeting a
+ :: Meeting a -> Meeting a -> Meeting a
$c+ :: forall a. Num a => Meeting a -> Meeting a -> Meeting a
Num, Eq (Meeting a)
Eq (Meeting a) =>
(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)
-> (Meeting a -> Meeting a -> Meeting a)
-> (Meeting a -> Meeting a -> Meeting a)
-> Ord (Meeting a)
Meeting a -> Meeting a -> Bool
Meeting a -> Meeting a -> Ordering
Meeting a -> Meeting a -> Meeting a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (Meeting a)
forall a. Ord a => Meeting a -> Meeting a -> Bool
forall a. Ord a => Meeting a -> Meeting a -> Ordering
forall a. Ord a => Meeting a -> Meeting a -> Meeting a
min :: Meeting a -> Meeting a -> Meeting a
$cmin :: forall a. Ord a => Meeting a -> Meeting a -> Meeting a
max :: Meeting a -> Meeting a -> Meeting a
$cmax :: forall a. Ord a => Meeting a -> Meeting a -> Meeting a
>= :: Meeting a -> Meeting a -> Bool
$c>= :: forall a. Ord a => Meeting a -> Meeting a -> Bool
> :: Meeting a -> Meeting a -> Bool
$c> :: forall a. Ord a => Meeting a -> Meeting a -> Bool
<= :: Meeting a -> Meeting a -> Bool
$c<= :: forall a. Ord a => Meeting a -> Meeting a -> Bool
< :: Meeting a -> Meeting a -> Bool
$c< :: forall a. Ord a => Meeting a -> Meeting a -> Bool
compare :: Meeting a -> Meeting a -> Ordering
$ccompare :: forall a. Ord a => Meeting a -> Meeting a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (Meeting a)
Ord, ReadPrec [Meeting a]
ReadPrec (Meeting a)
Int -> ReadS (Meeting a)
ReadS [Meeting a]
(Int -> ReadS (Meeting a))
-> ReadS [Meeting a]
-> ReadPrec (Meeting a)
-> ReadPrec [Meeting a]
-> Read (Meeting a)
forall a. Read a => ReadPrec [Meeting a]
forall a. Read a => ReadPrec (Meeting a)
forall a. Read a => Int -> ReadS (Meeting a)
forall a. Read a => ReadS [Meeting a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Meeting a]
$creadListPrec :: forall a. Read a => ReadPrec [Meeting a]
readPrec :: ReadPrec (Meeting a)
$creadPrec :: forall a. Read a => ReadPrec (Meeting a)
readList :: ReadS [Meeting a]
$creadList :: forall a. Read a => ReadS [Meeting a]
readsPrec :: Int -> ReadS (Meeting a)
$creadsPrec :: forall a. Read a => Int -> ReadS (Meeting a)
Read, Int -> Meeting a -> ShowS
[Meeting a] -> ShowS
Meeting a -> String
(Int -> Meeting a -> ShowS)
-> (Meeting a -> String)
-> ([Meeting a] -> ShowS)
-> Show (Meeting a)
forall a. Show a => Int -> Meeting a -> ShowS
forall a. Show a => [Meeting a] -> ShowS
forall a. Show a => Meeting a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Meeting a] -> ShowS
$cshowList :: forall a. Show a => [Meeting a] -> ShowS
show :: Meeting a -> String
$cshow :: forall a. Show a => Meeting a -> String
showsPrec :: Int -> Meeting a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Meeting a -> ShowS
Show, Functor Meeting
Foldable Meeting
(Functor Meeting, Foldable Meeting) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> Meeting a -> f (Meeting b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Meeting (f a) -> f (Meeting a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Meeting a -> m (Meeting b))
-> (forall (m :: * -> *) a.
    Monad m =>
    Meeting (m a) -> m (Meeting a))
-> Traversable Meeting
(a -> f b) -> Meeting a -> f (Meeting b)
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Meeting (m a) -> m (Meeting a)
forall (f :: * -> *) a.
Applicative f =>
Meeting (f a) -> f (Meeting a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Meeting a -> m (Meeting b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Meeting a -> f (Meeting b)
sequence :: Meeting (m a) -> m (Meeting a)
$csequence :: forall (m :: * -> *) a. Monad m => Meeting (m a) -> m (Meeting a)
mapM :: (a -> m b) -> Meeting a -> m (Meeting b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Meeting a -> m (Meeting b)
sequenceA :: Meeting (f a) -> f (Meeting a)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
Meeting (f a) -> f (Meeting a)
traverse :: (a -> f b) -> Meeting a -> f (Meeting b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Meeting a -> f (Meeting b)
$cp2Traversable :: Foldable Meeting
$cp1Traversable :: Functor Meeting
Traversable, Meeting a
Meeting a -> Upper (Meeting a)
forall s. s -> Upper s
forall a. Upper a => Meeting a
upperBound :: Meeting a
$cupperBound :: forall a. Upper a => Meeting a
Upper)

-- | 'Meeting' '<>' is associative.
--
--   prop> Meeting a <> (Meeting b <> Meeting c) == (Meeting a <> Meeting b) <> Meeting (c :: IntSet)
instance Meet a => Semigroup (Meeting a) where
  <> :: Meeting a -> Meeting a -> Meeting a
(<>) = Meeting a -> Meeting a -> Meeting a
forall s. Meet s => s -> s -> s
(/\)

-- | 'Meeting' 'mempty' is the left- and right-identity.
--
--   prop> let (l, r) = (mappend mempty (Meeting x), mappend (Meeting x) mempty) in l == Meeting x && r == Meeting (x :: Bool)
instance (Upper a, Meet a) => Monoid (Meeting a) where
  mappend :: Meeting a -> Meeting a -> Meeting a
mappend = Meeting a -> Meeting a -> Meeting a
forall a. Semigroup a => a -> a -> a
(<>)
  mempty :: Meeting a
mempty = Meeting a
forall s. Upper s => s
upperBound


-- | 'Meet' semilattices give rise to a partial 'Ord'ering.
newtype GreaterThan a = GreaterThan { GreaterThan a -> a
getGreaterThan :: a }
  deriving (Int -> GreaterThan a
GreaterThan a -> Int
GreaterThan a -> [GreaterThan a]
GreaterThan a -> GreaterThan a
GreaterThan a -> GreaterThan a -> [GreaterThan a]
GreaterThan a -> GreaterThan a -> GreaterThan a -> [GreaterThan a]
(GreaterThan a -> GreaterThan a)
-> (GreaterThan a -> GreaterThan a)
-> (Int -> GreaterThan a)
-> (GreaterThan a -> Int)
-> (GreaterThan a -> [GreaterThan a])
-> (GreaterThan a -> GreaterThan a -> [GreaterThan a])
-> (GreaterThan a -> GreaterThan a -> [GreaterThan a])
-> (GreaterThan a
    -> GreaterThan a -> GreaterThan a -> [GreaterThan a])
-> Enum (GreaterThan a)
forall a. Enum a => Int -> GreaterThan a
forall a. Enum a => GreaterThan a -> Int
forall a. Enum a => GreaterThan a -> [GreaterThan a]
forall a. Enum a => GreaterThan a -> GreaterThan a
forall a.
Enum a =>
GreaterThan a -> GreaterThan a -> [GreaterThan a]
forall a.
Enum a =>
GreaterThan a -> GreaterThan a -> GreaterThan a -> [GreaterThan a]
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
enumFromThenTo :: GreaterThan a -> GreaterThan a -> GreaterThan a -> [GreaterThan a]
$cenumFromThenTo :: forall a.
Enum a =>
GreaterThan a -> GreaterThan a -> GreaterThan a -> [GreaterThan a]
enumFromTo :: GreaterThan a -> GreaterThan a -> [GreaterThan a]
$cenumFromTo :: forall a.
Enum a =>
GreaterThan a -> GreaterThan a -> [GreaterThan a]
enumFromThen :: GreaterThan a -> GreaterThan a -> [GreaterThan a]
$cenumFromThen :: forall a.
Enum a =>
GreaterThan a -> GreaterThan a -> [GreaterThan a]
enumFrom :: GreaterThan a -> [GreaterThan a]
$cenumFrom :: forall a. Enum a => GreaterThan a -> [GreaterThan a]
fromEnum :: GreaterThan a -> Int
$cfromEnum :: forall a. Enum a => GreaterThan a -> Int
toEnum :: Int -> GreaterThan a
$ctoEnum :: forall a. Enum a => Int -> GreaterThan a
pred :: GreaterThan a -> GreaterThan a
$cpred :: forall a. Enum a => GreaterThan a -> GreaterThan a
succ :: GreaterThan a -> GreaterThan a
$csucc :: forall a. Enum a => GreaterThan a -> GreaterThan a
Enum, GreaterThan a -> GreaterThan a -> Bool
(GreaterThan a -> GreaterThan a -> Bool)
-> (GreaterThan a -> GreaterThan a -> Bool) -> Eq (GreaterThan a)
forall a. Eq a => GreaterThan a -> GreaterThan a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: GreaterThan a -> GreaterThan a -> Bool
$c/= :: forall a. Eq a => GreaterThan a -> GreaterThan a -> Bool
== :: GreaterThan a -> GreaterThan a -> Bool
$c== :: forall a. Eq a => GreaterThan a -> GreaterThan a -> Bool
Eq, GreaterThan a -> Bool
(a -> m) -> GreaterThan a -> m
(a -> b -> b) -> b -> GreaterThan a -> b
(forall m. Monoid m => GreaterThan m -> m)
-> (forall m a. Monoid m => (a -> m) -> GreaterThan a -> m)
-> (forall m a. Monoid m => (a -> m) -> GreaterThan a -> m)
-> (forall a b. (a -> b -> b) -> b -> GreaterThan a -> b)
-> (forall a b. (a -> b -> b) -> b -> GreaterThan a -> b)
-> (forall b a. (b -> a -> b) -> b -> GreaterThan a -> b)
-> (forall b a. (b -> a -> b) -> b -> GreaterThan a -> b)
-> (forall a. (a -> a -> a) -> GreaterThan a -> a)
-> (forall a. (a -> a -> a) -> GreaterThan a -> a)
-> (forall a. GreaterThan a -> [a])
-> (forall a. GreaterThan a -> Bool)
-> (forall a. GreaterThan a -> Int)
-> (forall a. Eq a => a -> GreaterThan a -> Bool)
-> (forall a. Ord a => GreaterThan a -> a)
-> (forall a. Ord a => GreaterThan a -> a)
-> (forall a. Num a => GreaterThan a -> a)
-> (forall a. Num a => GreaterThan a -> a)
-> Foldable GreaterThan
forall a. Eq a => a -> GreaterThan a -> Bool
forall a. Num a => GreaterThan a -> a
forall a. Ord a => GreaterThan a -> a
forall m. Monoid m => GreaterThan m -> m
forall a. GreaterThan a -> Bool
forall a. GreaterThan a -> Int
forall a. GreaterThan a -> [a]
forall a. (a -> a -> a) -> GreaterThan a -> a
forall m a. Monoid m => (a -> m) -> GreaterThan a -> m
forall b a. (b -> a -> b) -> b -> GreaterThan a -> b
forall a b. (a -> b -> b) -> b -> GreaterThan a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: GreaterThan a -> a
$cproduct :: forall a. Num a => GreaterThan a -> a
sum :: GreaterThan a -> a
$csum :: forall a. Num a => GreaterThan a -> a
minimum :: GreaterThan a -> a
$cminimum :: forall a. Ord a => GreaterThan a -> a
maximum :: GreaterThan a -> a
$cmaximum :: forall a. Ord a => GreaterThan a -> a
elem :: a -> GreaterThan a -> Bool
$celem :: forall a. Eq a => a -> GreaterThan a -> Bool
length :: GreaterThan a -> Int
$clength :: forall a. GreaterThan a -> Int
null :: GreaterThan a -> Bool
$cnull :: forall a. GreaterThan a -> Bool
toList :: GreaterThan a -> [a]
$ctoList :: forall a. GreaterThan a -> [a]
foldl1 :: (a -> a -> a) -> GreaterThan a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> GreaterThan a -> a
foldr1 :: (a -> a -> a) -> GreaterThan a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> GreaterThan a -> a
foldl' :: (b -> a -> b) -> b -> GreaterThan a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> GreaterThan a -> b
foldl :: (b -> a -> b) -> b -> GreaterThan a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> GreaterThan a -> b
foldr' :: (a -> b -> b) -> b -> GreaterThan a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> GreaterThan a -> b
foldr :: (a -> b -> b) -> b -> GreaterThan a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> GreaterThan a -> b
foldMap' :: (a -> m) -> GreaterThan a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> GreaterThan a -> m
foldMap :: (a -> m) -> GreaterThan a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> GreaterThan a -> m
fold :: GreaterThan m -> m
$cfold :: forall m. Monoid m => GreaterThan m -> m
Foldable, a -> GreaterThan b -> GreaterThan a
(a -> b) -> GreaterThan a -> GreaterThan b
(forall a b. (a -> b) -> GreaterThan a -> GreaterThan b)
-> (forall a b. a -> GreaterThan b -> GreaterThan a)
-> Functor GreaterThan
forall a b. a -> GreaterThan b -> GreaterThan a
forall a b. (a -> b) -> GreaterThan a -> GreaterThan b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> GreaterThan b -> GreaterThan a
$c<$ :: forall a b. a -> GreaterThan b -> GreaterThan a
fmap :: (a -> b) -> GreaterThan a -> GreaterThan b
$cfmap :: forall a b. (a -> b) -> GreaterThan a -> GreaterThan b
Functor, GreaterThan a -> GreaterThan a -> GreaterThan a
(GreaterThan a -> GreaterThan a -> GreaterThan a)
-> Meet (GreaterThan a)
forall a. Meet a => GreaterThan a -> GreaterThan a -> GreaterThan a
forall s. (s -> s -> s) -> Meet s
/\ :: GreaterThan a -> GreaterThan a -> GreaterThan a
$c/\ :: forall a. Meet a => GreaterThan a -> GreaterThan a -> GreaterThan a
Meet, Integer -> GreaterThan a
GreaterThan a -> GreaterThan a
GreaterThan a -> GreaterThan a -> GreaterThan a
(GreaterThan a -> GreaterThan a -> GreaterThan a)
-> (GreaterThan a -> GreaterThan a -> GreaterThan a)
-> (GreaterThan a -> GreaterThan a -> GreaterThan a)
-> (GreaterThan a -> GreaterThan a)
-> (GreaterThan a -> GreaterThan a)
-> (GreaterThan a -> GreaterThan a)
-> (Integer -> GreaterThan a)
-> Num (GreaterThan a)
forall a. Num a => Integer -> GreaterThan a
forall a. Num a => GreaterThan a -> GreaterThan a
forall a. Num a => GreaterThan a -> GreaterThan a -> GreaterThan a
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
fromInteger :: Integer -> GreaterThan a
$cfromInteger :: forall a. Num a => Integer -> GreaterThan a
signum :: GreaterThan a -> GreaterThan a
$csignum :: forall a. Num a => GreaterThan a -> GreaterThan a
abs :: GreaterThan a -> GreaterThan a
$cabs :: forall a. Num a => GreaterThan a -> GreaterThan a
negate :: GreaterThan a -> GreaterThan a
$cnegate :: forall a. Num a => GreaterThan a -> GreaterThan a
* :: GreaterThan a -> GreaterThan a -> GreaterThan a
$c* :: forall a. Num a => GreaterThan a -> GreaterThan a -> GreaterThan a
- :: GreaterThan a -> GreaterThan a -> GreaterThan a
$c- :: forall a. Num a => GreaterThan a -> GreaterThan a -> GreaterThan a
+ :: GreaterThan a -> GreaterThan a -> GreaterThan a
$c+ :: forall a. Num a => GreaterThan a -> GreaterThan a -> GreaterThan a
Num, ReadPrec [GreaterThan a]
ReadPrec (GreaterThan a)
Int -> ReadS (GreaterThan a)
ReadS [GreaterThan a]
(Int -> ReadS (GreaterThan a))
-> ReadS [GreaterThan a]
-> ReadPrec (GreaterThan a)
-> ReadPrec [GreaterThan a]
-> Read (GreaterThan a)
forall a. Read a => ReadPrec [GreaterThan a]
forall a. Read a => ReadPrec (GreaterThan a)
forall a. Read a => Int -> ReadS (GreaterThan a)
forall a. Read a => ReadS [GreaterThan a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [GreaterThan a]
$creadListPrec :: forall a. Read a => ReadPrec [GreaterThan a]
readPrec :: ReadPrec (GreaterThan a)
$creadPrec :: forall a. Read a => ReadPrec (GreaterThan a)
readList :: ReadS [GreaterThan a]
$creadList :: forall a. Read a => ReadS [GreaterThan a]
readsPrec :: Int -> ReadS (GreaterThan a)
$creadsPrec :: forall a. Read a => Int -> ReadS (GreaterThan a)
Read, Int -> GreaterThan a -> ShowS
[GreaterThan a] -> ShowS
GreaterThan a -> String
(Int -> GreaterThan a -> ShowS)
-> (GreaterThan a -> String)
-> ([GreaterThan a] -> ShowS)
-> Show (GreaterThan a)
forall a. Show a => Int -> GreaterThan a -> ShowS
forall a. Show a => [GreaterThan a] -> ShowS
forall a. Show a => GreaterThan a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [GreaterThan a] -> ShowS
$cshowList :: forall a. Show a => [GreaterThan a] -> ShowS
show :: GreaterThan a -> String
$cshow :: forall a. Show a => GreaterThan a -> String
showsPrec :: Int -> GreaterThan a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> GreaterThan a -> ShowS
Show, Functor GreaterThan
Foldable GreaterThan
(Functor GreaterThan, Foldable GreaterThan) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> GreaterThan a -> f (GreaterThan b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    GreaterThan (f a) -> f (GreaterThan a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> GreaterThan a -> m (GreaterThan b))
-> (forall (m :: * -> *) a.
    Monad m =>
    GreaterThan (m a) -> m (GreaterThan a))
-> Traversable GreaterThan
(a -> f b) -> GreaterThan a -> f (GreaterThan b)
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
GreaterThan (m a) -> m (GreaterThan a)
forall (f :: * -> *) a.
Applicative f =>
GreaterThan (f a) -> f (GreaterThan a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> GreaterThan a -> m (GreaterThan b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> GreaterThan a -> f (GreaterThan b)
sequence :: GreaterThan (m a) -> m (GreaterThan a)
$csequence :: forall (m :: * -> *) a.
Monad m =>
GreaterThan (m a) -> m (GreaterThan a)
mapM :: (a -> m b) -> GreaterThan a -> m (GreaterThan b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> GreaterThan a -> m (GreaterThan b)
sequenceA :: GreaterThan (f a) -> f (GreaterThan a)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
GreaterThan (f a) -> f (GreaterThan a)
traverse :: (a -> f b) -> GreaterThan a -> f (GreaterThan b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> GreaterThan a -> f (GreaterThan b)
$cp2Traversable :: Foldable GreaterThan
$cp1Traversable :: Functor GreaterThan
Traversable)

-- | NB: This is not in general a total ordering.
instance (Eq a, Meet a) => Ord (GreaterThan a) where
  compare :: GreaterThan a -> GreaterThan a -> Ordering
compare a :: GreaterThan a
a b :: GreaterThan a
b
    | GreaterThan a
a GreaterThan a -> GreaterThan a -> Bool
forall a. Eq a => a -> a -> Bool
== GreaterThan a
b      = Ordering
EQ
    | GreaterThan a
a GreaterThan a -> GreaterThan a -> GreaterThan a
forall s. Meet s => s -> s -> s
/\ GreaterThan a
b GreaterThan a -> GreaterThan a -> Bool
forall a. Eq a => a -> a -> Bool
== GreaterThan a
a = Ordering
LT
    | Bool
otherwise   = Ordering
GT

  a :: GreaterThan a
a <= :: GreaterThan a -> GreaterThan a -> Bool
<= b :: GreaterThan a
b = GreaterThan a
a GreaterThan a -> GreaterThan a -> GreaterThan a
forall s. Meet s => s -> s -> s
/\ GreaterThan a
b GreaterThan a -> GreaterThan a -> Bool
forall a. Eq a => a -> a -> Bool
== GreaterThan a
a


-- $setup
-- >>> import Data.Semilattice.Lower
-- >>> import Test.QuickCheck
-- >>> import Test.QuickCheck.Function
-- >>> import Test.QuickCheck.Instances.UnorderedContainers ()
-- >>> instance Arbitrary a => Arbitrary (Min a) where arbitrary = Min <$> arbitrary
-- >>> :{
-- infix 4 ~=
-- f ~= g = (==) <$> f <*> g
-- :}