cantor-pairing 0.2.0.0 → 0.2.0.1

raw patch · 4 files changed

+26/−28 lines, 4 filesdep +integer-rootsdep −arithmoidep ~basePVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: integer-roots

Dependencies removed: arithmoi

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• cantor-pairing.cabal +3/−3
• src/Cantor.hs +21/−24
• src/Cantor/Huge.hs +1/−1
• test/Spec.hs +1/−0

@@ -1,6 +1,6 @@ cabal-version:       2.4 name:                cantor-pairing-version:             0.2.0.0+version:             0.2.0.1 synopsis:            Convert data to and from a natural number representation description:         Convert data to and from a natural number representation conveniently using GHC Generics. homepage:            https://github.com/identicalsnowflake/cantor-pairing@@ -22,11 +22,11 @@       Cantor   other-modules:       Cantor.Huge-  build-depends:       arithmoi >= 0.8.0.0 && < 0.11-                     , base >= 4.12.0.0 && < 5+  build-depends:       base >= 4.12.0.0 && < 5                      , containers >= 0.6.0.1 && < 0.7                      , integer-gmp ^>= 1.0.2.0                      , integer-logarithms >= 1.0.2.2 && < 2.0+                     , integer-roots >= 1.0 && < 1.1   hs-source-dirs:      src   ghc-options: -Wall -Wextra   default-language:    Haskell2010

@@ -26,41 +26,34 @@ -- data MyType = MyType { --     value1 :: [ Maybe Bool ] --   , value2 :: Integer---   } deriving (Generic)------ instance Cantor MyType+--   } deriving (Generic,Cantor) -- @--- +-- -- = Recursive example -- -- This should work nicely even with simple inductive types:--- --- @--- data Tree a = Leaf | Branch (Tree a) a (Tree a) deriving (Generic) ----- instance Cantor a => Cantor (Tree a) -- @+-- data Tree a = Leaf | Branch (Tree a) a (Tree a) deriving (Generic,Cantor)+-- @ -- -- = Finite example -- -- If your type is finite, you can specify this by deriving the @Finite@ typeclass, which is a subclass of @Cantor@:--- --- @--- data Color = Red | Green | Blue deriving (Generic) ----- instance Cantor Color--- instance Finite Color -- @+-- data Color = Red | Green | Blue deriving (Generic,Cantor,Finite)+-- @ ----- +-- -- = Mutually-recursive types--- +-- -- If you have mutually-recursive types, unfortunately you'll need to manually specify the cardinality for now, but you can still get the to/from encodings for free:--- +-- -- @ -- data Foo = FooNil | Foo Bool Bar deriving (Generic,Show) -- data Bar = BarNil | Bar Bool Foo deriving (Generic,Show)--- +-- -- instance Cantor Foo where --   cardinality = Countable -- instance Cantor Bar@@ -69,8 +62,7 @@  module Cantor        ( cantorEnumeration-       , Cardinality(Countable)-       , pattern Finite+       , Cardinality(Countable,Finite)        , Cantor(..)        , Finite        , fCardinality@@ -85,7 +77,7 @@ import Data.Functor.Identity import qualified Data.Functor.Const import Data.Proxy-import Math.NumberTheory.Powers.Squares (integerSquareRoot')+import Math.NumberTheory.Roots (integerSquareRoot) import Data.Void import Data.Bits import Data.Foldable (foldl')@@ -121,7 +113,7 @@  -- | Enumerates all values of a type by mapping @toCantor@ over the naturals or finite subset of naturals with the correct cardinality. ----- >>> take 5 cantorEnumeration :: [Data.IntSet.IntSet]+-- >>> take 5 cantorEnumeration :: [ Data.IntSet.IntSet ] -- [fromList [],fromList [0],fromList [1],fromList [0,1],fromList [2]] {-# INLINABLE cantorEnumeration #-} cantorEnumeration :: Cantor a => [ a ]@@ -162,20 +154,25 @@ -- | @Cardinality@ can be either @Finite@ or @Countable@. @Countable@ cardinality entails that a type has the same cardinality as the natural numbers. Note that not all infinite types are countable: for example, @Natural -> Natural@ is an infinite type, but it is not countably infinite; the basic intuition is that there is no possible way to enumerate all values of type @Natural -> Natural@ without "skipping" almost all of them. This is in contrast to the naturals, where despite their being infinite, we can trivially (by definition, in fact!) enumerate all of them without skipping any. data Cardinality =     Finite' Huge-  | Countable+  | Countable'   deriving (Generic,Eq,Ord)  instance Show Cardinality where   show Countable = "Countable"   show (Finite i) = "Finite " <> show i --- | Finite cardinality.+pattern Countable :: Cardinality+pattern Countable <- Countable'+  where+    Countable = Countable'+ pattern Finite :: Integer -> Cardinality pattern Finite n <- Finite' (evalWith (^) -> n)   where     Finite n = Finite' (fromInteger n)  {-# COMPLETE Finite, Countable #-}+{-# COMPLETE Finite', Countable #-}  -- | The @Finite@ typeclass simply entails that the @Cardinality@ of the set is finite. class Cantor a => Finite a where@@ -530,7 +527,7 @@   in   (x , y)   where-    w = (integerSquareRoot' (8 * i + 1) - 1) `div` 2+    w = (integerSquareRoot (8 * i + 1) - 1) `div` 2  cantorUnsplit :: (Integer , Integer) -> Integer cantorUnsplit (x , y) = (((x + y + 1) * (x + y)) `quot` 2) + y

@@ -14,8 +14,8 @@  import Prelude hiding ((^^)) import Control.Exception-import Math.NumberTheory.Powers import Math.NumberTheory.Logarithms+import Math.NumberTheory.Roots import Numeric.Natural  -- | Lazy huge numbers with an efficient 'Ord' instance.

@@ -13,6 +13,7 @@  import Cantor + data TreeL a = NodeL | BranchL (TreeL a) a (TreeL a) deriving (Generic,Eq)  instance Cantor a => Cantor (TreeL a)