variety 0.1.0.1 → 0.1.0.2

raw patch · 6 files changed

+84/−24 lines, 6 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +4/−0
• src/Codec/Arithmetic/Combinatorics.hs +5/−6
• src/Codec/Arithmetic/Variety.hs +3/−1
• src/Codec/Elias.hs +60/−5
• src/Codec/Elias/Natural.hs +8/−8
• variety.cabal +4/−4

@@ -1,5 +1,9 @@ # Revision history for variety +## 0.1.0.2 -- 2025-06-05++* Improved documentation+ ## 0.1.0.1 -- 2025-06-05  * Removed dependency on extra

@@ -14,8 +14,7 @@     -- more than once. The number of such permutations is equal to the     -- multinomial coefficient with the same parameters: \[ {n \choose     -- k_{1}, k_{2}, \ldots, k_{m}} = \frac{n!}{k_{1}! k_{2}! \cdots-    -- k_{m}!} \] This is the most general definition in this module,-    -- of which all following objects are special cases.+    -- k_{m}!} ~~~~~\mathrm{where}~~~~~ n = \sum_i k_i \]      rankMultisetPermutation   , unrankMultisetPermutation@@ -24,8 +23,8 @@   -- * Permutations    -- | A [permutation](https://en.wikipedia.org/wiki/Permutation) is an-  -- ordering of all the objects of a set. The number of permutations of-  -- a set of \(n\) elements is \(n!\).+  -- ordering of the objects of a set of distinct elements. The number+  -- of permutations of a set of \(n\) elements is \(n!\).    , rankPermutation   , unrankPermutation@@ -44,7 +43,7 @@   -- * Distributions    -- | A distribution (usually discussed under the name [stars and-  -- bars](https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics\))+  -- bars](https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics\)))   -- is a way to distribute \(n\) equal elements (stars) among \(k\)   -- bins (i.e. \(k-1\) bars ). @@ -130,7 +129,7 @@           | otherwise = findBin acc' ascs           where acc' = acc + subCoef --- | Computes the multinomial coefficient.+-- | Computes the multinomial coefficient given a list of counts \(k_i\). multinomial :: [Int] -> Integer multinomial ns | any (< 0) ns = 0                | otherwise = factorial (sum ns)

@@ -9,7 +9,9 @@ -- coding](https://en.wikipedia.org/wiki/Arithmetic_coding) on a -- rational number code is that for each operation, we operate on the -- whole code with infinite precision. For an codec with finite--- precision, see the @Variety.Bounded@ module.+-- precision, see the+-- [Variety.Bounded](https://hackage-content.haskell.org/package/variety/docs/Codec-Arithmetic-Variety-Bounded.html)+-- module. module Codec.Arithmetic.Variety   ( -- * Value-base Interface 

@@ -1,11 +1,29 @@--- | Elias codes are prefix codes for positive, non-zero integers with--- no prior assumption to their size.+-- | [Elias codes](https://en.wikipedia.org/wiki/Elias_coding) are+-- prefix codes for positive, non-zero integers with no assumption or+-- limit to their size.+--+-- For codes that include the value @0@, see+-- [Elias.Natural](https://hackage-content.haskell.org/package/variety/docs/Codec-Elias-Natural.html). module Codec.Elias     ( -- * Gamma coding        -- | An Elias gamma code consists of the binary expansion of an       -- integer, preceded by the unary encoding of the length of that       -- expansion in zeros.+      --+      -- For example, while the binary expansion of @21@ is:+      --+      -- > import qualified Codec.Arithmetic.Variety.BitVec as BV+      -- > BV.toString $ BV.fromInteger 21+      -- > "10101"+      --+      -- its Elias code is:+      --+      -- > BV.toString $ enodeGamma 21+      -- > "000010101"+      --+      -- where an expansion of \(i\) is always preceeded by \(i-1\)+      -- zeros.        encodeGamma     , decodeGamma@@ -15,6 +33,26 @@     -- | An Elias delta code is like an Elias gamma code except that the     -- length is itself coded like a gamma code instead of simply a     -- unary encoding.+    --+    -- For example:+    --+    -- > BV.toString $ BV.fromInteger (10^6)+    -- > "11110100001001000000"+    -- >+    -- > length "11110100001001000000"+    -- > 20+    --+    -- is prefixed with the gamma encoding of @20@ and loses its leading+    -- bit which begins every binary expansion:+    --+    -- > BV.toString <$> [encodeGamma 20, BV.fromInteger (10^6)]+    -- > ["000010100","11110100001001000000"]+    -- >+    -- > BV.toString $ encodeDelta 1000000+    -- > "0000101001110100001001000000"+    -- >+    -- > length "0000101001110100001001000000"+    -- > 28      , encodeDelta     , decodeDelta@@ -22,9 +60,26 @@     -- * Omega coding      -- | An Elias omega code is the result of recursively encoding the-    -- length of binary expansions until a length of @1@ is-    -- reached. Since binary expansions are written without any leading-    -- zeros, a single @0@ bit marks the end of the code.+    -- length of binary expansions in the prefix until a length of @1@+    -- is reached. Since binary expansions are written without any+    -- leading zeros, a single @0@ bit marks the end of the code.+    --+    -- For example:+    --+    -- > BV.toString . BV.fromInteger <$> [2,4,19,10^6]+    -- > ["10","100","10011","11110100001001000000"]+    -- >+    -- > length <$> ["10","100","10011","11110100001001000000"]+    -- > [2,3,5,20]+    -- >+    -- > BV.toString $ encodeOmega (10^6)+    -- > "1010010011111101000010010000000"+    -- >+    -- > length $ "1010010011111101000010010000000"+    -- > 31+    --+    -- Notice that, while /asymptotically/ more efficient, omega codes+    -- are longer than delta codes until around 1 googol, or @10^100@.      , encodeOmega     , decodeOmega

@@ -1,9 +1,9 @@--- | Elias codes are prefix codes for positive, non-zero integers with--- no prior assumption to their size.+-- | [Elias codes](https://en.wikipedia.org/wiki/Elias_coding) are+-- prefix codes for positive, non-zero integers with no assumption or+-- limit to their size. ----- To allow for encoding zero, functions of this module add @1@ at--- encoding time and subtract @1@ at decoding time to support any--- natural number.+-- Functions of this module add @1@ at encoding time and subtract @1@ at+-- decoding time to support any natural number, including zero. module Codec.Elias.Natural     ( -- * Gamma coding @@ -26,9 +26,9 @@     -- * Omega coding      -- | An Elias omega code is the result of recursively encoding the-    -- length of binary expansions until a length of @1@ is-    -- reached. Since binary expansions are written without any leading-    -- zeros, a single @0@ bit marks the end of the code.+    -- length of binary expansions in the prefix until a length of @1@+    -- is reached. Since binary expansions are written without any+    -- leading zeros, a single @0@ bit marks the end of the code.      , encodeOmega     , decodeOmega

@@ -1,6 +1,6 @@ cabal-version:      3.0 name:               variety-version:            0.1.0.1+version:            0.1.0.2 synopsis:           integer arithmetic codes  description: The@@ -11,14 +11,14 @@                      If codes get too large and slow to process,                     [Variety.Bounded](https://hackage-content.haskell.org/package/variety/docs/Codec-Arithmetic-Variety-Bounded.html)-                    provides similar interface with a precision+                    provides a similar interface with a precision                     parameter at small cost to code length.                      The                     [Combinatorics](https://hackage-content.haskell.org/package/variety/docs/Codec-Arithmetic-Combinatorics.html)                     module provides functions to optimally encode and-                    decode common combinatorial objects through ranking-                    and unranking.+                    decode (rank and unrank) common combinatorial+                    objects.                      The                     [Elias](https://hackage-content.haskell.org/package/variety/docs/Codec-Elias.html)