Safe Haskell | None |
---|---|
Language | Haskell2010 |
Set with and without interfaces. We provide instances for sets, and
sets with one or two interfaces. The First
and Last
annotation is
purely cosmetical (apart from introducing type safety).
- newtype Interface t = Iter {}
- data First
- data Last
- data Any
- newtype BitSet = BitSet {}
- type BS1I i = BitSet :> Interface i
- type BS2I i j = (BitSet :> Interface i) :> Interface j
- class SetPredSucc s where
- type family Mask s :: *
- data Fixed t = Fixed {
- getFixedMask :: Mask t
- getFixed :: !t
- class ApplyMask s where
- testBsS :: BitSet -> Maybe (Fixed BitSet)
- arbitraryBitSetMax :: Integer
newtype
s, data
types, class
es.
Certain sets have an interface, a particular element with special
meaning. In this module, certain ``meanings'' are already provided.
These include a First
element and a Last
element. We phantom-type
these to reduce programming overhead.
Newtype for a bitset. We'd use Word
s but that requires more shape
instances.
TODO can we use Word
s now?
class SetPredSucc s where Source
Successor and Predecessor for sets. Designed as a class to accomodate sets with interfaces and without interfaces with one function.
The functions are not written recursively, as we currently only have three cases, and we do not want to "reset" while generating successors and predecessors.
Note that sets have a partial order. Within the group of element with
the same popCount
, we use popPermutation
which has the same stepping
order for both, setSucc
and setPred
.
setSucc :: s -> s -> s -> Maybe s Source
Set successor. The first argument is the lower set limit, the second the upper set limit, the third the current set.
setPred :: s -> s -> s -> Maybe s Source
Set predecessor. The first argument is the lower set limit, the second the upper set limit, the third the current set.
SetPredSucc BitSet | |
SetPredSucc (Fixed ((:>) ((:>) BitSet (Interface i)) (Interface j))) | |
SetPredSucc (Fixed ((:>) BitSet (Interface i))) | |
SetPredSucc (Fixed BitSet) | |
SetPredSucc ((:>) ((:>) BitSet (Interface i)) (Interface j)) | |
SetPredSucc ((:>) BitSet (Interface i)) |
type family Mask s :: * Source
Masks are used quite often for different types of bitsets. We liberate them as a type family.
Fixed
allows us to fix some or all bits of a bitset, thereby
providing succ/pred
operations which are only partially free.
The mask is lazy, this allows us to have undefined
for l
and h
.
f = getFixedMask .&. getFixed
are the fixed bits.
n = getFixed .&. complement getFixedMask
are the free bits.
to = complement getFixed
is the to move mask
n' = popShiftR to n
yields the population after the move
p = popPermutation undefined n'
yields the new population permutation
p' = popShiftL to p
yields the population moved back
final = p' .|. f
Fixed | |
|
(Unbox t0, Unbox (Mask t0)) => Vector Vector (Fixed t) | |
(Unbox t0, Unbox (Mask t0)) => MVector MVector (Fixed t) | |
(Eq t, Eq (Mask t)) => Eq (Fixed t) | |
(Ord t, Ord (Mask t)) => Ord (Fixed t) | |
(Read t, Read (Mask t)) => Read (Fixed t) | |
(Show t, Show (Mask t)) => Show (Fixed t) | |
(Generic t, Generic (Mask t)) => Generic (Fixed t) | |
(Arbitrary t, Arbitrary (Mask t)) => Arbitrary (Fixed t) | |
(Generic t, Generic (Mask t), Binary t, Binary (Mask t)) => Binary (Fixed t) | |
(Generic t, Generic (Mask t), Serialize t, Serialize (Mask t)) => Serialize (Fixed t) | |
NFData (Fixed t) | |
(Unbox t0, Unbox (Mask t0)) => Unbox (Fixed t) | |
SetPredSucc (Fixed ((:>) ((:>) BitSet (Interface i)) (Interface j))) | |
SetPredSucc (Fixed ((:>) BitSet (Interface i))) | |
SetPredSucc (Fixed BitSet) | |
data MVector s0 (Fixed t0) = MV_Fixed (MVector s (Mask t, t)) | |
type Rep (Fixed t) | |
data Vector (Fixed t0) = V_Fixed (Vector (Mask t, t)) |
class ApplyMask s where Source
Assuming a bitset on bits [0 .. highbit]
, we can apply a mask that
stretches out those bits over [0 .. higherBit]
with highbit <=
higherBit
. Any active interfaces are correctly set as well.