variety 0.1.0.2 → 0.2.0.0
raw patch · 9 files changed
+317/−120 lines, 9 files
Files
- CHANGELOG.md +12/−2
- src/Codec/Arithmetic/Combinatorics.hs +197/−25
- src/Codec/Arithmetic/Variety.hs +23/−18
- src/Codec/Arithmetic/Variety/BitVec.hs +4/−1
- src/Codec/Arithmetic/Variety/Bounded.hs +17/−18
- src/Codec/Elias.hs +43/−42
- src/Codec/Elias/Natural.hs +16/−9
- test/Main.hs +4/−4
- variety.cabal +1/−1
CHANGELOG.md view
@@ -1,12 +1,22 @@ # Revision history for variety +## 0.2.0.0 -- 2025-07-22++* Altered the type/interface for all BitVec decoding functions to+ leverage the prefix property, returning `Maybe (a, BitVec)` which+ includes the remaining bits upon successful decoding and `Nothing` in+ case of a lack of bits instead of throwing an error.+* Specify ranges for which each Elias codes are optimal.+* `BitVec` interfaces added to `Combinatorics` to facilitate+ serialization and interactivity with the other modules.+ ## 0.1.0.2 -- 2025-06-05 -* Improved documentation+* Improved documentation. ## 0.1.0.1 -- 2025-06-05 -* Removed dependency on extra+* Removed dependency on extra. ## 0.1.0.0 -- 2025-06-04
src/Codec/Arithmetic/Combinatorics.hs view
@@ -16,7 +16,9 @@ -- k_{1}, k_{2}, \ldots, k_{m}} = \frac{n!}{k_{1}! k_{2}! \cdots -- k_{m}!} ~~~~~\mathrm{where}~~~~~ n = \sum_i k_i \] - rankMultisetPermutation+ encodeMultisetPermutation+ , decodeMultisetPermutation+ , rankMultisetPermutation , unrankMultisetPermutation , multinomial @@ -26,8 +28,11 @@ -- ordering of the objects of a set of distinct elements. The number -- of permutations of a set of \(n\) elements is \(n!\). + , encodePermutation+ , decodePermutation , rankPermutation , unrankPermutation+ , factorial -- * Combinations @@ -36,6 +41,8 @@ -- combinations for parameters \(n\) and \(k\) is given by the -- binomial coefficient: \[ {n \choose k} = \frac{n!}{k! (n-k)!} \] + , encodeCombination+ , decodeCombination , rankCombination , unrankCombination , choose@@ -47,16 +54,22 @@ -- is a way to distribute \(n\) equal elements (stars) among \(k\) -- bins (i.e. \(k-1\) bars ). + , encodeDistribution+ , decodeDistribution , rankDistribution , unrankDistribution+ , countDistributions -- * Non-Empty Distributions -- | The class of distributions that have at least one element per -- bin. + , encodeDistribution1+ , decodeDistribution1 , rankDistribution1 , unrankDistribution1+ , countDistributions1 ) where import Control.Exception (assert)@@ -65,13 +78,41 @@ import qualified Data.List as L import Data.Map.Strict (Map) import qualified Data.Map.Strict as M-import Math.Combinatorics.Exact.Factorial (factorial)+import qualified Math.Combinatorics.Exact.Factorial as E (factorial) -import qualified Codec.Arithmetic.Variety as V+import qualified Codec.Arithmetic.Variety as Var+import Codec.Arithmetic.Variety.BitVec (BitVec)+import qualified Codec.Arithmetic.Variety.BitVec as BV err :: String -> a err = error . ("Combinatorics." ++) +--------------------------+-- MULTISET PERMUTATION --+--------------------------++-- | Encode a multiset permutation into a bit vector. Returns the count+-- of each element in the set and the code as a vector of length equal+-- to the multinomial coefficient with those counts.+encodeMultisetPermutation :: Ord a => [a] -> ([(a,Int)], BitVec)+encodeMultisetPermutation = fmap (uncurry Var.encode1)+ . rankMultisetPermutation++-- | Try to decode a multiset permutation at the head of a bit vector,+-- given the count of each element in the set. If successful, returns+-- the decoded multiset permutation and the remainder of the `BitVec`+-- with the permutation's code removed. Returns @Nothing@ if the bit+-- vector doesn't contain enough bits to specify a multiset permutation+-- of the given parameters.+decodeMultisetPermutation :: Ord a => [(a,Int)] -> BitVec -> Maybe ([a], BitVec)+decodeMultisetPermutation aks bv | BV.length bv0 < len = Nothing+ | otherwise = Just (msp, bv1)+ where+ base = multinomial $ snd <$> aks+ len = Var.codeLen1 base+ (bv0,bv1) = BV.splitAt len bv+ msp = unrankMultisetPermutation aks $ BV.toInteger bv0+ -- | Rank a multiset permutation. Returns the count of each element in -- the set, the rank and the total number of permutations with those -- counts (the multinomial coefficient).@@ -81,8 +122,8 @@ where counts = L.foldl' (\m k -> M.insertWith (+) k 1 m) M.empty msp total0 = sum counts- coef0 = factorial total0- `div` product (factorial <$> counts)+ coef0 = E.factorial total0+ `div` product (E.factorial <$> counts) index = sum $ go (fromIntegral total0) coef0 counts msp go :: Ord a => Integer -> Integer -> Map a Int -> [a] -> [Integer]@@ -110,8 +151,8 @@ err' = err . ("unrankMultisetPermutation: " ++) counts = M.fromList $ filter ((> 0) . snd) l total0 = sum counts- coef0 = factorial total0- `div` product (factorial <$> counts)+ coef0 = E.factorial total0+ `div` product (E.factorial <$> counts) go total coef m i | M.null m = [] | otherwise = a : go total' coef' m' i'@@ -129,17 +170,42 @@ | otherwise = findBin acc' ascs where acc' = acc + subCoef --- | Computes the multinomial coefficient given a list of counts \(k_i\).+-- | Computes the multinomial coefficient given a list of counts+-- \(k_i\). multinomial :: [Int] -> Integer multinomial ns | any (< 0) ns = 0- | otherwise = factorial (sum ns)- `div` product (factorial <$> ns)+ | otherwise = E.factorial (sum ns)+ `div` product (E.factorial <$> ns) --- | Rank a permutation. Returns the rank and the total number of--- permutations of sets with that size ( \(n!\) ).+-----------------+-- PERMUTATION --+-----------------++-- | Encode a permutation into a bit vector of length equal to the+-- factorial of the length of the given list.+encodePermutation :: Ord a => [a] -> BitVec+encodePermutation = uncurry Var.encode1 . rankPermutation++-- | Try to decode a permutation at the head of a bit vector, given the+-- elements in the set that was permuted. If successful, returns the+-- decoded permutation and the remainder of the `BitVec` with the+-- permutation's code removed. Returns @Nothing@ if the bit vector+-- doesn't contain enough bits to specify a permutation of a set of the+-- length of the given list of elements.+decodePermutation :: Ord a => [a] -> BitVec -> Maybe ([a], BitVec)+decodePermutation as bv | BV.length bv0 < len = Nothing+ | otherwise = Just (p, bv1)+ where+ base = E.factorial $ length as+ len = Var.codeLen1 base+ (bv0,bv1) = BV.splitAt len bv+ p = unrankPermutation as $ BV.toInteger bv0++-- | Rank a permutation. Returns the rank (`fst`) and the total number+-- of permutations of sets with that size ( \(n!\) ) (`snd`). rankPermutation :: Ord a => [a] -> (Integer, Integer) rankPermutation p | length p /= n0 = err' "not unique elements"- | otherwise = V.fromValue val+ | otherwise = Var.fromValue val where err' = err . ("rankPermutation: " ++) s0 = S.fromList p@@ -148,7 +214,7 @@ is = fromIntegral <$> go s0 p val = assert (length is == length ns) mconcat $- zipWith V.mkValue is ns+ zipWith Var.mkValue is ns -- | Lookup element index in the set of remaining elements go s [] = assert (S.null s) []@@ -168,18 +234,50 @@ set = S.fromList as n = S.size set ns = fromIntegral <$> [n,n-1..1]- base = factorial $ fromIntegral n- bv = V.toBitVec $ V.mkValue index base- is = fromIntegral <$> V.decode ns bv+ base = E.factorial $ fromIntegral n+ bv = Var.toBitVec $ Var.mkValue index base+ is = fromIntegral <$> fst (fromJust $ Var.decode ns bv) -- | Successively delete elements at given indexes from a set go s [] = assert (S.null s) [] go s (i:rest) = S.elemAt i s : go (S.deleteAt i s) rest --- | Rank a combination in the form of a list of booleans. Returns the--- \((n,k)\) parameters (where \(k\) is the number of `True` values and--- \(n\) is the total), the rank and the total number of combinations--- with those parameters (the binomial coefficient).+-- | Computes the factorial of the given number.+factorial :: Int -> Integer+factorial = E.factorial++-----------------+-- COMBINATION --+-----------------++-- | Encode a combination in the form of a list of booleans (chosen/not+-- chosen) into a bit vector. Returns the \((n,k)\) parameters (where+-- \(k\) is the number of `True` values and \(n\) is the total), and the+-- code as a vector of length equal to the binomial coefficient with+-- those parameters.+encodeCombination :: [Bool] -> ((Int, Int), BitVec)+encodeCombination = fmap (uncurry Var.encode1) . rankCombination++-- | Try to decode a combination in the form of a list of booleans+-- (chosen/not chosen) at the head of a bit vector, given the parameters+-- \((n,k)\). If successful, returns the decoded combination and the+-- remainder of the `BitVec` with the combination's code+-- removed. Returns @Nothing@ if the bit vector doesn't contain enough+-- bits to specify a combination of the given parameters.+decodeCombination :: (Int, Int) -> BitVec -> Maybe ([Bool], BitVec)+decodeCombination (n,k) bv | BV.length bv0 < len = Nothing+ | otherwise = Just (p, bv1)+ where+ base = choose n k+ len = Var.codeLen1 base+ (bv0,bv1) = BV.splitAt len bv+ p = unrankCombination (n,k) $ BV.toInteger bv0++-- | Rank a combination in the form of a list of booleans (chosen/not+-- chosen). Returns the \((n,k)\) parameters (where \(k\) is the number+-- of `True` values and \(n\) is the total), the rank and the total+-- number of combinations with those parameters (the binomial+-- coefficient). rankCombination :: [Bool] -> ((Int, Int), (Integer, Integer)) rankCombination c = ( (n0, k0) , (res, n0Ck0) )@@ -218,9 +316,36 @@ choose :: Int -> Int -> Integer choose n k | denom == 0 = 0 | otherwise = num `div` denom- where num = factorial n- denom = factorial k * factorial (n-k)+ where num = E.factorial n+ denom = E.factorial k * E.factorial (n-k) +------------------+-- DISTRIBUTION --+------------------++-- | Encode a distribution in the form of a list bin counts into a bit+-- vector. Returns the \((n,k)\) parameters (where \(n\) is the total+-- number of elements and \(k\) is the number of bins) and the code as a+-- vector of length equal to the number of distributions with those+-- parameters.+encodeDistribution :: [Int] -> ((Int, Int), BitVec)+encodeDistribution = fmap (uncurry Var.encode1) . rankDistribution++-- | Try to decode a distribution in the form of a list of bin counts at+-- the head of a bit vector, given the parameters \((n,k)\). If+-- successful, returns the decoded distribution and the remainder of the+-- `BitVec` with the distribution's code removed. Returns @Nothing@ if+-- the bit vector doesn't contain enough bits to specify a distribution+-- of the given parameters.+decodeDistribution :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec)+decodeDistribution (balls,bins) bv | BV.length bv0 < len = Nothing+ | otherwise = Just (d, bv1)+ where+ base = countDistributions balls bins+ len = Var.codeLen1 base+ (bv0,bv1) = BV.splitAt len bv+ d = unrankDistribution (balls,bins) $ BV.toInteger bv0+ -- | Rank a distribution in the form of a list bin counts. Returns the -- \((n,k)\) parameters (where \(n\) is the total number of elements and -- \(k\) is the number of bins), the rank and the total number of@@ -256,14 +381,50 @@ countGaps !acc (False:rest) = countGaps (acc + 1) rest countGaps !acc (True:rest) = acc : countGaps 0 rest +-- | Computes the number of distributions that have the given parameters+-- \(n\) and \(k\).+countDistributions :: Int -> Int -> Integer+countDistributions balls bins = base+ where+ n = balls + bins - 1 -- stars and bars+ k = bins - 1 -- number of bars+ base = if bins == 0 then 1 else n `choose` k++----------------------------+-- NON-EMPTY DISTRIBUTION --+----------------------------++-- | Encode a non-empty distribution in the form of a list bin counts+-- into a bit vector. Returns the \((n,k)\) parameters (where \(n\) is+-- the total number of elements and \(k\) is the number of bins) and the+-- code as a vector of length equal to the number of distributions with+-- those parameters.+encodeDistribution1 :: [Int] -> ((Int, Int), BitVec)+encodeDistribution1 = fmap (uncurry Var.encode1) . rankDistribution1++-- | Try to decode a non-empty distribution in the form of a list of bin+-- counts at the head of a bit vector, given the parameters+-- \((n,k)\). If successful, returns the decoded distribution and the+-- remainder of the `BitVec` with the distribution's code+-- removed. Returns @Nothing@ if the bit vector doesn't contain enough+-- bits to specify a non-empty distribution of the given parameters.+decodeDistribution1 :: (Int, Int) -> BitVec -> Maybe ([Int], BitVec)+decodeDistribution1 (bins,balls) bv | BV.length bv0 < len = Nothing+ | otherwise = Just (d1, bv1)+ where+ base = countDistributions1 bins balls+ len = Var.codeLen1 base+ (bv0,bv1) = BV.splitAt len bv+ d1 = unrankDistribution1 (balls,bins) $ BV.toInteger bv0+ -- | Rank a non-empty distribution in the form of a list bin -- counts. Returns the \((n,k)\) parameters (where \(n\) is the total -- number of elements and \(k\) is the number of bins), the rank and the -- total number of distributions with those parameters. rankDistribution1 :: [Int] -> ((Int, Int), (Integer, Integer)) rankDistribution1 ns- | any (< 1) ns = if any (< 0) ns then err' "negative count"- else err' "empty count"+ | any (< 0) ns = err' "negative count"+ | any (< 1) ns = err' "empty count" | otherwise = ((balls,bins),(i,base)) where err' = err . ("rankDistribution1: " ++)@@ -276,6 +437,17 @@ | balls < bins || bins < 0 = err' $ "invalid parameters: " ++ show (balls,bins) | otherwise = (+1) <$> unrankDistribution (balls',bins) i+ where+ err' = err . ("unrankDistribution1: " ++)+ balls' = balls - bins++-- | Computes the number of non-empty distributions that have the given+-- parameters \(n\) and \(k\).+countDistributions1 :: Int -> Int -> Integer+countDistributions1 balls bins+ | balls < bins || bins < 0 =+ err' $ "invalid parameters: " ++ show (balls,bins)+ | otherwise = countDistributions balls' bins where err' = err . ("unrankDistribution1: " ++) balls' = balls - bins
src/Codec/Arithmetic/Variety.hs view
@@ -8,7 +8,7 @@ -- difference with typical [arithmetic -- 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+-- whole code with infinite precision. For a codec with finite -- precision, see the -- [Variety.Bounded](https://hackage-content.haskell.org/package/variety/docs/Codec-Arithmetic-Variety-Bounded.html) -- module.@@ -48,19 +48,20 @@ codeLen :: [Integer] -> Int codeLen = codeLen1 . product --- | Decode a bit vector given the same series of bases that was used to--- encode it. Throws an error if the given vector's size doesn't match--- the given bases.-decode :: [Integer] -> BitVec -> [Integer]+-- | Try to decode the head of a bit vector given the same series of+-- bases that was used to encode. If successful, returns the decoded+-- values and the remainder of the `BitVec` with the values' code+-- removed. Returns @Nothing@ if the bit vector doesn't contain enough+-- bits to specify values for each given base.+decode :: [Integer] -> BitVec -> Maybe ([Integer], BitVec) decode bases bv = case init $ scanr (*) 1 bases of -- last is 1- [] -> []- (base:ns) -> case compare len expectedLen of -- base == product bases- EQ -> go (BV.toInteger bv) ns- LT -> err "decode: not enough bits"- GT -> err "decode: too many bits"+ [] -> Just ([], bv)+ (base:ns) | BV.length bv0 < len -> Nothing+ | otherwise -> Just ( go (BV.toInteger bv0) ns+ , bv1 ) where- len = BV.length bv- expectedLen = codeLen1 base+ len = codeLen1 base -- base == product bases+ (bv0,bv1) = BV.splitAt len bv where go i [] = [i] go i2 (n1:ns) = i0 : go i1 ns@@ -78,8 +79,12 @@ | otherwise = BV.bitLen $ n - 1 -- | Recover the value from a bit vector.-decode1 :: BitVec -> Integer-decode1 = BV.toInteger+decode1 :: Integer -> BitVec -> Maybe (Integer, BitVec)+decode1 base bv | BV.length bv0 < len = Nothing+ | otherwise = Just (BV.toInteger bv0, bv1)+ where+ len = codeLen1 base+ (bv0,bv1) = BV.splitAt len bv ---------------- -- VALUE TYPE --@@ -109,8 +114,8 @@ mempty :: Value mempty = Value (0,1) --- | Compose two values into a value of a greater base. This is--- associative, but not commutative.+-- | Compose two values into a value of a greater base. Associative, not+-- commutative. compose :: Value -> Value -> Value compose (Value (i0,n0)) (Value (i1,n1)) = Value (i2, n2) where@@ -121,8 +126,8 @@ maxValue :: Value -> Integer maxValue = (+(-1)) . snd . fromValue --- | Drop the base and consider the value as a bit vector. The base--- conceptually rounds to the next power of 2.+-- | Drop the base and consider the value as a bit vector. Conceptually,+-- the base rounds to the next power of 2. toBitVec :: Value -> BitVec toBitVec (Value (i,n)) = bitVec (codeLen1 n) i
src/Codec/Arithmetic/Variety/BitVec.hs view
@@ -208,7 +208,10 @@ -- | The number of bits in the binary expansion of a positive -- integer. For consistency with inductive definitions, leading zeros--- are not considered and so @`bitLen` 0 == 0@.+-- are not considered and so:+--+-- >>> bitLen 0+-- 0 bitLen :: Integer -> Int bitLen 0 = 0 bitLen n = fromIntegral (integerLog2 n) + 1
src/Codec/Arithmetic/Variety/Bounded.hs view
@@ -15,14 +15,17 @@ ) where import Data.Bits (Bits(bit))+import Data.Bifunctor (Bifunctor(first)) -import qualified Codec.Arithmetic.Variety as V+import qualified Codec.Arithmetic.Variety as Var import Codec.Arithmetic.Variety.BitVec (BitVec)-import qualified Codec.Arithmetic.Variety.BitVec as BV err :: String -> a err = error . ("Variety.Bounded: " ++) +-- | Given a base getter function and precision, chunk the values into+-- lists that do not exceed the given precision or are singleton lists,+-- annotated with the total base for each chunk. groupWithinPrec :: (a -> Integer) -> Int -> [a] -> [(Integer,[a])] groupWithinPrec getBase prec | prec < 0 = err "negative precision"@@ -44,7 +47,7 @@ -- associated values must exist in the range @[0..base-1]@. encode :: Int -> [(Integer,Integer)] -> BitVec encode = mconcat- . fmap (V.encode . snd)+ . fmap (Var.encode . snd) .: groupWithinPrec snd -- | Return the length of the code of a sequence of values in the given@@ -52,25 +55,21 @@ codeLen :: Int -> [Integer] -> Int codeLen = fromIntegral . sum- . fmap (V.codeLen1 . fst)+ . fmap (Var.codeLen1 . fst) .: groupWithinPrec id --- | Try to decode a sequence of values at the head of a bit vector--- given the same precision and list of bases that was used to encode--- it. If successful, returns the decoded values and the remainder of--- the `BitVec`, with the sequence's code removed. Throws an error if--- the given vector's size doesn't match the given bases.-decode :: Int -> [Integer] -> BitVec -> [Integer]+-- | Try to decode the head of a bit vector given the same precision and+-- series of bases that was used to encode. If successful, returns the+-- decoded values and the remainder of the `BitVec` with the values'+-- code removed. Returns @Nothing@ if the bit vector doesn't contain+-- enough bits to specify values for each given base.+decode :: Int -> [Integer] -> BitVec -> Maybe ([Integer], BitVec) decode = go .: groupWithinPrec id where- go [] bv | not (BV.null bv) = err "decode: too many bits"- | otherwise = []- go ((base,bases):rest) bv- | BV.length hd /= len = err "decode: not enough bits"- | otherwise = V.decode bases hd ++ go rest tl- where- len = BV.bitLen (base - 1)- (hd,tl) = BV.splitAt len bv+ go [] bv = Just ([], bv)+ go ((_,bases):rest) bv = do+ (vals, bv') <- Var.decode bases bv+ first (vals ++) <$> go rest bv' (.:) :: (b -> c) -> (a1 -> a2 -> b) -> a1 -> a2 -> c (.:) = (.).(.)
src/Codec/Elias.hs view
@@ -1,7 +1,14 @@ -- | [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.+-- limit to their size. For completeness, gamma, delta and omega codes+-- are implemented although for most applications you can get away with+-- only using delta codes: --+-- - Gamma codes are 1 bit more efficient than delta codes for certain+-- numbers between 1 and 15.+-- - Omega codes only become shorter than delta codes for numbers above+-- 1 googol, or \(10^{100}\).+-- -- 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@@ -13,14 +20,14 @@ -- -- For example, while the binary expansion of @21@ is: --- -- > import qualified Codec.Arithmetic.Variety.BitVec as BV- -- > BV.toString $ BV.fromInteger 21- -- > "10101"+ -- >>> import qualified Codec.Arithmetic.Variety.BitVec as BV+ -- >>> BV.toString $ BV.fromInteger 21+ -- "10101" -- -- its Elias code is: --- -- > BV.toString $ enodeGamma 21- -- > "000010101"+ -- >>> BV.toString $ enodeGamma 21+ -- "000010101" -- -- where an expansion of \(i\) is always preceeded by \(i-1\) -- zeros.@@ -31,28 +38,25 @@ -- * Delta coding -- | 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.+ -- length is itself coded like a gamma code instead of a unary+ -- encoding. --- -- For example:+ -- For example, the binary expansion of \(1\,000\,000\) --- -- > BV.toString $ BV.fromInteger (10^6)- -- > "11110100001001000000"- -- >- -- > length "11110100001001000000"- -- > 20+ -- >>> 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:+ -- bit (which begins every binary expansion): --- -- > BV.toString <$> [encodeGamma 20, BV.fromInteger (10^6)]- -- > ["000010100","11110100001001000000"]- -- >- -- > BV.toString $ encodeDelta 1000000- -- > "0000101001110100001001000000"- -- >- -- > length "0000101001110100001001000000"- -- > 28+ -- >>> BV.toString <$> [encodeGamma 20, BV.fromInteger (10^6)]+ -- ["000010100","11110100001001000000"]+ -- >>> BV.toString $ encodeDelta 1000000+ -- "0000101001110100001001000000"+ -- >>> length "0000101001110100001001000000"+ -- 28 , encodeDelta , decodeDelta@@ -66,20 +70,17 @@ -- -- 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+ -- >>> 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@.+ -- Note that, while /asymptotically/ more efficient, omega codes are+ -- longer than delta codes until around 1 googol, or \(10^{100}\). , encodeOmega , decodeOmega@@ -104,8 +105,8 @@ -- | Try to decode an Elias gamma code at the head of the given bit -- vector. If successful, returns the decoded value and the remainder of--- the `BitVec`, with the value code removed. Returns @Nothing@ if the--- bit vector doesn't contain enough bits to define a number.+-- the `BitVec` with the value's code removed. Returns @Nothing@ if the+-- bit vector doesn't contain enough bits to specify a number. decodeGamma :: BitVec -> Maybe (Integer, BitVec) decodeGamma bv | BV.length xBits /= xLen = Nothing | otherwise = Just (x, bv'')@@ -129,8 +130,8 @@ -- | Try to decode an Elias delta code at the head of the given bit -- vector. If successful, returns the decoded value and the remainder of--- the `BitVec`, with the value code removed. Returns @Nothing@ if the--- bit vector doesn't contain enough bits to define a number.+-- the `BitVec` with the value's code removed. Returns @Nothing@ if the+-- bit vector doesn't contain enough bits to specify a number. decodeDelta :: BitVec -> Maybe (Integer, BitVec) decodeDelta bv = do (xLen, bv') <- first fromIntegral <$> decodeGamma bv@@ -156,8 +157,8 @@ -- | Try to decode an Elias omega code at the head of the given bit -- vector. If successful, returns the decoded value and the remainder of--- the `BitVec`, with the value code removed. Returns @Nothing@ if the--- bit vector doesn't contain enough bits to define a number.+-- the `BitVec` with the value's code removed. Returns @Nothing@ if the+-- bit vector doesn't contain enough bits to specify a number. decodeOmega :: BitVec -> Maybe (Integer, BitVec) decodeOmega = go 1 where
src/Codec/Elias/Natural.hs view
@@ -1,7 +1,14 @@ -- | [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.+-- limit to their size. For completeness, gamma, delta and omega codes+-- are implemented although for most applications you can get away with+-- only using delta codes: --+-- - Gamma codes are 1 bit more efficient than delta codes for certain+-- numbers between 0 and 14.+-- - Omega codes only become shorter than delta codes for numbers above+-- 1 googol, or \(10^{100}\).+-- -- 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@@ -17,8 +24,8 @@ -- * Delta coding -- | 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.+ -- length is itself coded like a gamma code instead of a unary+ -- encoding. , encodeDelta , decodeDelta@@ -49,8 +56,8 @@ -- | Try to decode an Elias gamma code at the head of the given bit -- vector. If successful, returns the decoded value and the remainder of--- the `BitVec`, with the value code removed. Returns @Nothing@ if the--- bit vector doesn't contain enough bits to define a number.+-- the `BitVec` with the value's code removed. Returns @Nothing@ if the+-- bit vector doesn't contain enough bits to specify a number. decodeGamma :: BitVec -> Maybe (Integer, BitVec) decodeGamma = fmap (first (+(-1))) . E.decodeGamma @@ -62,8 +69,8 @@ -- | Try to decode an Elias delta code at the head of the given bit -- vector. If successful, returns the decoded value and the remainder of--- the `BitVec`, with the value code removed. Returns @Nothing@ if the--- bit vector doesn't contain enough bits to define a number.+-- the `BitVec` with the value's code removed. Returns @Nothing@ if the+-- bit vector doesn't contain enough bits to specify a number. decodeDelta :: BitVec -> Maybe (Integer, BitVec) decodeDelta = fmap (first (+(-1))) . E.decodeDelta @@ -75,7 +82,7 @@ -- | Try to decode an Elias omega code at the head of the given bit -- vector. If successful, returns the decoded value and the remainder of--- the `BitVec`, with the value code removed. Returns @Nothing@ if the--- bit vector doesn't contain enough bits to define a number.+-- the `BitVec` with the value's code removed. Returns @Nothing@ if the+-- bit vector doesn't contain enough bits to specify a number. decodeOmega :: BitVec -> Maybe (Integer, BitVec) decodeOmega = fmap (first (+(-1))) . E.decodeOmega
test/Main.hs view
@@ -167,14 +167,14 @@ bases = map snd pairs expected = map fst pairs decoded = V.decode bases encoded- in decoded === expected+ in decoded === Just (expected, BV.empty) prop_encode1_decode1_roundtrip :: Integer -> Integer -> Property prop_encode1_decode1_roundtrip value base = value >= 0 && value < base && base >= 1 ==> let encoded = V.encode1 value base- decoded = V.decode1 encoded- in decoded === value+ decoded = V.decode1 base encoded+ in decoded === Just (value, BV.empty) prop_bounded_encode_decode_roundtrip :: Int -> [(Integer, Integer)] -> Property prop_bounded_encode_decode_roundtrip prec pairs =@@ -183,4 +183,4 @@ bases = map snd pairs expected = map fst pairs decoded = VB.decode prec bases encoded- in decoded === expected+ in decoded === Just (expected, BV.empty)
variety.cabal view
@@ -1,6 +1,6 @@ cabal-version: 3.0 name: variety-version: 0.1.0.2+version: 0.2.0.0 synopsis: integer arithmetic codes description: The