finitary 1.1.0.1 → 1.2.0.0

raw patch · 5 files changed

+61/−205 lines, 5 filesdep −mtldep ~basedep ~template-haskellPVP ok

version bump matches the API change (PVP)

Dependencies removed: mtl

Dependency ranges changed: base, template-haskell

API changes (from Hackage documentation)

Files

• CHANGELOG.md +7/−2
• README.md +6/−5
• finitary.cabal +6/−6
• src/Data/Finitary.hs +41/−169
• test/Main.hs +1/−23

@@ -1,8 +1,13 @@ # Revision history for finitary -## 1.1.0.1 -- 2019-09-21+## 1.2.0.0 -- 2019-10-17 -* Fix bug tracker link in Cabal file (no code changes).+* Remove ``nextSkipping`` and ``previousSkipping`` as unnecessary.+* Add (and note) support for GHC 8.2.2.+* Remove MTL dependency.+* Remove ``enumerate*`` class methods.+* Add ``inhabitants``, ``inhabitantsFrom``, ``inhabitantsTo``,+  ``inhabitantsFromTo``.  ## 1.1.0.0 -- 2019-09-21 

@@ -82,12 +82,13 @@  Aside from cardinality, we also inherently get the ability to: -* Have a 'starting' and 'ending' value-* Get the 'next' or 'previous' value, or report that it doesn't exist-* Enumerate ranges of these values+* Have a 'starting' and 'ending' value (assuming the cardinality of the type+  isn't zero); and+* Get the 'next' or 'previous' value, or report that it doesn't exist.  All of this is safe, total and can be relied upon. Check out the documentation-for more details - all of this functionality is provided.+for more details - all of this functionality is provided. We also have functions+to help enumerate values of ``Finitary`` types.  #### But what about auto-derivation? @@ -134,7 +135,7 @@ ## What will this work on?  Currently, we have tested ``finitary`` (meaning 'run tests, not just compiled')-on GHC 8.4.4, GHC 8.6.5 and GHC 8.8.1. If you would like any additional versions +on GHCs 8.2.2, 8.4.4, 8.6.5 and 8.8.1. If you would like any additional versions  supported, please let us know.  So far, the tests have all been on x86_64 GNU/Linux. If you have results on

@@ -3,7 +3,7 @@ -- PVP summary:        +-+------- breaking API changes --                     | | +----- non-breaking API additions --                     | | | +--- code changes with no API change-version:               1.1.0.1+version:               1.2.0.0 synopsis:              A better, more type-safe Enum. description:           Provides a type class witnessing that a type has                        finitely-many inhabitants, as well as its cardinality.@@ -11,7 +11,7 @@                        Generics, together with a range of instances for existing                        types. homepage:              https://notabug.org/koz.ross/finitary-bug-reports:           https://notabug.org/koz.ross/finitary/issues+bug-reports:           https://notabug.org/koz/ross/finitary/issues license:               GPL-3.0-or-later license-file:          LICENSE.md author:                Koz Ross@@ -21,7 +21,8 @@ build-type:            Simple tested-with:           GHC == 8.8.1,                        GHC == 8.6.5, -                       GHC == 8.4.4+                       GHC == 8.4.4,+                       GHC == 8.2.2 extra-source-files:    CHANGELOG.md,                        README.md,                        LICENSE.md@@ -33,14 +34,13 @@ library   exposed-modules:     Data.Finitary   other-modules:       Data.Finitary.TH-  build-depends:       base >= 4.11 && < 4.14,+  build-depends:       base >= 4.10 && < 4.14,                        finite-typelits >= 0.1.4.2 && < 0.2.0.0,                        coercible-utils >= 0.0.0 && < 1.0.0,                        ghc-typelits-knownnat >= 0.7 && < 0.8,                        ghc-typelits-natnormalise >= 0.7 && < 0.8,                        vector-sized >= 1.4.0.0 && < 1.5.0.0,-                       mtl >= 2.2.2 && < 2.3.0,-                       template-haskell >= 2.13.0.0 && < 2.16.0.0,+                       template-haskell >= 2.12.0.0 && < 2.16.0.0,                        bitvec >= 1.0.0.1 && < 1.2.0.0,                        primitive >= 0.6.4.0 && < 0.8.0.0,                        vector >= 0.12.0.3 && < 0.13.0.0,

