finitary-derive-2.0.0.0: Flexible and easy deriving of type classes for finitary types.
Copyright(C) Koz Ross 2019
LicenseGPL version 3.0 or later
Maintainerkoz.ross@retro-freedom.nz
StabilityExperimental
PortabilityGHC only
Safe HaskellTrustworthy
LanguageHaskell2010

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

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

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.