Copyright	(C) Koz Ross 2019
License	GPL version 3.0 or later
Maintainer	koz.ross@retro-freedom.nz
Stability	Experimental
Portability	GHC only
Safe Haskell	Trustworthy
Language	Haskell2010

Data.Finitary.PackBits.Unsafe

Description

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 not thread-safe, in exchange for performance. If you suspect race conditions are possible, it's better to use Data.Finitary.PackBits instead.

Synopsis

data PackBits (a :: Type)
pattern Packed :: forall (a :: Type). (Finitary a, 1 <= Cardinality a) => PackBits a -> 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) => MVector MVector (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe 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) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe 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) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe Methods minBound :: PackBits a # maxBound :: PackBits a #
Eq (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe Methods (==) :: PackBits a -> PackBits a -> Bool # (/=) :: PackBits a -> PackBits a -> Bool #
Ord (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe 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) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe Methods put :: PackBits a -> Put # get :: Get (PackBits a) # putList :: [PackBits a] -> Put #
NFData (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe Methods rnf :: PackBits a -> () #
(Finitary a, 1 <= Cardinality a) => Finitary (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe 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) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe
Hashable (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe Methods hashWithSalt :: Int -> PackBits a -> Int hash :: PackBits a -> Int
newtype MVector s (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe newtype MVector s (PackBits a) = MV_PackBits (MVector s Bit)
type Cardinality (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe type Cardinality (PackBits a) = Cardinality a
newtype Vector (PackBits a) Source #
Instance details Defined in Data.Finitary.PackBits.Unsafe newtype Vector (PackBits a) = V_PackBits (Vector Bit)

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