A newtype wrapper with a custom instance of Data.Vector.Unboxed, which packs booleans as efficient as possible (8 values per byte). Vectors of Bit use 8x less memory than vectors of Bool (which stores one value per byte). but random writes are up to 10% slower.

Flip the bit at the given position. No bounds checks are performed. Equivalent to flip unsafeModify complement, but up to 2x faster.

In general there is no reason to unsafeModify bit vectors: either you modify it with id (which is id altogether) or with complement (which is unsafeFlipBit).

>>> :set -XOverloadedLists
>>> Data.Vector.Unboxed.modify (`unsafeFlipBit` 2) [1,1,1,1]
[1,1,0,1]

Flip the bit at the given position. Equivalent to flip modify complement, but up to 2x faster.

In general there is no reason to modify bit vectors: either you modify it with id (which is id altogether) or with complement (which is flipBit).

>>> :set -XOverloadedLists
>>> Data.Vector.Unboxed.modify (`flipBit` 2) [1,1,1,1]
[1,1,0,1]

Cast an unboxed vector of words to an unboxed vector of bits. Cf. castFromWordsM.

>>> :set -XOverloadedLists
>>> castFromWords [123]
[1,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Try to cast an unboxed vector of bits to an unboxed vector of words. It succeeds if a vector of bits is aligned. Use cloneToWords otherwise. Cf. castToWordsM.

castToWords (castFromWords v) == Just v

Clone an unboxed vector of bits to a new unboxed vector of words. If the bits don't completely fill the words, the last word will be zero-padded. Cf. cloneToWordsM.

>>> :set -XOverloadedLists
>>> cloneToWords [1,1,0,1,1,1,1]
[123]

Cast a unboxed vector of Word8 to an unboxed vector of bits.

>>> :set -XOverloadedLists
>>> castFromWords8 [123]
[1,1,0,1,1,1,1,0]

Try to cast an unboxed vector of bits to an unboxed vector of Word8. It succeeds if a vector of bits is aligned. Use cloneToWords8 otherwise.

castToWords8 (castFromWords8 v) == Just v

Clone an unboxed vector of bits to a new unboxed vector of Word8. If the bits don't completely fill the bytes, the last Word8 will be zero-padded.

>>> :set -XOverloadedLists
>>> cloneToWords8 [1,1,0,1,1,1,1]
[123]

Clone a ByteString to a new unboxed vector of bits.

>>> :set -XOverloadedStrings
>>> cloneFromByteString "abc"
[1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]

Clone an unboxed vector of bits to a new ByteString. If the bits don't completely fill the bytes, the last character will be zero-padded.

>>> :set -XOverloadedLists
>>> cloneToByteString [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1]
"ab#"

Zip two vectors with the given function. Similar to zipWith, but up to 1000x (!) faster.

For sufficiently dense sets, represented as bitmaps, zipBits is up to 32x faster than union, intersection, etc.

Users are strongly encouraged to enable flag libgmp for the ultimate performance of zipBits.

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> zipBits (.&.) [1,1,0] [0,1,1] -- intersection
[0,1,0]
>>> zipBits (.|.) [1,1,0] [0,1,1] -- union
[1,1,1]
>>> zipBits (\x y -> x .&. complement y) [1,1,0] [0,1,1] -- difference
[1,0,0]
>>> zipBits xor [1,1,0] [0,1,1] -- symmetric difference
[1,0,1]

Map a vectors with the given function. Similar to map, but faster.

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> mapBits complement [0,1,1]
[1,0,0]

Invert (flip) all bits.

Users are strongly encouraged to enable flag libgmp for the ultimate performance of invertBits.

>>> :set -XOverloadedLists
>>> invertBits [0,1,0,1,0]
[1,0,1,0,1]

Reverse the order of bits.

>>> :set -XOverloadedLists
>>> reverseBits [1,1,0,1,0]
[0,1,0,1,1]

Consider using vector-rotcev package to reverse vectors in O(1) time.

Return the index of the first bit in the vector with the specified value, if any. Similar to elemIndex, but up to 64x faster.

>>> :set -XOverloadedLists
>>> bitIndex 1 [0,0,1,0,1]
Just 2
>>> bitIndex 1 [0,0,0,0,0]
Nothing

bitIndex bit == nthBitIndex bit 1

One can also use it to reduce a vector with disjunction or conjunction:

import Data.Maybe
isAnyBitSet   = isJust    . bitIndex 1
areAllBitsSet = isNothing . bitIndex 0

Return the index of the n-th bit in the vector with the specified value, if any. Here n is 1-based and the index is 0-based. Non-positive n results in an error.

>>> :set -XOverloadedLists
>>> nthBitIndex 1 2 [0,1,0,1,1,1,0] -- 2nd occurence of 1
Just 3
>>> nthBitIndex 1 5 [0,1,0,1,1,1,0] -- 5th occurence of 1
Nothing

One can use nthBitIndex to implement to implement select{0,1} queries for succinct dictionaries.

Return the number of set bits in a vector (population count, popcount).

Users are strongly encouraged to enable flag libgmp for the ultimate performance of countBits.

>>> :set -XOverloadedLists
>>> countBits [1,1,0,1,0,1]
4

One can combine countBits with take to implement rank{0,1} queries for succinct dictionaries.

Return 0-based indices of set bits in a vector.

>>> :set -XOverloadedLists
>>> listBits [1,1,0,1,0,1]
[0,1,3,5]

For each set bit of the first argument, deposit the corresponding bit of the second argument to the result. Similar to the parallel deposit instruction (PDEP).

>>> :set -XOverloadedLists
>>> selectBits [0,1,0,1,1] [1,1,0,0,1]
[1,0,1]

Here is a reference (but slow) implementation:

import qualified Data.Vector.Unboxed as U
selectBits mask ws == U.map snd (U.filter (unBit . fst) (U.zip mask ws))

For each unset bit of the first argument, deposit the corresponding bit of the second argument to the result.

>>> :set -XOverloadedLists
>>> excludeBits [0,1,0,1,1] [1,1,0,0,1]
[1,0]

Here is a reference (but slow) implementation:

import qualified Data.Vector.Unboxed as U
excludeBits mask ws == U.map snd (U.filter (not . unBit . fst) (U.zip mask ws))

Cast a vector of words to a vector of bits. Cf. castFromWords.

Try to cast a vector of bits to a vector of words. It succeeds if a vector of bits is aligned. Use cloneToWordsM otherwise. Cf. castToWords.

Clone a vector of bits to a new unboxed vector of words. If the bits don't completely fill the words, the last word will be zero-padded. Cf. cloneToWords.

Zip two vectors with the given function. rewriting contents of the second argument. Cf. zipBits.

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> Data.Vector.Unboxed.modify (zipInPlace (.&.) [1,1,0]) [0,1,1]
[0,1,0]

Warning: if the immutable vector is shorter than the mutable one, it is a caller's responsibility to trim the result:

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> Data.Vector.Unboxed.modify (zipInPlace (.&.) [1,1,0]) [0,1,1,1,1,1]
[0,1,0,1,1,1] -- note trailing garbage

Apply a function to a mutable vector bitwise, rewriting its contents. Cf. mapBits.

>>> :set -XOverloadedLists
>>> import Data.Bits
>>> Data.Vector.Unboxed.modify (mapInPlace complement) [0,1,1]
[1,0,0]

Invert (flip) all bits in-place.

>>> :set -XOverloadedLists
>>> Data.Vector.Unboxed.modify invertInPlace [0,1,0,1,0]
[1,0,1,0,1]

Reverse the order of bits in-place.

>>> :set -XOverloadedLists
>>> Data.Vector.Unboxed.modify reverseInPlace [1,1,0,1,0]
[0,1,0,1,1]

Consider using vector-rotcev package to reverse vectors in O(1) time.

Same as selectBits, but deposit selected bits in-place. Returns a number of selected bits. It is caller's responsibility to trim the result to this number.

>>> :set -XOverloadedLists
>>> import Control.Monad.ST (runST)
>>> import qualified Data.Vector.Unboxed as U
>>> runST $ do { vec <- U.unsafeThaw [1,1,0,0,1]; n <- selectBitsInPlace [0,1,0,1,1] vec; U.take n <$> U.unsafeFreeze vec }
[1,0,1]

Same as excludeBits, but deposit excluded bits in-place. Returns a number of excluded bits. It is caller's responsibility to trim the result to this number.

>>> :set -XOverloadedLists
>>> import Control.Monad.ST (runST)
>>> import qualified Data.Vector.Unboxed as U
>>> runST $ do { vec <- U.unsafeThaw [1,1,0,0,1]; n <- excludeBitsInPlace [0,1,0,1,1] vec; U.take n <$> U.unsafeFreeze vec }
[1,0]

Binary polynomials of one variable, backed by an unboxed Vector Bit.

Polynomials are stored normalized, without leading zero coefficients.

Ord instance does not make much sense mathematically, it is defined only for the sake of Set, Map, etc.

>>> :set -XBinaryLiterals
>>> -- (1 + x) (1 + x + x^2) = 1 + x^3 (mod 2)
>>> 0b11 * 0b111 :: F2Poly
0b1001

Convert F2Poly to a vector of coefficients (first element corresponds to a constant term).

>>> :set -XBinaryLiterals
>>> unF2Poly 0b1101
[1,0,1,1]

Make F2Poly from a list of coefficients (first element corresponds to a constant term).

>>> :set -XOverloadedLists
>>> toF2Poly [1,0,1,1,0,0]
0b1101

Execute the extended Euclidean algorithm. For polynomials a and b, compute their unique greatest common divisor g and the unique coefficient polynomial s satisfying as + bt = g.

>>> :set -XBinaryLiterals
>>> gcdExt 0b101 0b0101
(0b101,0b0)
>>> gcdExt 0b11 0b111
(0b1,0b10)