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 |

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.

# Documentation

data PackBits (a :: Type) Source #

An opaque wrapper around `a`

, representing each value as a 'bit-packed'
encoding.

#### Instances

(Finitary a, 1 <= Cardinality a) => MVector MVector (PackBits a) Source # | |

Defined in Data.Finitary.PackBits 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 # | |

Defined in Data.Finitary.PackBits 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 () | |

(Finitary a, 1 <= Cardinality a) => Bounded (PackBits a) Source # | |

Eq (PackBits a) Source # | |

Ord (PackBits a) Source # | |

Binary (PackBits a) Source # | |

NFData (PackBits a) Source # | |

Defined in Data.Finitary.PackBits | |

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

Defined in Data.Finitary.PackBits | |

(Finitary a, 1 <= Cardinality a) => Unbox (PackBits a) Source # | |

Defined in Data.Finitary.PackBits | |

Hashable (PackBits a) Source # | |

Defined in Data.Finitary.PackBits | |

newtype MVector s (PackBits a) Source # | |

Defined in Data.Finitary.PackBits | |

type Cardinality (PackBits a) Source # | |

Defined in Data.Finitary.PackBits type Cardinality (PackBits a) = Cardinality a | |

newtype Vector (PackBits a) Source # | |

Defined in Data.Finitary.PackBits |

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.