Data.Finitary.PackBits

From the Kraft-McMillan inequality and 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.

Packing and unpacking between a type and a bit vector

newtype PackBits (a :: Type)

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

Constructors

PackedBits (Vector Bit)

Bundled Patterns

pattern Packed :: forall (a :: Type). (Finitary a, 1 <= Cardinality a) => a -> PackBits 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.

Instances

(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) => 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) => 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

(Finitary a, 1 <= Cardinality a) => 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

Show (PackBits a)

Defined in Data.Finitary.PackBits

Methods

showsPrec :: Int -> PackBits a -> ShowS

show :: PackBits a -> String

showList :: [PackBits a] -> ShowS

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 :: PackBits a -> Maybe (PackBits a)

next :: PackBits a -> Maybe (PackBits a)

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

Defined in Data.Finitary.PackBits

newtype MVector s (PackBits a)

Defined in Data.Finitary.PackBits

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

newtype Vector (PackBits a)

Defined in Data.Finitary.PackBits

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

type Cardinality (PackBits a)

Defined in Data.Finitary.PackBits

type Cardinality (PackBits a) = Cardinality a

data BulkPack a

This wrapper provides an efficient Hashable instance (hash the entire underlying bit-packed vector, rather than each element individually), as well as a Binary instance (which stores or reads the entire blob of bits 'in one go').

Instances

(Finitary a, 1 <= Cardinality a) => Eq (BulkPack a)

Defined in Data.Finitary.PackBits

Methods

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

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

(Finitary a, 1 <= Cardinality a) => Ord (BulkPack a)

Defined in Data.Finitary.PackBits

Methods

compare :: BulkPack a -> BulkPack a -> Ordering

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

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

(>) :: BulkPack a -> BulkPack a -> Bool

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

max :: BulkPack a -> BulkPack a -> BulkPack a

min :: BulkPack a -> BulkPack a -> BulkPack a

Binary (BulkPack a)

Defined in Data.Finitary.PackBits

Methods

put :: BulkPack a -> Put

get :: Get (BulkPack a)

putList :: [BulkPack a] -> Put

NFData (BulkPack a)

Defined in Data.Finitary.PackBits

Methods

rnf :: BulkPack a -> ()

Hashable (BulkPack a)

Defined in Data.Finitary.PackBits

Methods

hashWithSalt :: Int -> BulkPack a -> Int

hash :: BulkPack a -> Int

exposeVector :: BulkPack a -> Vector (PackBits a)

Helpers

intoBits :: forall (n :: Nat). (KnownNat n, 1 <= n) => Finite n -> Vector Bit

outOfBits :: forall (n :: Nat). KnownNat n => Vector Bit -> Finite n