@@ -45,8 +45,9 @@ -- Stability:     Experimental -- Portability:   GHC only ----- This package provides the 'Finitary' type class, as well as a range of useful--- \'base\' instances for commonly-used finitary types. +-- This package provides the 'Finitary' type class, a range of useful+-- \'base\' instances for commonly-used finitary types, and some helper+-- functions for enumerating values of types with 'Finitary' instances.  -- -- For your own types, there are three possible ways to define an instance of -- 'Finitary':@@ -83,9 +84,12 @@ -- the laws! -- module Data.Finitary (-Finitary(..)+  Finitary(..),+  -- * Enumeration functions+  inhabitants, inhabitantsFrom, inhabitantsTo, inhabitantsFromTo ) where +import Data.List.NonEmpty (NonEmpty(..)) import Data.Bifunctor (bimap, first) import Numeric.Natural (Natural) import Data.Semigroup (Max, Min, Sum, Product, Dual, Last, First, Any, All)@@ -100,7 +104,7 @@ import Control.Applicative (Alternative(..), Const) import Data.Kind (Type) import GHC.TypeNats-import Data.Finite (Finite, separateSum, separateProduct, combineProduct, weakenN, shiftN)+import Data.Finite (Finite, finites, separateSum, separateProduct, combineProduct, weakenN, shiftN) import Data.Ord (Down(..)) import Control.Monad.Primitive (PrimMonad(..)) import Control.Monad (forM_, join)@@ -109,6 +113,7 @@ import Control.Monad.ST (ST, runST) import Foreign.Storable (Storable) +import qualified Data.List.NonEmpty as NE import qualified Data.Bit as B import qualified Data.Bit.ThreadSafe as BTS import qualified Data.Vector.Sized as VS@@ -159,20 +164,8 @@ --    * \[ a \neq \emptyset \rightarrow \texttt{end} = \texttt{fromFinite} \; \texttt{maxBound} \] --    * \[ \forall x :: a \; \texttt{end} \neq x \rightarrow \texttt{next} \; x = -- (\texttt{fromFinite} \circ + 1 \circ \texttt{toFinite}) \; x \]---    * \[ \forall i :: \texttt{Finite} \; (\texttt{Cardinality} \; a) \; \texttt{nextSkipping} \; i =---    \underbrace{\texttt{next} \circ \ldots \circ \texttt{next}}_{i} \] --    * \[ \forall x :: a \; \texttt{start} \neq x \rightarrow \texttt{previous} \; x = -- (\texttt{fromFinite} \circ - 1 \circ \texttt{toFinite}) \; x \]---    * \[ \forall i :: \texttt{Finite} \; (\texttt{Cardinality} \; a) \;---    \texttt{previousSkipping} \; i = \underbrace{\texttt{previous} \circ---    \ldots \circ \texttt{previous}}_{i} \] ---    * \[ \forall x :: a \; \texttt{enumerateFrom} \; x = \texttt{fromFinite <\$> [toFinite} \; x \texttt{..]} \]---    * \[ \forall x, y :: a \; \texttt{enumerateFromThen} \; x y =---    \texttt{fromFinite <\$> [toFinite} \; x \texttt{, }\; y \texttt{..]} \]---    * \[ \forall x, y :: a \; \texttt{enumerateFromTo} \; x \; y =---    \texttt{fromFinite <\$> [toFinite} \; x \texttt{..} \; y \texttt{]} \]---    * \[ \forall x, y, z :: a \; \texttt{enumerateFromThenTo} \; x \; y \; z =---    \texttt{fromFinite <\$> [toFinite} \; x \texttt{,} \; y \texttt{..} \; z \texttt{]} \]  --  -- Together with the fact that @Finite n@ is well-ordered whenever @KnownNat n@ -- holds, a law-abiding @Finitary@ instance for a type @a@ defines a constructive@@ -209,37 +202,10 @@   -- or 'empty' if no such index exists.   previous :: (Alternative f) => a -> f a   previous = fmap fromFinite . guarded (/= maxBound) . dec . toFinite-  -- | @previousSkipping i x@ \'skips back\' @i@ index values from the index of-  -- @x@, then gives the inhabitant whose index precedes the result, or 'empty'-  -- if no such index exists.-  previousSkipping :: (Alternative f) => Finite (Cardinality a) -> a -> f a-  previousSkipping i x = fmap fromFinite . guarded (> index) . subtract i $ index-    where index = toFinite x   -- | @next x@ gives the inhabitant whose index follows the index of @x@, or   -- 'empty' if no such index exists.   next :: (Alternative f) => a -> f a   next = fmap fromFinite . guarded (/= minBound) . inc . toFinite-  -- | @nextSkipping i x@ \'skips forward\' @i@ index values from the index of-  -- @x@, then gives the inhabitant whose index follows the result, or 'empty'-  -- if no such index exists.-  nextSkipping :: (Alternative f) => Finite (Cardinality a) -> a -> f a-  nextSkipping i x = fmap fromFinite . guarded (< index) . (+ i) $ index-    where index = toFinite x-  -- | @enumerateFrom x@ gives a list of inhabitants, starting with @x@,-  -- followed by all other values whose indexes follow @x@, in index order.-  enumerateFrom :: a -> [a]-  enumerateFrom x = fromFinite <$> [toFinite x ..]-  -- | Like @enumerateFrom@, except in steps of @toFinite y - toFinite x@.-  enumerateFromThen :: a -> a -> [a]-  enumerateFromThen x y = fromFinite <$> [toFinite x, toFinite y ..]-  -- | @enumerateFromTo x y@ gives a list of inhabitants, starting with @x@,-  -- ending with @y@, and containing all other values whose indices lie between-  -- those of @x@ and @y@. The list is in index order.-  enumerateFromTo :: a -> a -> [a]-  enumerateFromTo x y = fromFinite <$> [toFinite x .. toFinite y]-  -- | Like @enumerateFromTo@, except in steps of @toFinite y - toFinite x@.-  enumerateFromThenTo :: a -> a -> a -> [a]-  enumerateFromThenTo x y z = fromFinite <$> [toFinite x, toFinite y .. toFinite z]  class (KnownNat (GCardinality a)) => GFinitary (a :: Type -> Type) where   type GCardinality a :: Nat@@ -319,14 +285,6 @@   next = fmap succ . guarded (== minBound)   {-# INLINE previous #-}   previous = fmap pred . guarded (== maxBound)-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary BTS.Bit where   type Cardinality BTS.Bit = 2@@ -342,14 +300,6 @@   next = fmap succ . guarded (== minBound)   {-# INLINE previous #-}   previous = fmap pred . guarded (== maxBound)-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary Ordering @@ -368,16 +318,6 @@   next = fmap succ . guarded (/= maxBound)   {-# INLINE previous #-}   previous = fmap pred . guarded (/= minBound)-  {-# INLINE previousSkipping #-}-  previousSkipping i = fmap toEnum . guarded (>= 0) . subtract (fromIntegral i) . fromEnum-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary Word8 where   type Cardinality Word8 = $(cardinalityOf @Word8)@@ -393,16 +333,6 @@   next = fmap succ . guarded (/= maxBound)   {-# INLINE previous #-}   previous = fmap pred . guarded (/= minBound)-  {-# INLINE previousSkipping #-}-  previousSkipping i = fmap fromIntegral . guarded (>= 0) . subtract (fromIntegral i) . fromIntegral @_ @Int-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary Word16 where   type Cardinality Word16 = $(cardinalityOf @Word16)@@ -418,16 +348,6 @@   next = fmap succ . guarded (/= maxBound)   {-# INLINE previous #-}   previous = fmap pred . guarded (/= minBound)-  {-# INLINE previousSkipping #-}-  previousSkipping i = fmap fromIntegral . guarded (>= 0) . subtract (fromIntegral i) . fromIntegral @_ @Int-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary Word32 where   type Cardinality Word32 = $(cardinalityOf @Word32)@@ -443,16 +363,6 @@   next = guarded (== minBound) . inc   {-# INLINE previous #-}   previous = guarded (== maxBound) . dec-  {-# INLINE previousSkipping #-}-  previousSkipping i = fmap fromIntegral . guarded (>= 0) . subtract (fromIntegral i) . fromIntegral @_ @Integer-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary Word64 where   type Cardinality Word64 = $(cardinalityOf @Word64)@@ -468,16 +378,6 @@   next = guarded (== minBound) . inc   {-# INLINE previous #-}   previous = guarded (== maxBound) . dec-  {-# INLINE previousSkipping #-}-  previousSkipping i = fmap fromIntegral . guarded (>= 0) . subtract (fromIntegral i) . fromIntegral @_ @Integer-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary Int8 where   type Cardinality Int8 = $(cardinalityOf @Int8)@@ -493,14 +393,6 @@   next = fmap succ . guarded (/= maxBound)   {-# INLINE previous #-}   previous = fmap pred . guarded (/= minBound)-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary Int16 where   type Cardinality Int16 = $(cardinalityOf @Int16)@@ -516,14 +408,6 @@   next = fmap succ . guarded (/= maxBound)   {-# INLINE previous #-}   previous = fmap pred . guarded (/= minBound)-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary Int32 where   type Cardinality Int32 = $(cardinalityOf @Int32)@@ -539,14 +423,6 @@   next = guarded (== minBound) . inc   {-# INLINE previous #-}   previous = guarded (== maxBound) . dec-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  instance Finitary Int64 where   type Cardinality Int64 = $(cardinalityOf @Int64)@@ -562,14 +438,6 @@   next = guarded (== minBound) . inc   {-# INLINE previous #-}   previous = guarded (== maxBound) . dec-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  -- Variable-width instances @@ -589,14 +457,6 @@   next = guarded (== minBound) . inc   {-# INLINE previous #-}   previous = guarded (== maxBound) . dec-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  -- | 'Word' has a finite number of inhabitants, varying by platform. This -- instance will determine this when the library is built.@@ -614,16 +474,6 @@   next = guarded (== minBound) . inc   {-# INLINE previous #-}   previous = guarded (== maxBound) . dec-  {-# INLINE previousSkipping #-}-  previousSkipping i = fmap fromIntegral . guarded (>= 0) . subtract (fromIntegral i) . fromIntegral @_ @Integer-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  -- | Since any type is isomorphic to itself, it follows that a \'valid\' @Finite -- n@ (meaning that @n@ is a 'KnownNat') has finite cardinality.@@ -641,16 +491,6 @@   next = guarded (== minBound) . inc   {-# INLINE previous #-}   previous = guarded (== maxBound) . dec-  {-# INLINE previousSkipping #-}-  previousSkipping i = guarded (< i) . subtract i-  {-# INLINE enumerateFrom #-}-  enumerateFrom = enumFrom-  {-# INLINE enumerateFromThen #-}-  enumerateFromThen = enumFromThen-  {-# INLINE enumerateFromTo #-}-  enumerateFromTo = enumFromTo-  {-# INLINE enumerateFromThenTo #-}-  enumerateFromThenTo = enumFromThenTo  -- | @Maybe a@ introduces one additional inhabitant (namely, 'Nothing') to @a@. instance (Finitary a) => Finitary (Maybe a)@@ -743,11 +583,43 @@   {-# INLINE toFinite #-}   toFinite = roll +-- * Enumeration helpers++-- | Produce every inhabitant of @a@, in ascending order of indexes.+-- If you want descending order, use @Down a@ instead.+{-# INLINE inhabitants #-}+inhabitants :: forall (a :: Type) . (Finitary a) => [a]+inhabitants = fromFinite <$> finites++-- | Produce every inhabitant of @a@, starting with the argument, in ascending+-- order of indexes.+-- If you want descending order, use @Down a@ instead.+{-# INLINE inhabitantsFrom #-}+inhabitantsFrom :: forall (a :: Type) . (Finitary a) => a -> NonEmpty a+inhabitantsFrom x = x :| concatMap @Maybe (fmap fromFinite . enumFrom . toFinite) (next x) ++-- | Produce every inhabitant of @a@, up to and including the argument, in+-- ascending order of indexes.+-- If you want descending order, use @Down a@ instead.+{-# INLINE inhabitantsTo #-}+inhabitantsTo :: forall (a :: Type) . (Finitary a) => a -> NonEmpty a+inhabitantsTo x = NE.fromList (fromFinite <$> [0 .. toFinite x]) ++-- | Produce every inhabitant of @a@, starting with the first argument, up to+-- the second argument, in ascending order of indexes. @inhabitantsFromTo x y@+-- will produce the empty list if @toFinite x > toFinite y@.+-- If you want descending order, use @Down a@ instead.+{-# INLINE inhabitantsFromTo #-}+inhabitantsFromTo :: forall (a :: Type) . (Finitary a) => a -> a -> [a]+inhabitantsFromTo lo hi = fromFinite <$> [toFinite lo .. toFinite hi]+ -- Helpers +{-# INLINE combineProduct' #-} combineProduct' :: forall n m . (KnownNat n, KnownNat m) => (Finite n, Finite m) -> Finite (n * m) combineProduct' = fromIntegral . uncurry (+) . first ((natVal $ Proxy @m) *) . bimap @_ @_ @Natural @_ @Natural fromIntegral fromIntegral +{-# INLINE separateProduct' #-} separateProduct' :: forall n m . (KnownNat n, KnownNat m) => Finite (n * m) -> (Finite n, Finite m) separateProduct' = bimap (fromIntegral . (\x -> fromIntegral x `div` natVal @m Proxy)) (fromIntegral . (\x -> fromIntegral x `mod` natVal @m Proxy)) . join (,) 

