{-# LANGUAGE DeriveTraversable, GeneralizedNewtypeDeriving #-}
-- | Join semilattices, related to 'Lower' and 'Data.Semilattice.Upper.Upper'.
module Data.Semilattice.Join
( Join(..)
, Joining(..)
, LessThan(..)
) 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.Lower
import Data.Set as Set

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

  infixr 6 \/


-- Prelude

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

-- | Boolean disjunction 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> lowerBound \/ a == (a :: Bool)
--
--   Absorption:
--
--   prop> upperBound \/ a == (upperBound :: Bool)
instance Join 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> lowerBound \/ a == (a :: Ordering)
--
--   Absorption:
--
--   prop> upperBound \/ a == (upperBound :: Ordering)
instance Join Ordering where
  GT \/ :: Ordering -> Ordering -> Ordering
\/ _ = Ordering
GT
  _ \/ GT = Ordering
GT
  LT \/ b :: Ordering
b = Ordering
b
  a :: Ordering
a \/ LT = 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) -> lowerBound \/ a ~= (a :: Int -> Bool)
--
--   Absorption:
--
--   prop> \ (Fn a) -> upperBound \/ a ~= (upperBound :: Int -> Bool)
instance Join b => Join (a -> b) where
  f :: a -> b
f \/ :: (a -> b) -> (a -> b) -> a -> b
\/ g :: a -> b
g = b -> b -> b
forall s. Join 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 least upperBound bound gives rise to a join semilattice.
--
--   Idempotence:
--
--   prop> x \/ x == (x :: Max Int)
--
--   Associativity:
--
--   prop> a \/ (b \/ c) == (a \/ b) \/ (c :: Max Int)
--
--   Commutativity:
--
--   prop> a \/ b == b \/ (a :: Max Int)
--
--   Identity:
--
--   prop> lowerBound \/ a == (a :: Max Int)
--
--   Absorption:
--
--   prop> upperBound \/ a == (upperBound :: Max Int)
instance Ord a => Join (Max a) where
  \/ :: Max a -> Max a -> Max a
(\/) = Max a -> Max a -> Max a
forall a. Semigroup a => a -> a -> a
(<>)


-- containers

-- | IntMap union with 'Join'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))
--
--   Identity:
--
--   prop> lowerBound \/ a == (a :: IntMap (Set Char))
instance Join a => Join (IntMap a) where
  \/ :: IntMap a -> IntMap a -> IntMap a
(\/) = (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
IntMap.unionWith a -> a -> a
forall s. Join s => s -> s -> s
(\/)

-- | IntSet union 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)
--
--   Identity:
--
--   prop> lowerBound \/ a == (a :: IntSet)
instance Join IntSet where
  \/ :: IntSet -> IntSet -> IntSet
(\/) = IntSet -> IntSet -> IntSet
IntSet.union

-- | Map union with 'Join'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))
--
--   Identity:
--
--   prop> lowerBound \/ a == (a :: Map Char (Set Char))
instance (Ord k, Join a) => Join (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. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith a -> a -> a
forall s. Join s => s -> s -> s
(\/)

-- | Set union 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)
--
--   Identity:
--
--   prop> lowerBound \/ a == (a :: Set Char)
instance Ord a => Join (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.union


-- unordered-containers

-- | HashMap union with 'Join'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))
--
--   Identity:
--
--   prop> lowerBound \/ a == (a :: HashMap Char (Set Char))
instance (Eq k, Hashable k, Join a) => Join (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 v.
(Eq k, Hashable k) =>
(v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
HashMap.unionWith a -> a -> a
forall s. Join s => s -> s -> s
(\/)

-- | HashSet union 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)
--
--   Identity:
--
--   prop> lowerBound \/ a == (a :: HashSet Char)
instance (Eq a, Hashable a) => Join (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.union


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

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

-- | 'Joining' 'mempty' is the left- and right-identity.
--
--   prop> \ x -> let (l, r) = (mappend mempty (Joining x), mappend (Joining x) mempty) in l == Joining x && r == Joining (x :: IntSet)
instance (Lower a, Join a) => Monoid (Joining a) where
  mappend :: Joining a -> Joining a -> Joining a
mappend = Joining a -> Joining a -> Joining a
forall a. Semigroup a => a -> a -> a
(<>)
  mempty :: Joining a
mempty = Joining a
forall s. Lower s => s
lowerBound


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

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

  a :: LessThan a
a <= :: LessThan a -> LessThan a -> Bool
<= b :: LessThan a
b = LessThan a
a LessThan a -> LessThan a -> LessThan a
forall s. Join s => s -> s -> s
\/ LessThan a
b LessThan a -> LessThan a -> Bool
forall a. Eq a => a -> a -> Bool
== LessThan a
b


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