-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Space-efficient bit vectors -- -- A newtype over Bool with a better Vector instance: 8x -- less memory, up to 1000x faster. -- -- The vector package represents unboxed arrays of Bool -- spending 1 byte (8 bits) per boolean. This library provides a newtype -- wrapper Bit and a custom instance of unboxed Vector, -- which packs bits densely, achieving 8x less memory footprint. -- The performance stays mostly the same; the most significant -- degradation happens for random writes (up to 10% slower). On the other -- hand, for certain bulk bit operations Vector Bit is up -- to 1000x faster than Vector Bool. -- --

Thread safety

-- -- -- --

Similar packages

-- -- @package bitvec @version 1.0.2.0 -- | This module exposes an interface with thread-safe writes and flips. -- Consider using Data.Bit, which is faster (up to 20%), but -- thread-unsafe. module Data.Bit.ThreadSafe -- | 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 20% slower. newtype Bit Bit :: Bool -> Bit [unBit] :: Bit -> Bool -- | Flip the bit at the given position. No bounds checks are performed. -- Equivalent to flip unsafeModify complement, but -- up to 33% faster and atomic. -- -- 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). -- -- 
--   >>> Data.Vector.Unboxed.modify (\v -> unsafeFlipBit v 1) (read "[1,1,1]")
--   [1,0,1]
--
unsafeFlipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m () -- | Flip the bit at the given position. Equivalent to flip -- modify complement, but up to 33% faster and atomic. -- -- 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). -- -- 
--   >>> Data.Vector.Unboxed.modify (\v -> flipBit v 1) (read "[1,1,1]")
--   [1,0,1]
--
flipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m () -- | Cast a vector of words to a vector of bits. Cf. castFromWordsM. -- -- 
--   >>> castFromWords (Data.Vector.Unboxed.singleton 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]
--
castFromWords :: Vector Word -> Vector Bit -- | Try to cast a vector of bits to a vector of words. It succeeds if a -- vector of bits is aligned. Use cloneToWords otherwise. Cf. -- castToWordsM. -- -- 
--   castToWords (castFromWords v) == Just v
--
castToWords :: Vector Bit -> Maybe (Vector Word) -- | 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. cloneToWordsM. -- -- 
--   >>> cloneToWords (read "[1,1,0,1,1,1,1,0]")
--   [123]
--
cloneToWords :: Vector Bit -> Vector Word -- | 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. -- -- 
--   >>> import Data.Bits
--   
--   >>> zipBits (.&.) (read "[1,1,0]") (read "[0,1,1]") -- intersection
--   [0,1,0]
--   
--   >>> zipBits (.|.) (read "[1,1,0]") (read "[0,1,1]") -- union
--   [1,1,1]
--   
--   >>> zipBits (\x y -> x .&. complement y) (read "[1,1,0]") (read "[0,1,1]") -- difference
--   [1,0,0]
--   
--   >>> zipBits xor (read "[1,1,0]") (read "[0,1,1]") -- symmetric difference
--   [1,0,1]
--
zipBits :: (forall a. Bits a => a -> a -> a) -> Vector Bit -> Vector Bit -> Vector Bit -- | Invert (flip) all bits. -- -- 
--   >>> invertBits (read "[0,1,0,1,0]")
--   [1,0,1,0,1]
--
invertBits :: Vector Bit -> Vector Bit -- | Reverse the order of bits. -- -- 
--   >>> reverseBits (read "[1,1,0,1,0]")
--   [0,1,0,1,1]
--
reverseBits :: Vector Bit -> Vector Bit -- | Return the index of the first bit in the vector with the specified -- value, if any. Similar to elemIndex, but up to 64x faster. -- -- 
--   >>> bitIndex (Bit True) (read "[0,0,1,0,1]")
--   Just 2
--   
--   >>> bitIndex (Bit True) (read "[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 (Bit True)
--   
--   >>> areAllBitsSet = isNothing . bitIndex (Bit False)
--
bitIndex :: Bit -> Vector Bit -> Maybe Int -- | 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. -- -- 
--   >>> nthBitIndex (Bit True) 2 (read "[0,1,0,1,1,1,0]")
--   Just 3
--   
--   >>> nthBitIndex (Bit True) 5 (read "[0,1,0,1,1,1,0]")
--   Nothing
--
-- -- One can use nthBitIndex to implement to implement -- select{0,1} queries for succinct dictionaries. nthBitIndex :: Bit -> Int -> Vector Bit -> Maybe Int -- | Return the number of set bits in a vector (population count, -- popcount). -- -- 
--   >>> countBits (read "[1,1,0,1,0,1]")
--   4
--
-- -- One can combine countBits with take to implement -- rank{0,1} queries for succinct dictionaries. countBits :: Vector Bit -> Int -- | Return the indices of set bits in a vector. -- -- 
--   >>> listBits (read "[1,1,0,1,0,1]")
--   [0,1,3,5]
--
listBits :: Vector Bit -> [Int] -- | 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). -- -- 
--   >>> selectBits (read "[0,1,0,1,1]") (read "[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))
--
selectBits :: Vector Bit -> Vector Bit -> Vector Bit -- | For each unset bit of the first argument, deposit the corresponding -- bit of the second argument to the result. -- -- 
--   >>> excludeBits (read "[0,1,0,1,1]") (read "[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))
--
excludeBits :: Vector Bit -> Vector Bit -> Vector Bit -- | Cast a vector of words to a vector of bits. Cf. castFromWords. castFromWordsM :: MVector s Word -> MVector s Bit -- | 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. castToWordsM :: MVector s Bit -> Maybe (MVector s Word) -- | 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. cloneToWordsM :: PrimMonad m => MVector (PrimState m) Bit -> m (MVector (PrimState m) Word) -- | Zip two vectors with the given function. rewriting contents of the -- second argument. Cf. zipBits. -- -- 
--   >>> import Data.Bits
--   
--   >>> modify (zipInPlace (.&.) (read "[1,1,0]")) (read "[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: -- -- 
--   >>> import Data.Bits
--   
--   >>> modify (zipInPlace (.&.) (read "[1,1,0]")) (read "[0,1,1,1,1,1]")
--   [0,1,0,1,1,1] -- note trailing garbage
--
zipInPlace :: forall m. PrimMonad m => (forall a. Bits a => a -> a -> a) -> Vector Bit -> MVector (PrimState m) Bit -> m () -- | Invert (flip) all bits in-place. -- -- 
--   >>> Data.Vector.Unboxed.modify invertInPlace (read "[0,1,0,1,0]")
--   [1,0,1,0,1]
--
invertInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m () -- | Reverse the order of bits in-place. -- -- 
--   >>> Data.Vector.Unboxed.modify reverseInPlace (read "[1,1,0,1,0]")
--   [0,1,0,1,1]
--
reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m () -- | Same as selectBits, but deposit selected bits in-place. Returns -- a number of selected bits. It is caller's resposibility to trim the -- result to this number. selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int -- | Same as excludeBits, but deposit excluded bits in-place. -- Returns a number of excluded bits. It is caller's resposibility to -- trim the result to this number. excludeBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int -- | 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
--
data F2Poly -- | Convert F2Poly to a vector of coefficients (first element -- corresponds to a constant term). unF2Poly :: F2Poly -> Vector Bit -- | Make F2Poly from a list of coefficients (first element -- corresponds to a constant term). toF2Poly :: Vector Bit -> F2Poly -- | 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)
--
gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly) -- | This module exposes an interface with thread-unsafe writes and flips. -- Consider using Data.Bit.ThreadSafe, which is thread-safe, but -- slower (up to 20%). module Data.Bit -- | 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. newtype Bit Bit :: Bool -> Bit [unBit] :: Bit -> Bool -- | 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). -- -- 
--   >>> Data.Vector.Unboxed.modify (\v -> unsafeFlipBit v 1) (read "[1,1,1]")
--   [1,0,1]
--
unsafeFlipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m () -- | 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). -- -- 
--   >>> Data.Vector.Unboxed.modify (\v -> flipBit v 1) (read "[1,1,1]")
--   [1,0,1]
--
flipBit :: PrimMonad m => MVector (PrimState m) Bit -> Int -> m () -- | Cast a vector of words to a vector of bits. Cf. castFromWordsM. -- -- 
--   >>> castFromWords (Data.Vector.Unboxed.singleton 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]
--
castFromWords :: Vector Word -> Vector Bit -- | Try to cast a vector of bits to a vector of words. It succeeds if a -- vector of bits is aligned. Use cloneToWords otherwise. Cf. -- castToWordsM. -- -- 
--   castToWords (castFromWords v) == Just v
--
castToWords :: Vector Bit -> Maybe (Vector Word) -- | 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. cloneToWordsM. -- -- 
--   >>> cloneToWords (read "[1,1,0,1,1,1,1,0]")
--   [123]
--
cloneToWords :: Vector Bit -> Vector Word -- | 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. -- -- 
--   >>> import Data.Bits
--   
--   >>> zipBits (.&.) (read "[1,1,0]") (read "[0,1,1]") -- intersection
--   [0,1,0]
--   
--   >>> zipBits (.|.) (read "[1,1,0]") (read "[0,1,1]") -- union
--   [1,1,1]
--   
--   >>> zipBits (\x y -> x .&. complement y) (read "[1,1,0]") (read "[0,1,1]") -- difference
--   [1,0,0]
--   
--   >>> zipBits xor (read "[1,1,0]") (read "[0,1,1]") -- symmetric difference
--   [1,0,1]
--
zipBits :: (forall a. Bits a => a -> a -> a) -> Vector Bit -> Vector Bit -> Vector Bit -- | Invert (flip) all bits. -- -- 
--   >>> invertBits (read "[0,1,0,1,0]")
--   [1,0,1,0,1]
--
invertBits :: Vector Bit -> Vector Bit -- | Reverse the order of bits. -- -- 
--   >>> reverseBits (read "[1,1,0,1,0]")
--   [0,1,0,1,1]
--
reverseBits :: Vector Bit -> Vector Bit -- | Return the index of the first bit in the vector with the specified -- value, if any. Similar to elemIndex, but up to 64x faster. -- -- 
--   >>> bitIndex (Bit True) (read "[0,0,1,0,1]")
--   Just 2
--   
--   >>> bitIndex (Bit True) (read "[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 (Bit True)
--   
--   >>> areAllBitsSet = isNothing . bitIndex (Bit False)
--
bitIndex :: Bit -> Vector Bit -> Maybe Int -- | 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. -- -- 
--   >>> nthBitIndex (Bit True) 2 (read "[0,1,0,1,1,1,0]")
--   Just 3
--   
--   >>> nthBitIndex (Bit True) 5 (read "[0,1,0,1,1,1,0]")
--   Nothing
--
-- -- One can use nthBitIndex to implement to implement -- select{0,1} queries for succinct dictionaries. nthBitIndex :: Bit -> Int -> Vector Bit -> Maybe Int -- | Return the number of set bits in a vector (population count, -- popcount). -- -- 
--   >>> countBits (read "[1,1,0,1,0,1]")
--   4
--
-- -- One can combine countBits with take to implement -- rank{0,1} queries for succinct dictionaries. countBits :: Vector Bit -> Int -- | Return the indices of set bits in a vector. -- -- 
--   >>> listBits (read "[1,1,0,1,0,1]")
--   [0,1,3,5]
--
listBits :: Vector Bit -> [Int] -- | 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). -- -- 
--   >>> selectBits (read "[0,1,0,1,1]") (read "[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))
--
selectBits :: Vector Bit -> Vector Bit -> Vector Bit -- | For each unset bit of the first argument, deposit the corresponding -- bit of the second argument to the result. -- -- 
--   >>> excludeBits (read "[0,1,0,1,1]") (read "[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))
--
excludeBits :: Vector Bit -> Vector Bit -> Vector Bit -- | Cast a vector of words to a vector of bits. Cf. castFromWords. castFromWordsM :: MVector s Word -> MVector s Bit -- | 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. castToWordsM :: MVector s Bit -> Maybe (MVector s Word) -- | 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. cloneToWordsM :: PrimMonad m => MVector (PrimState m) Bit -> m (MVector (PrimState m) Word) -- | Zip two vectors with the given function. rewriting contents of the -- second argument. Cf. zipBits. -- -- 
--   >>> import Data.Bits
--   
--   >>> modify (zipInPlace (.&.) (read "[1,1,0]")) (read "[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: -- -- 
--   >>> import Data.Bits
--   
--   >>> modify (zipInPlace (.&.) (read "[1,1,0]")) (read "[0,1,1,1,1,1]")
--   [0,1,0,1,1,1] -- note trailing garbage
--
zipInPlace :: forall m. PrimMonad m => (forall a. Bits a => a -> a -> a) -> Vector Bit -> MVector (PrimState m) Bit -> m () -- | Invert (flip) all bits in-place. -- -- 
--   >>> Data.Vector.Unboxed.modify invertInPlace (read "[0,1,0,1,0]")
--   [1,0,1,0,1]
--
invertInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m () -- | Reverse the order of bits in-place. -- -- 
--   >>> Data.Vector.Unboxed.modify reverseInPlace (read "[1,1,0,1,0]")
--   [0,1,0,1,1]
--
reverseInPlace :: PrimMonad m => MVector (PrimState m) Bit -> m () -- | Same as selectBits, but deposit selected bits in-place. Returns -- a number of selected bits. It is caller's resposibility to trim the -- result to this number. selectBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int -- | Same as excludeBits, but deposit excluded bits in-place. -- Returns a number of excluded bits. It is caller's resposibility to -- trim the result to this number. excludeBitsInPlace :: PrimMonad m => Vector Bit -> MVector (PrimState m) Bit -> m Int -- | 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
--
data F2Poly -- | Convert F2Poly to a vector of coefficients (first element -- corresponds to a constant term). unF2Poly :: F2Poly -> Vector Bit -- | Make F2Poly from a list of coefficients (first element -- corresponds to a constant term). toF2Poly :: Vector Bit -> F2Poly -- | 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)
--
gcdExt :: F2Poly -> F2Poly -> (F2Poly, F2Poly)