@@ -150,24 +150,6 @@                                                           then success                                                           else assert . isJust . next $ x) -skipZeroIsPrevious :: forall (a :: Type) . (Finitary a, Show a) => Proxy a -> Property-skipZeroIsPrevious _ = withTests (testLimit @a) (property $ do x <- forAll $ choose @a-                                                               previous @a @Maybe x === previousSkipping 0 x)--skipZeroIsNext :: forall (a :: Type) . (Finitary a, Show a) => Proxy a -> Property-skipZeroIsNext _ = withTests (testLimit @a) (property $ do x <- forAll $ choose @a-                                                           next @a @Maybe x === nextSkipping 0 x)--skipNPreviousAgrees :: forall (a :: Type) . (Finitary a, Show a) => Proxy a -> Property-skipNPreviousAgrees _ = withTests (testLimit @a) (property $ do x <- forAll $ choose @a-                                                                i <- forAll $ choose @(Finite (Cardinality a))-                                                                iterateMN @Maybe i previous x === previousSkipping i x)--skipNNextAgrees :: forall (a :: Type) . (Finitary a, Show a) => Proxy a -> Property-skipNNextAgrees _ = withTests (testLimit @a) (property $ do x <- forAll $ choose @a-                                                            i <- forAll $ choose @(Finite (Cardinality a))-                                                            iterateMN @Maybe i next x === nextSkipping i x)- -- Check the behaviour of the tuple generic so that we don't violate -- order-preservation agreesWithOrd :: Property@@ -190,11 +172,7 @@   (SomeTestFunction previousStartNothing, "previous + start"),   (SomeTestFunction endNextNothing, "next + end"),   (SomeTestFunction previousIsCorrect, "previous"),-  (SomeTestFunction nextIsCorrect, "next"),-  (SomeTestFunction skipZeroIsPrevious, "previousSkipping 0"),-  (SomeTestFunction skipZeroIsNext, "nextSkipping 0"),-  (SomeTestFunction skipNPreviousAgrees, "previousSkipping n"),-  (SomeTestFunction skipNNextAgrees, "nextSkipping n")+  (SomeTestFunction nextIsCorrect, "next")   ]  main :: IO Bool