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	None
Language	Haskell2010

Data.Finitary.PackWords

Description

If a type a is Finitary, each inhabitant of a has an index, which can be represented as an unsigned integer, spread across one or more machine words. This unsigned integer will have fixed length (as the number of inhabitants of a is finite). We can use this to derive a Unbox instance, by representing Vector as a large array of machine words. We can also derive a Storable instance similarly.

This is the most efficient encoding of an arbitrary finitary type, both due to the asymptotics of encoding and decoding (logarithmic in Cardinality a with base Cardinality Word) and the fact that word accesses are faster than byte and bit accesses on almost all architectures. Unless you have concerns regarding space, this encoding is a good choice.

Unless your type's cardinality is extremely large (a non-trivial multiple of Cardinality Word), this encoding is wasteful. If your type's cardinality is smaller than that of Word, you should consider Data.Finitary.PackInto instead, as you will have much larger control over space usage at almost no performance penalty.

Synopsis

data PackWords (a :: Type)
pattern Packed :: forall (a :: Type). (Finitary a, 1 <= Cardinality a) => PackWords a -> a

Documentation

data PackWords (a :: Type) Source #

An opaque wrapper around a, representing each value as a fixed-length array of machine words.

Instances

Instances details

(Finitary a, 1 <= Cardinality a) => MVector MVector (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods basicLength :: MVector s (PackWords a) -> Int basicUnsafeSlice :: Int -> Int -> MVector s (PackWords a) -> MVector s (PackWords a) basicOverlaps :: MVector s (PackWords a) -> MVector s (PackWords a) -> Bool basicUnsafeNew :: PrimMonad m => Int -> m (MVector (PrimState m) (PackWords a)) basicInitialize :: PrimMonad m => MVector (PrimState m) (PackWords a) -> m () basicUnsafeReplicate :: PrimMonad m => Int -> PackWords a -> m (MVector (PrimState m) (PackWords a)) basicUnsafeRead :: PrimMonad m => MVector (PrimState m) (PackWords a) -> Int -> m (PackWords a) basicUnsafeWrite :: PrimMonad m => MVector (PrimState m) (PackWords a) -> Int -> PackWords a -> m () basicClear :: PrimMonad m => MVector (PrimState m) (PackWords a) -> m () basicSet :: PrimMonad m => MVector (PrimState m) (PackWords a) -> PackWords a -> m () basicUnsafeCopy :: PrimMonad m => MVector (PrimState m) (PackWords a) -> MVector (PrimState m) (PackWords a) -> m () basicUnsafeMove :: PrimMonad m => MVector (PrimState m) (PackWords a) -> MVector (PrimState m) (PackWords a) -> m () basicUnsafeGrow :: PrimMonad m => MVector (PrimState m) (PackWords a) -> Int -> m (MVector (PrimState m) (PackWords a))
(Finitary a, 1 <= Cardinality a) => Vector Vector (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods basicUnsafeFreeze :: PrimMonad m => Mutable Vector (PrimState m) (PackWords a) -> m (Vector (PackWords a)) basicUnsafeThaw :: PrimMonad m => Vector (PackWords a) -> m (Mutable Vector (PrimState m) (PackWords a)) basicLength :: Vector (PackWords a) -> Int basicUnsafeSlice :: Int -> Int -> Vector (PackWords a) -> Vector (PackWords a) basicUnsafeIndexM :: Monad m => Vector (PackWords a) -> Int -> m (PackWords a) basicUnsafeCopy :: PrimMonad m => Mutable Vector (PrimState m) (PackWords a) -> Vector (PackWords a) -> m () elemseq :: Vector (PackWords a) -> PackWords a -> b -> b
(Finitary a, 1 <= Cardinality a) => Bounded (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods minBound :: PackWords a # maxBound :: PackWords a #
Eq (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods (==) :: PackWords a -> PackWords a -> Bool # (/=) :: PackWords a -> PackWords a -> Bool #
Ord (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods compare :: PackWords a -> PackWords a -> Ordering # (<) :: PackWords a -> PackWords a -> Bool # (<=) :: PackWords a -> PackWords a -> Bool # (>) :: PackWords a -> PackWords a -> Bool # (>=) :: PackWords a -> PackWords a -> Bool # max :: PackWords a -> PackWords a -> PackWords a # min :: PackWords a -> PackWords a -> PackWords a #
Show (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods showsPrec :: Int -> PackWords a -> ShowS # show :: PackWords a -> String # showList :: [PackWords a] -> ShowS #
(Finitary a, 1 <= Cardinality a) => Storable (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods sizeOf :: PackWords a -> Int # alignment :: PackWords a -> Int # peekElemOff :: Ptr (PackWords a) -> Int -> IO (PackWords a) # pokeElemOff :: Ptr (PackWords a) -> Int -> PackWords a -> IO () # peekByteOff :: Ptr b -> Int -> IO (PackWords a) # pokeByteOff :: Ptr b -> Int -> PackWords a -> IO () # peek :: Ptr (PackWords a) -> IO (PackWords a) # poke :: Ptr (PackWords a) -> PackWords a -> IO () #
Binary (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods put :: PackWords a -> Put # get :: Get (PackWords a) # putList :: [PackWords a] -> Put #
NFData (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods rnf :: PackWords a -> () #
(Finitary a, 1 <= Cardinality a) => Finitary (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Associated Types type Cardinality (PackWords a) :: Nat Methods fromFinite :: Finite (Cardinality (PackWords a)) -> PackWords a toFinite :: PackWords a -> Finite (Cardinality (PackWords a)) start :: PackWords a end :: PackWords a previous :: Alternative f => PackWords a -> f (PackWords a) next :: Alternative f => PackWords a -> f (PackWords a)
(Finitary a, 1 <= Cardinality a) => Unbox (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords
Hashable (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords Methods hashWithSalt :: Int -> PackWords a -> Int hash :: PackWords a -> Int
newtype MVector s (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords newtype MVector s (PackWords a) = MV_PackWords (MVector s Word)
type Cardinality (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords type Cardinality (PackWords a) = Cardinality a
newtype Vector (PackWords a) Source #
Instance details Defined in Data.Finitary.PackWords newtype Vector (PackWords a) = V_PackWords (Vector Word)

pattern Packed :: forall (a :: Type). (Finitary a, 1 <= Cardinality a) => PackWords a -> a Source #

To provide (something that resembles a) data constructor for PackWords, we provide the following pattern. It can be used like any other data constructor:

import Data.Finitary.PackWords

anInt :: PackWords Int
anInt = Packed 10

isPackedEven :: PackWords Int -> Bool
isPackedEven (Packed x) = even x

Every pattern match, and data constructor call, performs a \(\Theta(\log_{\texttt{Cardinality Word}}(\texttt{Cardinality a}))\) encoding or decoding of a. Use with this in mind.