finitary-derive-2.0.0.0: Flexible and easy deriving of type classes for finitary types.
Copyright (C) Koz Ross 2019 GPL version 3.0 or later koz.ross@retro-freedom.nz Experimental GHC only Trustworthy Haskell2010

Data.Finitary.PackBits

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 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

# Documentation

data PackBits (a :: Type) Source #

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

#### Instances

Instances details

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.