Copyright	(C) Koz Ross 2019
License	GPL version 3.0 or later
Stability	Experimental
Portability	GHC only
Safe Haskell	Trustworthy
Language	Haskell2010

Data.Finitary.PackBits

Description

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.

Synopsis

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

Documentation

data PackBits (a :: Type) Source #

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

Instances

Instances details

(Finitary a, 1 <= Cardinality a) => Vector Vector (PackBits a) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details Defined in Data.Finitary.PackBits Methods minBound :: PackBits a maxBound :: PackBits a
Eq (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits Methods (==) :: PackBits a -> PackBits a -> Bool (/=) :: PackBits a -> PackBits a -> Bool
Ord (PackBits a) Source #
Instance details 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) Source #
Instance details Defined in Data.Finitary.PackBits Methods showsPrec :: Int -> PackBits a -> ShowS show :: PackBits a -> String showList :: [PackBits a] -> ShowS
(Finitary a, 1 <= Cardinality a) => Finitary (PackBits a) Source #
Instance details 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) Source #
Instance details Defined in Data.Finitary.PackBits
NFData (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits Methods rnf :: PackBits a -> ()
newtype MVector s (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits newtype MVector s (PackBits a) = MV_PackBits (MVector s Bit)
newtype Vector (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits newtype Vector (PackBits a) = V_PackBits (Vector Bit)
type Cardinality (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits type Cardinality (PackBits a) = Cardinality a

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

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.

data BulkPack a Source #

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

Instances details

(Finitary a, 1 <= Cardinality a) => Eq (BulkPack a) Source #
Instance details Defined in Data.Finitary.PackBits Methods (==) :: BulkPack a -> BulkPack a -> Bool (/=) :: BulkPack a -> BulkPack a -> Bool
(Finitary a, 1 <= Cardinality a) => Ord (BulkPack a) Source #
Instance details 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
Hashable (BulkPack a) Source #
Instance details Defined in Data.Finitary.PackBits Methods hashWithSalt :: Int -> BulkPack a -> Int # hash :: BulkPack a -> Int #
NFData (BulkPack a) Source #
Instance details Defined in Data.Finitary.PackBits Methods rnf :: BulkPack a -> ()
Binary (BulkPack a) Source #
Instance details Defined in Data.Finitary.PackBits Methods put :: BulkPack a -> Put get :: Get (BulkPack a) putList :: [BulkPack a] -> Put

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