Data.Finitary.PackBits

From the Kraft-McMillan inequality, the fact that we are not able to have 'fractional' bits, we can derive a fixed-length code into a bitstring for any Finitary type a, with code length \(\lceil \log_{2}(\texttt{Cardinality a}) \rceil\) bits. This code is essentially a binary representation of the index of each inhabitant of a. On that basis, we can derive an Unbox instance, representing the entire Vector as an unboxed bit array.

This encoding is advantageous from the point of view of space - there is no tighter possible packing that preserves \(\Theta(1)\) random access and also allows the full range of Vector operations. If you are concerned about space usage above all, this is the best choice for you.

Because access to individual bits is slower than whole bytes or words, this encoding adds some overhead. Additionally, a primary advantage of bit arrays (the ability to perform 'bulk' operations on bits efficiently) is not made use of here. Therefore, if speed matters more than compactness, this encoding is suboptimal.

This encoding is thread-safe, and thus slightly slower. If you are certain that race conditions cannot occur for your code, you can gain a speed improvement by using Data.Finitary.PackBits.Unsafe instead.

Documentation

data PackBits (a :: Type)

An opaque wrapper around a, representing each value as a 'bit-packed' encoding.

Instances

(Finitary a, 1 <= Cardinality a) => MVector MVector (PackBits a)

Defined in Data.Finitary.PackBits

Methods

basicLength :: MVector s (PackBits a) -> Int

basicUnsafeSlice :: Int -> Int -> MVector s (PackBits a) -> MVector s (PackBits a)

basicOverlaps :: MVector s (PackBits a) -> MVector s (PackBits a) -> Bool

basicUnsafeNew :: PrimMonad m => Int -> m (MVector (PrimState m) (PackBits a))

basicInitialize :: PrimMonad m => MVector (PrimState m) (PackBits a) -> m ()

basicUnsafeReplicate :: PrimMonad m => Int -> PackBits a -> m (MVector (PrimState m) (PackBits a))

basicUnsafeRead :: PrimMonad m => MVector (PrimState m) (PackBits a) -> Int -> m (PackBits a)

basicUnsafeWrite :: PrimMonad m => MVector (PrimState m) (PackBits a) -> Int -> PackBits a -> m ()

basicClear :: PrimMonad m => MVector (PrimState m) (PackBits a) -> m ()

basicSet :: PrimMonad m => MVector (PrimState m) (PackBits a) -> PackBits a -> m ()

basicUnsafeCopy :: PrimMonad m => MVector (PrimState m) (PackBits a) -> MVector (PrimState m) (PackBits a) -> m ()

basicUnsafeMove :: PrimMonad m => MVector (PrimState m) (PackBits a) -> MVector (PrimState m) (PackBits a) -> m ()

basicUnsafeGrow :: PrimMonad m => MVector (PrimState m) (PackBits a) -> Int -> m (MVector (PrimState m) (PackBits a))

(Finitary a, 1 <= Cardinality a) => Vector Vector (PackBits a)

Defined in Data.Finitary.PackBits

Methods

basicUnsafeFreeze :: PrimMonad m => Mutable Vector (PrimState m) (PackBits a) -> m (Vector (PackBits a))

basicUnsafeThaw :: PrimMonad m => Vector (PackBits a) -> m (Mutable Vector (PrimState m) (PackBits a))

basicLength :: Vector (PackBits a) -> Int

basicUnsafeSlice :: Int -> Int -> Vector (PackBits a) -> Vector (PackBits a)

basicUnsafeIndexM :: Monad m => Vector (PackBits a) -> Int -> m (PackBits a)

basicUnsafeCopy :: PrimMonad m => Mutable Vector (PrimState m) (PackBits a) -> Vector (PackBits a) -> m ()

elemseq :: Vector (PackBits a) -> PackBits a -> b -> b

(Finitary a, 1 <= Cardinality a) => Bounded (PackBits a)

Defined in Data.Finitary.PackBits

Methods

minBound :: PackBits a

maxBound :: PackBits a

Eq (PackBits a)

Defined in Data.Finitary.PackBits

Methods

(==) :: PackBits a -> PackBits a -> Bool

(/=) :: PackBits a -> PackBits a -> Bool

Ord (PackBits a)

Defined in Data.Finitary.PackBits

Methods

compare :: PackBits a -> PackBits a -> Ordering

(<) :: PackBits a -> PackBits a -> Bool

(<=) :: PackBits a -> PackBits a -> Bool

(>) :: PackBits a -> PackBits a -> Bool

(>=) :: PackBits a -> PackBits a -> Bool

max :: PackBits a -> PackBits a -> PackBits a

min :: PackBits a -> PackBits a -> PackBits a

Binary (PackBits a)

Defined in Data.Finitary.PackBits

Methods

put :: PackBits a -> Put

get :: Get (PackBits a)

putList :: [PackBits a] -> Put

NFData (PackBits a)

Defined in Data.Finitary.PackBits

Methods

rnf :: PackBits a -> ()

(Finitary a, 1 <= Cardinality a) => Finitary (PackBits a)

Defined in Data.Finitary.PackBits

Associated Types

type Cardinality (PackBits a) :: Nat

Methods

fromFinite :: Finite (Cardinality (PackBits a)) -> PackBits a

toFinite :: PackBits a -> Finite (Cardinality (PackBits a))

start :: PackBits a

end :: PackBits a

previous :: Alternative f => PackBits a -> f (PackBits a)

next :: Alternative f => PackBits a -> f (PackBits a)

(Finitary a, 1 <= Cardinality a) => Unbox (PackBits a)

Defined in Data.Finitary.PackBits

Hashable (PackBits a)

Defined in Data.Finitary.PackBits

Methods

hashWithSalt :: Int -> PackBits a -> Int

hash :: PackBits a -> Int

newtype MVector s (PackBits a)

Defined in Data.Finitary.PackBits

newtype MVector s (PackBits a) = MV_PackBits (MVector s Bit)

type Cardinality (PackBits a)

Defined in Data.Finitary.PackBits

type Cardinality (PackBits a) = Cardinality a

newtype Vector (PackBits a)

Defined in Data.Finitary.PackBits

newtype Vector (PackBits a) = V_PackBits (Vector Bit)

pattern Packed :: forall (a :: Type). (Finitary a, 1 <= Cardinality a) => PackBits a -> a

To provide (something that resembles a) data constructor for PackBits, we provide the following pattern. It can be used like any other data constructor:

import Data.Finitary.PackBits

anInt :: PackBits Int
anInt = Packed 10

isPackedEven :: PackBits Int -> Bool
isPackedEven (Packed x) = even x

Every pattern match, and data constructor call, performs a \(\Theta(\log_{2}(\texttt{Cardinality a}))\) encoding or decoding operation. Use with this in mind.