lattices 2.0.3 → 2.1
raw patch · 6 files changed
+57/−121 lines, 6 files
Files
- CHANGELOG.md +8/−0
- lattices.cabal +8/−8
- src/Algebra/Lattice.hs +26/−0
- src/Algebra/Lattice/Stacked.hs +0/−100
- src/Algebra/PartialOrd.hs +10/−8
- test/Tests.hs +5/−5
CHANGELOG.md view
@@ -1,3 +1,11 @@+# 2.1 (2022-12-27)++- Fix `comprable` for `PartialOrd (a,b)` instance+- Remove `Stacked`, use `Either` instead for ordinal sum.+ There is no type for disjoint union / parallel composition.+ Open an issue if you need one.+ Terminology is from https://en.wikipedia.org/wiki/Partially_ordered_set#Sums_of_partially_ordered_sets+ # 2.0.3 (2021-10-30) - Add instances for `Solo`
lattices.cabal view
@@ -1,6 +1,6 @@ cabal-version: 1.18 name: lattices-version: 2.0.3+version: 2.1 category: Math license: BSD3 license-file: LICENSE@@ -31,8 +31,9 @@ || ==8.6.5 || ==8.8.3 || ==8.10.4- || ==9.0.1- || ==9.2.1+ || ==9.0.2+ || ==9.2.5+ || ==9.4.4 synopsis: Fine-grained library for constructing and manipulating lattices@@ -67,7 +68,6 @@ Algebra.Lattice.N5 Algebra.Lattice.Op Algebra.Lattice.Ordered- Algebra.Lattice.Stacked Algebra.Lattice.Unicode Algebra.Lattice.Wide Algebra.Lattice.ZeroHalfOne@@ -82,16 +82,16 @@ Algebra.PartialOrd.Instances build-depends:- base >=4.6 && <4.17+ base >=4.6 && <4.18 , base-compat >=0.10.5 && <0.13 , containers >=0.5.0.0 && <0.7 , deepseq >=1.3.0.0 && <1.5- , hashable >=1.2.7.0 && <1.4+ , hashable >=1.2.7.0 && <1.5 , integer-logarithms >=1.0.3 && <1.1 , QuickCheck >=2.12.6.1 && <2.15 , semigroupoids >=5.3.2 && <5.4 , tagged >=0.8.6 && <0.9- , transformers >=0.3.0.0 && <0.6+ , transformers >=0.3.0.0 && <0.7 , universe-base >=1.1 && <1.2 , universe-reverse-instances >=1.1 && <1.2 , unordered-containers >=0.2.8.0 && <0.3@@ -103,7 +103,7 @@ build-depends: OneTuple >=0.3 && <0.4 if !impl(ghc >=8.0)- build-depends: semigroups >=0.18.5 && <0.20+ build-depends: semigroups >=0.18.5 && <0.21 if !impl(ghc >=7.10) build-depends: void >=0.7.2 && <0.8
src/Algebra/Lattice.hs view
@@ -311,6 +311,32 @@ top = (top, top) --+-- Either+--++-- | Ordinal sum.+--+-- @since 2.1+instance (Lattice a, Lattice b) => Lattice (Either a b) where+ Right x \/ Right y = Right (x \/ y)+ u@(Right _) \/ _ = u+ _ \/ u@(Right _) = u+ Left x \/ Left y = Left (x \/ y)++ Left x /\ Left y = Left (x /\ y)+ l@(Left _) /\ _ = l+ _ /\ l@(Left _) = l+ Right x /\ Right y = Right (x /\ y)++-- | @since 2.1+instance (BoundedJoinSemiLattice a, Lattice b) => BoundedJoinSemiLattice (Either a b) where+ bottom = Left bottom++-- | @since 2.1+instance (Lattice a, BoundedMeetSemiLattice b) => BoundedMeetSemiLattice (Either a b) where+ top = Right top++-- -- Bools --
− src/Algebra/Lattice/Stacked.hs
@@ -1,100 +0,0 @@-{-# LANGUAGE DeriveDataTypeable #-}-{-# LANGUAGE DeriveFoldable #-}-{-# LANGUAGE DeriveFunctor #-}-{-# LANGUAGE DeriveGeneric #-}-{-# LANGUAGE DeriveTraversable #-}-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE Safe #-}-{-# LANGUAGE ScopedTypeVariables #-}-{-# LANGUAGE TypeOperators #-}-module Algebra.Lattice.Stacked (- Stacked(..)- , foldStacked- ) where--import Prelude ()-import Prelude.Compat--import Algebra.Lattice-import Algebra.PartialOrd--import Control.DeepSeq (NFData (..))-import Control.Monad (ap, liftM2)-import Data.Data (Data, Typeable)-import Data.Hashable (Hashable (..))-import Data.Universe.Class (Finite (..), Universe (..))-import Data.Universe.Helpers (Natural, Tagged, retag, (+++))-import GHC.Generics (Generic, Generic1)--import qualified Test.QuickCheck as QC------- Stacked------- | Stacked two lattices, one on top of another. All minimal elements of upper lattice cover all maximal elements of lower lattice.-data Stacked a b = Lower a- | Upper b- deriving ( Eq, Ord, Show, Read, Data, Typeable, Generic, Functor, Foldable, Traversable- , Generic1- )--foldStacked :: (l -> r) -> (u -> r) -> Stacked l u -> r-foldStacked f _ (Lower l) = f l-foldStacked _ f (Upper u) = f u--instance Applicative (Stacked a) where- pure = Upper- (<*>) = ap--instance Monad (Stacked a) where- return = pure-- Lower x >>= _ = Lower x- Upper x >>= f = f x--instance (NFData a, NFData b) => NFData (Stacked a b) where- rnf (Upper x) = rnf x- rnf (Lower x) = rnf x--instance (Hashable a, Hashable b) => Hashable (Stacked a b)--instance (PartialOrd a, PartialOrd b) => PartialOrd (Stacked a b) where- leq (Upper x) (Upper y) = leq x y- leq (Upper _) _ = False- leq _ (Upper _) = True- leq (Lower x) (Lower y) = leq x y- comparable (Upper x) (Upper y) = comparable x y- comparable (Upper _) _ = True- comparable _ (Upper _) = True- comparable (Lower x) (Lower y) = comparable x y--instance (Lattice a, Lattice b) => Lattice (Stacked a b) where- Upper x \/ Upper y = Upper (x \/ y)- u@(Upper _) \/ _ = u- _ \/ u@(Upper _) = u- Lower x \/ Lower y = Lower (x \/ y)- Lower x /\ Lower y = Lower (x /\ y)- l@(Lower _) /\ _ = l- _ /\ l@(Lower _) = l- Upper x /\ Upper y = Upper (x /\ y)--instance (BoundedJoinSemiLattice a, Lattice b) => BoundedJoinSemiLattice (Stacked a b) where- bottom = Lower bottom--instance (Lattice a, BoundedMeetSemiLattice b) => BoundedMeetSemiLattice (Stacked a b) where- top = Upper top--instance (Universe a, Universe b) => Universe (Stacked a b) where- universe = (Lower <$> universe) +++ (Upper <$> universe)--instance (Finite a, Finite b) => Finite (Stacked a b) where- universeF = (Lower <$> universe) ++ (Upper <$> universe)- cardinality = liftM2 (+)- (retag (cardinality :: Tagged a Natural))- (retag (cardinality :: Tagged b Natural))--instance (QC.Arbitrary a, QC.Arbitrary b) => QC.Arbitrary (Stacked a b) where- arbitrary = QC.oneof [Upper <$> QC.arbitrary, Lower <$> QC.arbitrary]- shrink (Lower x) = Lower <$> QC.shrink x- shrink (Upper y) = Upper <$> QC.shrink y
src/Algebra/PartialOrd.hs view
@@ -148,17 +148,19 @@ -- ordering is incompatible with the transitivity axiom we require for the derived partial order (x1, y1) `leq` (x2, y2) = x1 `leq` x2 && y1 `leq` y2 - comparable (x1, y1) (x2, y2) = comparable x1 x2 && comparable y1 y2---- | @since 2.0.1+-- | Ordinal sum.+--+-- @since 2.1 instance (PartialOrd a, PartialOrd b) => PartialOrd (Either a b) where- Left x `leq` Left y = leq x y- Right x `leq` Right y = leq x y- leq _ _ = False+ leq (Right x) (Right y) = leq x y+ leq (Right _) _ = False+ leq _ (Right _) = True+ leq (Left x) (Left y) = leq x y - comparable (Left x) (Left y) = comparable x y comparable (Right x) (Right y) = comparable x y- comparable _ _ = False+ comparable (Right _) _ = True+ comparable _ (Right _) = True+ comparable (Left x) (Left y) = comparable x y -- | Least point of a partially ordered monotone function. Checks that the function is monotone. lfpFrom :: PartialOrd a => a -> (a -> a) -> a
test/Tests.hs view
@@ -44,7 +44,6 @@ import qualified Algebra.Lattice.Lifted as U import qualified Algebra.Lattice.Op as Op import qualified Algebra.Lattice.Ordered as O-import qualified Algebra.Lattice.Stacked as S import qualified Algebra.Lattice.Wide as W import Data.HashMap.Lazy (HashMap)@@ -90,11 +89,14 @@ , allLatticeLaws (LBounded Partial Modular) (Proxy :: Proxy (W.Wide Int)) , allLatticeLaws (LBounded Partial NonModular) (Proxy :: Proxy (LO.Lexicographic (Set Bool) (Set Bool))) , allLatticeLaws (LBounded Partial NonModular) (Proxy :: Proxy (LO.Lexicographic M2 M2)) -- non distributive!- , allLatticeLaws (LBounded Partial Distributive) (Proxy :: Proxy (S.Stacked M2 M2))- , allLatticeLaws (LBounded Partial NonModular) (Proxy :: Proxy (S.Stacked M3 N5)) -- non modular, though it takes QC time to find + , allLatticeLaws LNotLattice (Proxy :: Proxy String) + , allLatticeLaws (LBounded Partial Modular) (Proxy :: Proxy (M2, M2))+ , allLatticeLaws (LBounded Partial Distributive) (Proxy :: Proxy (Either M2 M2))+ , allLatticeLaws (LBounded Partial NonModular) (Proxy :: Proxy (Either M3 N5)) -- non modular, though it takes QC time to find+ , allLatticeLaws (LHeyting Total IsBoolean) (Proxy :: Proxy All) , allLatticeLaws (LHeyting Total IsBoolean) (Proxy :: Proxy Any) , allLatticeLaws (LHeyting Partial IsBoolean) (Proxy :: Proxy (Endo Bool)) -- note: it's partial!@@ -122,7 +124,6 @@ , monadLaws "Op" (Proxy1 :: Proxy1 Op.Op) , monadLaws "Ordered" (Proxy1 :: Proxy1 O.Ordered) , monadLaws "Wide" (Proxy1 :: Proxy1 W.Wide)- , monadLaws "Stacked" (Proxy1 :: Proxy1 (S.Stacked N5)) , monadLaws "Heyting.Free" (Proxy1 :: Proxy1 HF.Free) , finiteLaws (Proxy :: Proxy M2)@@ -137,7 +138,6 @@ , finiteLaws (Proxy :: Proxy (L.Levitated OInt8)) , finiteLaws (Proxy :: Proxy (U.Lifted OInt8)) , finiteLaws (Proxy :: Proxy (LO.Lexicographic OInt8 OInt8))- , finiteLaws (Proxy :: Proxy (S.Stacked OInt8 OInt8)) ] type OInt8 = O.Ordered Int8