Copyright | (C) Koz Ross 2019 |
---|---|

License | GPL version 3.0 or later |

Stability | Experimental |

Portability | GHC only |

Safe Haskell | Trustworthy |

Language | Haskell2010 |

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

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.

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) Source # | |

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

Defined in Data.Finitary.PackBits | |

Hashable (BulkPack a) Source # | |

Defined in Data.Finitary.PackBits | |

NFData (BulkPack a) Source # | |

Defined in Data.Finitary.PackBits | |

Binary (BulkPack a) Source # | |