-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Fast, packed, strict and lazy bit streams with stream fusion
--
-- Fast, packed, strict and lazy bit vectors with stream fusion. This is
-- like bytestring but stores bits instead of bytes. NOTE: GHC
-- 7.0.1 fails to fuse almost every cases of bitstream fusion, producing
-- very large and not-so-fast object code. See:
-- http://hackage.haskell.org/trac/ghc/ticket/4397
@package bitstream
@version 0.1
-- | Some functions currently missing from
-- Data.Vector.Fusion.Stream.Monadic.
module Data.Bitstream.Fusion.Monadic
genericLength :: (Monad m, Num n) => Stream m α -> m n
genericTake :: (Monad m, Integral n) => n -> Stream m α -> Stream m α
genericDrop :: (Monad m, Integral n) => n -> Stream m α -> Stream m α
genericIndex :: (Monad m, Integral n) => Stream m α -> n -> m α
genericReplicate :: (Monad m, Integral n) => n -> α -> Stream m α
genericReplicateM :: (Monad m, Integral n) => n -> m α -> Stream m α
genericUnfoldrN :: (Monad m, Integral n) => n -> (β -> Maybe (α, β)) -> β -> Stream m α
genericUnfoldrNM :: (Monad m, Integral n) => n -> (β -> m (Maybe (α, β))) -> β -> Stream m α
genericFindIndex :: (Monad m, Integral n) => (α -> Bool) -> Stream m α -> m (Maybe n)
genericFindIndexM :: (Monad m, Integral n) => (α -> m Bool) -> Stream m α -> m (Maybe n)
genericIndexed :: (Monad m, Integral n) => Stream m α -> Stream m (n, α)
-- | Some functions currently missing from
-- Data.Vector.Fusion.Stream.
module Data.Bitstream.Fusion
genericLength :: Num n => Stream α -> n
genericTake :: Integral n => n -> Stream α -> Stream α
genericDrop :: Integral n => n -> Stream α -> Stream α
genericIndex :: Integral n => Stream α -> n -> α
genericReplicate :: Integral n => n -> α -> Stream α
genericUnfoldrN :: Integral n => n -> (β -> Maybe (α, β)) -> β -> Stream α
genericFindIndex :: Integral n => (α -> Bool) -> Stream α -> Maybe n
genericIndexed :: Integral n => Stream α -> Stream (n, α)
-- | Generic interface to diverse types of Bitstream.
module Data.Bitstream.Generic
-- | Class of diverse types of Bitstream.
--
-- Methods of this class are functions of Bitstreams that is
-- either basic functions to implement other ones, or have to preserve
-- their packet/chunk structure for efficiency and strictness behaviour.
--
-- Minimum complete implementation: All but cons',
-- concat, replicate and partition.
class Bitstream α
stream :: Bitstream α => α -> Stream Bool
unstream :: Bitstream α => Stream Bool -> α
cons :: Bitstream α => Bool -> α -> α
cons' :: Bitstream α => Bool -> α -> α
snoc :: Bitstream α => α -> Bool -> α
append :: Bitstream α => α -> α -> α
tail :: Bitstream α => α -> α
init :: Bitstream α => α -> α
map :: Bitstream α => (Bool -> Bool) -> α -> α
reverse :: Bitstream α => α -> α
concat :: Bitstream α => [α] -> α
scanl :: Bitstream α => (Bool -> Bool -> Bool) -> Bool -> α -> α
replicate :: (Bitstream α, Integral n) => n -> Bool -> α
take :: (Bitstream α, Integral n) => n -> α -> α
drop :: (Bitstream α, Integral n) => n -> α -> α
takeWhile :: Bitstream α => (Bool -> Bool) -> α -> α
dropWhile :: Bitstream α => (Bool -> Bool) -> α -> α
filter :: Bitstream α => (Bool -> Bool) -> α -> α
partition :: Bitstream α => (Bool -> Bool) -> α -> (α, α)
-- | O(n) Convert a [Bool] into a Bitstream.
pack :: Bitstream α => [Bool] -> α
-- | O(n) Convert a Bitstream into a [Bool].
unpack :: Bitstream α => α -> [Bool]
-- | O(1) The empty Bitstream.
empty :: Bitstream α => α
-- | O(1) Convert a Bool into a Bitstream.
singleton :: Bitstream α => Bool -> α
-- | O(1) Extract the first bit of a non-empty Bitstream. An
-- exception will be thrown if empty.
head :: Bitstream α => α -> Bool
-- | strict: O(1), lazy: O(n) Extract the last bit of a finite
-- Bitstream. An exception will be thrown if empty.
last :: Bitstream α => α -> Bool
-- | O(1) Test whether a Bitstream is empty.
null :: Bitstream α => α -> Bool
-- | O(n) Retern the length of a finite Bitstream.
length :: Bitstream α => Num n => α -> n
-- | Map a function over a Bitstream and concatenate the results.
concatMap :: Bitstream α => (Bool -> α) -> α -> α
-- | O(n) foldl, applied to a binary operator, a starting
-- value (typically the left-identity of the operator), and a
-- Bitstream, reduces the Bitstream using the binary
-- operator, from left to right:
--
--
-- foldl f z [x1, x2, ..., xn] == (...((z f x1) f x2) f...) f xn
--
--
-- The Bitstream must be finite.
foldl :: Bitstream α => (β -> Bool -> β) -> β -> α -> β
-- | O(n) foldl' is a variant of foldl that is strict
-- on the accumulator.
foldl' :: Bitstream α => (β -> Bool -> β) -> β -> α -> β
-- | O(n) foldl1 is a variant of foldl that has no
-- starting value argument, and thus must be applied to non-empty
-- Bitstreams.
foldl1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> Bool
-- | O(n) A strict version of foldl1.
foldl1' :: Bitstream α => (Bool -> Bool -> Bool) -> α -> Bool
-- | O(n) foldr, applied to a binary operator, a starting
-- value (typically the right-identity of the operator), and a
-- Bitstream, reduces the Bitstream using the binary
-- operator, from right to left:
--
--
-- foldr f z [x1, x2, ..., xn] == x1 f (x2 f ... (xn f z)...)
--
foldr :: Bitstream α => (Bool -> β -> β) -> β -> α -> β
-- | O(n) foldr1 is a variant of foldr that has no
-- starting value argument, and thus must be applied to non-empty
-- Bitstreams.
foldr1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> Bool
-- | O(n) and returns the conjunction of a Bool list.
-- For the result to be True, the Bitstream must be finite;
-- False, however, results from a False value at a finite
-- index of a finite or infinite Bitstream. Note that strict
-- Bitstreams are always finite.
and :: Bitstream α => α -> Bool
-- | O(n) or returns the disjunction of a Bool list.
-- For the result to be False, the Bitstream must be
-- finite; True, however, results from a True value at a
-- finite index of a finite or infinite Bitstream. Note that
-- strict Bitstreams are always finite.
or :: Bitstream α => α -> Bool
-- | O(n) Applied to a predicate and a Bitstream, any
-- determines if any bit of the Bitstream satisfies the predicate.
-- For the result to be False, the Bitstream must be
-- finite; True, however, results from a True value for the
-- predicate applied to a bit at a finite index of a finite or infinite
-- Bitstream.
any :: Bitstream α => (Bool -> Bool) -> α -> Bool
-- | O(n) Applied to a predicate and a Bitstream, all
-- determines if all bits of the Bitstream satisfy the predicate.
-- For the result to be True, the Bitstream must be finite;
-- False, however, results from a False value for the
-- predicate applied to a bit at a finite index of a finite or infinite
-- Bitstream.
all :: Bitstream α => (Bool -> Bool) -> α -> Bool
-- | O(n) The unfoldr function is a `dual' to foldr:
-- while foldr reduces a Bitstream to a summary value,
-- unfoldr builds a Bitstream from a seed value. The
-- function takes the element and returns Nothing if it is done
-- producing the Bitstream or returns Just (a, b),
-- in which case, a is a prepended to the Bitstream and
-- b is used as the next element in a recursive call.
unfoldr :: Bitstream α => (β -> Maybe (Bool, β)) -> β -> α
-- | O(n) unfoldrN is a variant of unfoldr but
-- constructs a Bitstream with at most n bits.
unfoldrN :: (Bitstream α, Integral n) => n -> (β -> Maybe (Bool, β)) -> β -> α
-- | O(n) scanl1 is a variant of scanl that has no
-- starting value argument:
--
--
-- scanl1 f [x1, x2, ...] == [x1, x1 f x2, ...]
--
scanl1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> α
-- | O(n) scanr is the right-to-left dual of scanl.
-- Note that
--
--
-- head (scanr f z xs) == foldr f z xs
--
scanr :: Bitstream α => (Bool -> Bool -> Bool) -> Bool -> α -> α
-- | O(n) scanr1 is a variant of scanr that has no
-- starting value argument.
scanr1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> α
-- | O(n) span, applied to a predicate p and a
-- Bitstream xs, returns a tuple where first element is
-- longest prefix (possibly empty) of xs of bits that
-- satisfy p and second element is the remainder of the
-- Bitstream.
--
-- span p xs is equivalent to (takeWhile p xs,
-- dropWhile p xs)
span :: Bitstream α => (Bool -> Bool) -> α -> (α, α)
-- | O(n) break, applied to a predicate p and a
-- Bitstream xs, returns a tuple where first element is
-- longest prefix (possibly empty) of xs of bits that
-- do not satisfy p and second element is the remainder
-- of the Bitstream.
--
-- break p is equivalent to span (not
-- . p).
break :: Bitstream α => (Bool -> Bool) -> α -> (α, α)
-- | O(n) elem is the Bitstream membership predicate,
-- usually written in infix form, e.g., x `elem` xs. For the
-- result to be False, the Bitstream must be finite;
-- True, however, results from an bit equal to x found at
-- a finite index of a finite or infinite Bitstream.
elem :: Bitstream α => Bool -> α -> Bool
-- | O(n) notElem is the negation of elem.
notElem :: Bitstream α => Bool -> α -> Bool
-- | O(n) The find function takes a predicate and a
-- Bitstream and returns the bit in the Bitstream matching
-- the predicate, or Nothing if there is no such bit.
find :: Bitstream α => (Bool -> Bool) -> α -> Maybe Bool
-- | O(n) Bitstream index (subscript) operator, starting from
-- 0.
(!!) :: (Bitstream α, Integral n) => α -> n -> Bool
-- | O(n) The elemIndex function returns the index of the
-- first bit in the given Bitstream which is equal to the query
-- bit, or Nothing if there is no such bit.
elemIndex :: (Bitstream α, Integral n) => Bool -> α -> Maybe n
-- | O(n) The elemIndices function extends elemIndex,
-- by returning the indices of all bits equal to the query bit, in
-- ascending order.
elemIndices :: (Bitstream α, Integral n) => Bool -> α -> [n]
-- | O(n) The findIndex function takes a predicate and a
-- Bitstream and returns the index of the first bit in the
-- Bitstream satisfying the predicate, or Nothing if there
-- is no such bit.
findIndex :: (Bitstream α, Integral n) => (Bool -> Bool) -> α -> Maybe n
-- | O(n) The findIndices function extends findIndex,
-- by returning the indices of all bits satisfying the predicate, in
-- ascending order.
findIndices :: (Bitstream α, Integral n) => (Bool -> Bool) -> α -> [n]
-- | O(min(m, n)) zip takes two Bitstreams and returns
-- a list of corresponding bit pairs. If one input Bitstream is
-- short, excess bits of the longer Bitstream are discarded.
zip :: Bitstream α => α -> α -> [(Bool, Bool)]
-- | The zip3 function takes three Bitstreams and returns a
-- list of triples, analogous to zip.
zip3 :: Bitstream α => α -> α -> α -> [(Bool, Bool, Bool)]
-- | The zip4 function takes four lists and returns a list of
-- quadruples, analogous to zip.
zip4 :: Bitstream α => α -> α -> α -> α -> [(Bool, Bool, Bool, Bool)]
-- | The zip5 function takes five Bitstreams and returns a
-- list of five-tuples, analogous to zip.
zip5 :: Bitstream α => α -> α -> α -> α -> α -> [(Bool, Bool, Bool, Bool, Bool)]
-- | The zip6 function takes six Bitstreams and returns a
-- list of six-tuples, analogous to zip.
zip6 :: Bitstream α => α -> α -> α -> α -> α -> α -> [(Bool, Bool, Bool, Bool, Bool, Bool)]
-- | O(min(m, n)) zipWith generalises zip by zipping
-- with the function given as the first argument, instead of a tupling
-- function.
zipWith :: Bitstream α => (Bool -> Bool -> β) -> α -> α -> [β]
-- | The zipWith3 function takes a function which combines three
-- bits, as well as three Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith3 :: Bitstream α => (Bool -> Bool -> Bool -> β) -> α -> α -> α -> [β]
-- | The zipWith4 function takes a function which combines four
-- bits, as well as four Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith4 :: Bitstream α => (Bool -> Bool -> Bool -> Bool -> β) -> α -> α -> α -> α -> [β]
-- | The zipWith5 function takes a function which combines five
-- bits, as well as five Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith5 :: Bitstream α => (Bool -> Bool -> Bool -> Bool -> Bool -> β) -> α -> α -> α -> α -> α -> [β]
-- | The zipWith6 function takes a function which combines six bits,
-- as well as six Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith6 :: Bitstream α => (Bool -> Bool -> Bool -> Bool -> Bool -> Bool -> β) -> α -> α -> α -> α -> α -> α -> [β]
-- | O(min(m, n)) unzip transforms a list of bit pairs into a
-- Bitstream of first components and a Bitstream of second
-- components.
unzip :: Bitstream α => [(Bool, Bool)] -> (α, α)
-- | The unzip3 function takes a list of triples and returns three
-- Bitstreams, analogous to unzip.
unzip3 :: Bitstream α => [(Bool, Bool, Bool)] -> (α, α, α)
-- | The unzip4 function takes a list of quadruples and returns four
-- Bitstreams, analogous to unzip.
unzip4 :: Bitstream α => [(Bool, Bool, Bool, Bool)] -> (α, α, α, α)
-- | The unzip5 function takes a list of five-tuples and returns
-- five Bitstreams, analogous to unzip.
unzip5 :: Bitstream α => [(Bool, Bool, Bool, Bool, Bool)] -> (α, α, α, α, α)
-- | The unzip6 function takes a list of six-tuples and returns six
-- Bitstreams, analogous to unzip.
unzip6 :: Bitstream α => [(Bool, Bool, Bool, Bool, Bool, Bool)] -> (α, α, α, α, α, α)
-- | (∅) = empty
--
-- U+2205, EMPTY SET
(∅) :: Bitstream α => α
-- | (⧺) = append
--
-- U+29FA, DOUBLE PLUS
(⧺) :: Bitstream α => α -> α -> α
-- | (∈) = elem
--
-- U+2208, ELEMENT OF
(∈) :: Bitstream α => Bool -> α -> Bool
-- | (∋) = flip (∈)
--
-- U+220B, CONTAINS AS MEMBER
(∋) :: Bitstream α => α -> Bool -> Bool
-- | (∉) = notElem
--
-- U+2209, NOT AN ELEMENT OF
(∉) :: Bitstream α => Bool -> α -> Bool
-- | (∌) = flip (∉)
--
-- U+220C, DOES NOT CONTAIN AS MEMBER
(∌) :: Bitstream α => α -> Bool -> Bool
-- | For internal use only.
module Data.Bitstream.Packet
-- | Left bitstreams interpret an octet as a vector of bits whose
-- LSB comes first and MSB comes last e.g.
--
--
-- - 11110000 => [False, False, False, False, True, True , True ,
-- True]
-- - 10010100 => [False, False, True , False, True, False, False,
-- True]
--
data Left
-- | Right bitstreams interpret an octet as a vector of bits whose
-- MSB comes first and LSB comes last e.g.
--
--
-- - 11110000 => [True, True , True , True, False, False, False,
-- False]
-- - 10010100 => [True, False, False, True, False, True , False,
-- False]
--
data Right
-- | Packets are strict Bitstreams having at most 8 bits.
data Packet d
-- | O(1) full p == True iff
-- length p == 8, otherwise it returns False.
full :: Packet d -> Bool
-- | O(1) Convert an octet to Packet.
fromOctet :: Word8 -> Packet d
-- | O(1) toOctet p converts a Packet
-- p to an octet, padding with zeroes if length p
-- < 8.
toOctet :: Packet d -> Word8
-- | O(1) Change the direction of Packet from Left to
-- Right. Bit directions only affect octet-based operations such
-- as toOctet.
packetLToR :: Packet Left -> Packet Right
-- | O(1) Change the direction of Packet from Right to
-- Left. Bit directions only affect octet-based operations such as
-- toOctet.
packetRToL :: Packet Right -> Packet Left
instance Eq (Packet d)
instance Bitstream (Packet Right)
instance Bitstream (Packet Left)
instance Ord (Packet Right)
instance Ord (Packet Left)
instance Show (Packet Right)
instance Show (Packet Left)
instance Storable (Packet d)
-- | Fast, packed, strict bit streams (i.e. list of Bools) with
-- semi-automatic stream fusion.
--
-- This module is intended to be imported qualified, to avoid
-- name clashes with Prelude functions. e.g.
--
--
-- import qualified Data.BitStream as BS
--
--
-- Strict Bitstreams are made of strict Vector of
-- Packets, and each Packets have at least 1 bit.
module Data.Bitstream
-- | A space-efficient representation of a Bool vector, supporting
-- many efficient operations. Bitstreams have an idea of
-- directions controlling how octets are interpreted as bits.
-- There are two types of concrete Bitstreams:
-- Bitstream Left and Bitstream
-- Right.
data Bitstream d
-- | Left bitstreams interpret an octet as a vector of bits whose
-- LSB comes first and MSB comes last e.g.
--
--
-- - 11110000 => [False, False, False, False, True, True , True ,
-- True]
-- - 10010100 => [False, False, True , False, True, False, False,
-- True]
--
data Left
-- | Right bitstreams interpret an octet as a vector of bits whose
-- MSB comes first and LSB comes last e.g.
--
--
-- - 11110000 => [True, True , True , True, False, False, False,
-- False]
-- - 10010100 => [True, False, False, True, False, True , False,
-- False]
--
data Right
-- | O(1) The empty Bitstream.
empty :: Bitstream α => α
-- | (∅) = empty
--
-- U+2205, EMPTY SET
(∅) :: Bitstream α => α
-- | O(1) Convert a Bool into a Bitstream.
singleton :: Bitstream α => Bool -> α
-- | O(n) Convert a [Bool] into a Bitstream.
pack :: Bitstream α => [Bool] -> α
-- | O(n) Convert a Bitstream into a [Bool].
unpack :: Bitstream α => α -> [Bool]
-- | O(1) Convert a Vector of Packets into a
-- Bitstream.
fromPackets :: Vector (Packet d) -> Bitstream d
-- | O(1) Convert a Bitstream into a Vector of
-- Packets.
toPackets :: Bitstream d -> Vector (Packet d)
-- | O(n) Convert a strict ByteString into a strict
-- Bitstream.
fromByteString :: ByteString -> Bitstream d
-- | O(n) toByteString bits converts a strict
-- Bitstream bits into a strict ByteString. The
-- resulting octets will be padded with zeroes if the length of
-- bs is not multiple of 8.
toByteString :: Bitstream (Packet d) => Bitstream d -> ByteString
-- | O(n) Explicitly convert a Bitstream into a Stream
-- of Bool.
--
-- Bitstream operations are automatically fused whenever it's
-- possible, safe, and effective to do so, but sometimes you may find the
-- rules are too conservative. These two functions stream and
-- unstream provide a means for coercive stream fusion.
--
-- You should be careful when you use stream. Most functions in
-- this package are optimised to minimise frequency of memory allocations
-- and copyings, but getting Bitstreams back from
-- Stream Bool requires the whole Bitstream
-- to be constructed from scratch. Moreover, for lazy Bitstreams
-- this leads to be an incorrect strictness behaviour because lazy
-- Bitstreams are represented as lists of strict Bitstream
-- chunks but stream can't preserve the original chunk structure.
-- Let's say you have a lazy Bitstream with the following chunks:
--
--
-- bs = [chunk1, chunk2, chunk3, ...]
--
--
-- and you want to drop the first bit of such stream. Our tail is
-- only strict on the chunk1 and will produce the following
-- chunks:
--
--
-- tail bs = [chunk0, chunk1', chunk2, chunk3, ...]
--
--
-- where chunk0 is a singleton vector of the first packet of
-- chunk1 whose first bit is dropped, and chunk1' is a
-- vector of remaining packets of the chunk1. Neither
-- chunk2 nor chunk3 have to be evaluated here as you
-- might expect.
--
-- But think about the following expression:
--
--
-- import qualified Data.Vector.Fusion.Stream as Stream
-- unstream $ Stream.tail $ stream bs
--
--
-- the resulting chunk structure will be:
--
--
-- [chunk1', chunk2', chunk3', ...]
--
--
-- where each and every chunks are slightly different from the original
-- chunks, and this time chunk1' has the same length as
-- chunk1 but the last bit of chunk1' is from the first
-- bit of chunk2. This means when you next time apply some
-- functions strict on the first chunk, you end up fully evaluating
-- chunk2 as well as chunk1 and this can be a serious
-- misbehaviour for lazy Bitstreams.
--
-- The automatic fusion rules are carefully designed to fire only when
-- there aren't any reason to preserve the original packet / chunk
-- structure.
stream :: Bitstream α => α -> Stream Bool
-- | O(n) Convert a Stream of Bool into a
-- Bitstream.
unstream :: Bitstream α => Stream Bool -> α
-- | O(n) Convert a Bitstream Left into a
-- Bitstream Right. Bit directions only affect
-- octet-based operations such as toByteString.
directionLToR :: Bitstream Left -> Bitstream Right
-- | O(n) Convert a Bitstream Right into a
-- Bitstream Left. Bit directions only affect
-- octet-based operations such as toByteString.
directionRToL :: Bitstream Right -> Bitstream Left
-- | strict: O(n), lazy: O(1) cons is an analogous to
-- (:) for lists.
cons :: Bitstream α => Bool -> α -> α
-- | O(n) Append a bit to the end of a Bitstream.
snoc :: Bitstream α => α -> Bool -> α
-- | O(n) Append two Bitstreams.
append :: Bitstream α => α -> α -> α
-- | (⧺) = append
--
-- U+29FA, DOUBLE PLUS
(⧺) :: Bitstream α => α -> α -> α
-- | O(1) Extract the first bit of a non-empty Bitstream. An
-- exception will be thrown if empty.
head :: Bitstream α => α -> Bool
-- | strict: O(1), lazy: O(n) Extract the last bit of a finite
-- Bitstream. An exception will be thrown if empty.
last :: Bitstream α => α -> Bool
-- | O(1) Extract the bits after the head of a non-empty
-- Bitstream. An exception will be thrown if empty.
tail :: Bitstream α => α -> α
-- | O(n) Return all the bits of a Bitstream except the last
-- one. An exception will be thrown if empty.
init :: Bitstream α => α -> α
-- | O(1) Test whether a Bitstream is empty.
null :: Bitstream α => α -> Bool
-- | O(n) Retern the length of a finite Bitstream.
length :: Bitstream α => Num n => α -> n
-- | O(n) Map a function over a Bitstream.
map :: Bitstream α => (Bool -> Bool) -> α -> α
-- | O(n) Reverse a Bitstream.
reverse :: Bitstream α => α -> α
-- | O(n) foldl, applied to a binary operator, a starting
-- value (typically the left-identity of the operator), and a
-- Bitstream, reduces the Bitstream using the binary
-- operator, from left to right:
--
--
-- foldl f z [x1, x2, ..., xn] == (...((z f x1) f x2) f...) f xn
--
--
-- The Bitstream must be finite.
foldl :: Bitstream α => (β -> Bool -> β) -> β -> α -> β
-- | O(n) foldl' is a variant of foldl that is strict
-- on the accumulator.
foldl' :: Bitstream α => (β -> Bool -> β) -> β -> α -> β
-- | O(n) foldl1 is a variant of foldl that has no
-- starting value argument, and thus must be applied to non-empty
-- Bitstreams.
foldl1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> Bool
-- | O(n) A strict version of foldl1.
foldl1' :: Bitstream α => (Bool -> Bool -> Bool) -> α -> Bool
-- | O(n) foldr, applied to a binary operator, a starting
-- value (typically the right-identity of the operator), and a
-- Bitstream, reduces the Bitstream using the binary
-- operator, from right to left:
--
--
-- foldr f z [x1, x2, ..., xn] == x1 f (x2 f ... (xn f z)...)
--
foldr :: Bitstream α => (Bool -> β -> β) -> β -> α -> β
-- | O(n) foldr1 is a variant of foldr that has no
-- starting value argument, and thus must be applied to non-empty
-- Bitstreams.
foldr1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> Bool
-- | O(n) Concatenate all Bitstreams in the list.
concat :: Bitstream α => [α] -> α
-- | Map a function over a Bitstream and concatenate the results.
concatMap :: Bitstream α => (Bool -> α) -> α -> α
-- | O(n) and returns the conjunction of a Bool list.
-- For the result to be True, the Bitstream must be finite;
-- False, however, results from a False value at a finite
-- index of a finite or infinite Bitstream. Note that strict
-- Bitstreams are always finite.
and :: Bitstream α => α -> Bool
-- | O(n) or returns the disjunction of a Bool list.
-- For the result to be False, the Bitstream must be
-- finite; True, however, results from a True value at a
-- finite index of a finite or infinite Bitstream. Note that
-- strict Bitstreams are always finite.
or :: Bitstream α => α -> Bool
-- | O(n) Applied to a predicate and a Bitstream, any
-- determines if any bit of the Bitstream satisfies the predicate.
-- For the result to be False, the Bitstream must be
-- finite; True, however, results from a True value for the
-- predicate applied to a bit at a finite index of a finite or infinite
-- Bitstream.
any :: Bitstream α => (Bool -> Bool) -> α -> Bool
-- | O(n) Applied to a predicate and a Bitstream, all
-- determines if all bits of the Bitstream satisfy the predicate.
-- For the result to be True, the Bitstream must be finite;
-- False, however, results from a False value for the
-- predicate applied to a bit at a finite index of a finite or infinite
-- Bitstream.
all :: Bitstream α => (Bool -> Bool) -> α -> Bool
-- | O(n) scanl is similar to foldl, but returns a
-- Bitstream of successive reduced bits from the left:
--
--
-- scanl f z [x1, x2, ...] == [z, z f x1, (z f x1) f x2, ...]
--
--
-- Note that
--
--
-- last (scanl f z xs) == foldl f z xs
--
scanl :: Bitstream α => (Bool -> Bool -> Bool) -> Bool -> α -> α
-- | O(n) scanl1 is a variant of scanl that has no
-- starting value argument:
--
--
-- scanl1 f [x1, x2, ...] == [x1, x1 f x2, ...]
--
scanl1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> α
-- | O(n) scanr is the right-to-left dual of scanl.
-- Note that
--
--
-- head (scanr f z xs) == foldr f z xs
--
scanr :: Bitstream α => (Bool -> Bool -> Bool) -> Bool -> α -> α
-- | O(n) scanr1 is a variant of scanr that has no
-- starting value argument.
scanr1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> α
-- | O(n) replicate n x is a Bitstream of
-- length n with x the value of every bit.
replicate :: (Bitstream α, Integral n) => n -> Bool -> α
-- | O(n) The unfoldr function is a `dual' to foldr:
-- while foldr reduces a Bitstream to a summary value,
-- unfoldr builds a Bitstream from a seed value. The
-- function takes the element and returns Nothing if it is done
-- producing the Bitstream or returns Just (a, b),
-- in which case, a is a prepended to the Bitstream and
-- b is used as the next element in a recursive call.
unfoldr :: Bitstream α => (β -> Maybe (Bool, β)) -> β -> α
-- | O(n) unfoldrN is a variant of unfoldr but
-- constructs a Bitstream with at most n bits.
unfoldrN :: (Bitstream α, Integral n) => n -> (β -> Maybe (Bool, β)) -> β -> α
-- | O(n) take n, applied to a Bitstream
-- xs, returns the prefix of xs of length n,
-- or xs itself if n > length xs.
take :: (Bitstream α, Integral n) => n -> α -> α
-- | O(n) drop n xs returns the suffix of
-- xs after the first n bits, or empty if n
-- > length xs.
drop :: (Bitstream α, Integral n) => n -> α -> α
-- | O(n) takeWhile, applied to a predicate p and a
-- Bitstream xs, returns the longest prefix (possibly
-- empty) of xs of bits that satisfy p.
takeWhile :: Bitstream α => (Bool -> Bool) -> α -> α
-- | O(n) dropWhile p xs returns the suffix
-- remaining after takeWhile p xs.
dropWhile :: Bitstream α => (Bool -> Bool) -> α -> α
-- | O(n) span, applied to a predicate p and a
-- Bitstream xs, returns a tuple where first element is
-- longest prefix (possibly empty) of xs of bits that
-- satisfy p and second element is the remainder of the
-- Bitstream.
--
-- span p xs is equivalent to (takeWhile p xs,
-- dropWhile p xs)
span :: Bitstream α => (Bool -> Bool) -> α -> (α, α)
-- | O(n) break, applied to a predicate p and a
-- Bitstream xs, returns a tuple where first element is
-- longest prefix (possibly empty) of xs of bits that
-- do not satisfy p and second element is the remainder
-- of the Bitstream.
--
-- break p is equivalent to span (not
-- . p).
break :: Bitstream α => (Bool -> Bool) -> α -> (α, α)
-- | O(n) elem is the Bitstream membership predicate,
-- usually written in infix form, e.g., x `elem` xs. For the
-- result to be False, the Bitstream must be finite;
-- True, however, results from an bit equal to x found at
-- a finite index of a finite or infinite Bitstream.
elem :: Bitstream α => Bool -> α -> Bool
-- | (∈) = elem
--
-- U+2208, ELEMENT OF
(∈) :: Bitstream α => Bool -> α -> Bool
-- | (∋) = flip (∈)
--
-- U+220B, CONTAINS AS MEMBER
(∋) :: Bitstream α => α -> Bool -> Bool
-- | O(n) notElem is the negation of elem.
notElem :: Bitstream α => Bool -> α -> Bool
-- | (∉) = notElem
--
-- U+2209, NOT AN ELEMENT OF
(∉) :: Bitstream α => Bool -> α -> Bool
-- | (∌) = flip (∉)
--
-- U+220C, DOES NOT CONTAIN AS MEMBER
(∌) :: Bitstream α => α -> Bool -> Bool
-- | O(n) The find function takes a predicate and a
-- Bitstream and returns the bit in the Bitstream matching
-- the predicate, or Nothing if there is no such bit.
find :: Bitstream α => (Bool -> Bool) -> α -> Maybe Bool
-- | O(n) filter, applied to a predicate and a
-- Bitstream, returns the Bitstream of those bits that
-- satisfy the predicate.
filter :: Bitstream α => (Bool -> Bool) -> α -> α
-- | O(n) The partition function takes a predicate and a
-- Bitstream and returns the pair of Bitstreams of bits
-- which do and do not satisfy the predicate, respectively.
partition :: Bitstream α => (Bool -> Bool) -> α -> (α, α)
-- | O(n) Bitstream index (subscript) operator, starting from
-- 0.
(!!) :: (Bitstream α, Integral n) => α -> n -> Bool
-- | O(n) The elemIndex function returns the index of the
-- first bit in the given Bitstream which is equal to the query
-- bit, or Nothing if there is no such bit.
elemIndex :: (Bitstream α, Integral n) => Bool -> α -> Maybe n
-- | O(n) The elemIndices function extends elemIndex,
-- by returning the indices of all bits equal to the query bit, in
-- ascending order.
elemIndices :: (Bitstream α, Integral n) => Bool -> α -> [n]
-- | O(n) The findIndex function takes a predicate and a
-- Bitstream and returns the index of the first bit in the
-- Bitstream satisfying the predicate, or Nothing if there
-- is no such bit.
findIndex :: (Bitstream α, Integral n) => (Bool -> Bool) -> α -> Maybe n
-- | O(n) The findIndices function extends findIndex,
-- by returning the indices of all bits satisfying the predicate, in
-- ascending order.
findIndices :: (Bitstream α, Integral n) => (Bool -> Bool) -> α -> [n]
-- | O(min(m, n)) zip takes two Bitstreams and returns
-- a list of corresponding bit pairs. If one input Bitstream is
-- short, excess bits of the longer Bitstream are discarded.
zip :: Bitstream α => α -> α -> [(Bool, Bool)]
-- | The zip3 function takes three Bitstreams and returns a
-- list of triples, analogous to zip.
zip3 :: Bitstream α => α -> α -> α -> [(Bool, Bool, Bool)]
-- | The zip4 function takes four lists and returns a list of
-- quadruples, analogous to zip.
zip4 :: Bitstream α => α -> α -> α -> α -> [(Bool, Bool, Bool, Bool)]
-- | The zip5 function takes five Bitstreams and returns a
-- list of five-tuples, analogous to zip.
zip5 :: Bitstream α => α -> α -> α -> α -> α -> [(Bool, Bool, Bool, Bool, Bool)]
-- | The zip6 function takes six Bitstreams and returns a
-- list of six-tuples, analogous to zip.
zip6 :: Bitstream α => α -> α -> α -> α -> α -> α -> [(Bool, Bool, Bool, Bool, Bool, Bool)]
-- | O(min(m, n)) zipWith generalises zip by zipping
-- with the function given as the first argument, instead of a tupling
-- function.
zipWith :: Bitstream α => (Bool -> Bool -> β) -> α -> α -> [β]
-- | The zipWith3 function takes a function which combines three
-- bits, as well as three Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith3 :: Bitstream α => (Bool -> Bool -> Bool -> β) -> α -> α -> α -> [β]
-- | The zipWith4 function takes a function which combines four
-- bits, as well as four Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith4 :: Bitstream α => (Bool -> Bool -> Bool -> Bool -> β) -> α -> α -> α -> α -> [β]
-- | The zipWith5 function takes a function which combines five
-- bits, as well as five Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith5 :: Bitstream α => (Bool -> Bool -> Bool -> Bool -> Bool -> β) -> α -> α -> α -> α -> α -> [β]
-- | The zipWith6 function takes a function which combines six bits,
-- as well as six Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith6 :: Bitstream α => (Bool -> Bool -> Bool -> Bool -> Bool -> Bool -> β) -> α -> α -> α -> α -> α -> α -> [β]
-- | O(min(m, n)) unzip transforms a list of bit pairs into a
-- Bitstream of first components and a Bitstream of second
-- components.
unzip :: Bitstream α => [(Bool, Bool)] -> (α, α)
-- | The unzip3 function takes a list of triples and returns three
-- Bitstreams, analogous to unzip.
unzip3 :: Bitstream α => [(Bool, Bool, Bool)] -> (α, α, α)
-- | The unzip4 function takes a list of quadruples and returns four
-- Bitstreams, analogous to unzip.
unzip4 :: Bitstream α => [(Bool, Bool, Bool, Bool)] -> (α, α, α, α)
-- | The unzip5 function takes a list of five-tuples and returns
-- five Bitstreams, analogous to unzip.
unzip5 :: Bitstream α => [(Bool, Bool, Bool, Bool, Bool)] -> (α, α, α, α, α)
-- | The unzip6 function takes a list of six-tuples and returns six
-- Bitstreams, analogous to unzip.
unzip6 :: Bitstream α => [(Bool, Bool, Bool, Bool, Bool, Bool)] -> (α, α, α, α, α, α)
-- | O(n) Read a Bitstream from the stdin strictly,
-- equivalent to hGetContents stdin. The Handle is
-- closed after the contents have been read.
getContents :: Bitstream (Packet d) => IO (Bitstream d)
-- | O(n) Write a Bitstream to the stdout, equivalent to
-- hPut stdout.
putBits :: Bitstream (Packet d) => Bitstream d -> IO ()
-- | The interact function takes a function of type
-- Bitstream d -> Bitstream d as its argument.
-- The entire input from the stdin is passed to this function as its
-- argument, and the resulting Bitstream is output on the stdout.
interact :: Bitstream (Packet d) => (Bitstream d -> Bitstream d) -> IO ()
-- | O(n) Read an entire file strictly into a Bitstream.
readFile :: Bitstream (Packet d) => FilePath -> IO (Bitstream d)
-- | O(n) Write a Bitstream to a file.
writeFile :: Bitstream (Packet d) => FilePath -> Bitstream d -> IO ()
-- | O(n) Append a Bitstream to a file.
appendFile :: Bitstream (Packet d) => FilePath -> Bitstream d -> IO ()
-- | O(n) Read entire handle contents strictly into a
-- Bitstream.
--
-- This function reads chunks at a time, doubling the chunksize on each
-- read. The final buffer is then realloced to the appropriate size. For
-- files > half of available memory, this may lead to memory
-- exhaustion. Consider using readFile in this case.
--
-- The Handle is closed once the contents have been read, or if an
-- exception is thrown.
hGetContents :: Bitstream (Packet d) => Handle -> IO (Bitstream d)
-- | O(n) hGet h n reads a Bitstream directly
-- from the specified Handle h. First argument h
-- is the Handle to read from, and the second n is the
-- number of octets to read, not bits. It returns the
-- octets read, up to n, or null if EOF has been reached.
--
-- If the handle is a pipe or socket, and the writing end is closed,
-- hGet will behave as if EOF was reached.
hGet :: Bitstream (Packet d) => Handle -> Int -> IO (Bitstream d)
-- | O(n) Like hGet, except that a shorter Bitstream
-- may be returned if there are not enough octets immediately available
-- to satisfy the whole request. hGetSome only blocks if there is
-- no data available, and EOF has not yet been reached.
hGetSome :: Bitstream (Packet d) => Handle -> Int -> IO (Bitstream d)
-- | O(n) hGetNonBlocking is similar to hGet, except
-- that it will never block waiting for data to become available. If
-- there is no data available to be read, hGetNonBlocking returns
-- empty.
hGetNonBlocking :: Bitstream (Packet d) => Handle -> Int -> IO (Bitstream d)
-- | O(n) Write a Bitstream to the given Handle.
hPut :: Bitstream (Packet d) => Handle -> Bitstream d -> IO ()
instance Bitstream (Packet d) => Bitstream (Bitstream d)
instance Bitstream (Packet d) => Monoid (Bitstream d)
instance Bitstream (Packet d) => Ord (Bitstream d)
instance Bitstream (Packet d) => Eq (Bitstream d)
instance Show (Packet d) => Show (Bitstream d)
-- | Fast, packed, lazy bit streams (i.e. list of Bools) with
-- semi-automatic stream fusion.
--
-- This module is intended to be imported qualified, to avoid
-- name clashes with Prelude functions. e.g.
--
--
-- import qualified Data.BitStream.Lazy as LS
--
--
-- Lazy Bitstreams are made of possibly infinite list of strict
-- Bitstreams as chunks, and each chunks have at least 1 bit.
module Data.Bitstream.Lazy
-- | A space-efficient representation of a Bool vector, supporting
-- many efficient operations. Bitstreams have an idea of
-- directions controlling how octets are interpreted as bits.
-- There are two types of concrete Bitstreams:
-- Bitstream Left and Bitstream
-- Right.
data Bitstream d
-- | Left bitstreams interpret an octet as a vector of bits whose
-- LSB comes first and MSB comes last e.g.
--
--
-- - 11110000 => [False, False, False, False, True, True , True ,
-- True]
-- - 10010100 => [False, False, True , False, True, False, False,
-- True]
--
data Left
-- | Right bitstreams interpret an octet as a vector of bits whose
-- MSB comes first and LSB comes last e.g.
--
--
-- - 11110000 => [True, True , True , True, False, False, False,
-- False]
-- - 10010100 => [True, False, False, True, False, True , False,
-- False]
--
data Right
-- | O(1) The empty Bitstream.
empty :: Bitstream α => α
-- | (∅) = empty
--
-- U+2205, EMPTY SET
(∅) :: Bitstream α => α
-- | O(1) Convert a Bool into a Bitstream.
singleton :: Bitstream α => Bool -> α
-- | O(n) Convert a [Bool] into a Bitstream.
pack :: Bitstream α => [Bool] -> α
-- | O(n) Convert a Bitstream into a [Bool].
unpack :: Bitstream α => α -> [Bool]
-- | O(n) Convert a list of chunks, strict Bitstreams, into a
-- lazy Bitstream.
fromChunks :: Bitstream (Packet d) => [Bitstream d] -> Bitstream d
-- | O(n) Convert a lazy Bitstream into a list of chunks,
-- strict Bitstreams.
toChunks :: Bitstream d -> [Bitstream d]
-- | O(n) Convert a lazy ByteString into a lazy
-- Bitstream.
fromByteString :: Bitstream (Packet d) => ByteString -> Bitstream d
-- | O(n) toByteString bits converts a lazy
-- Bitstream bits into a lazy ByteString. The
-- resulting octets will be padded with zeroes if bs is finite
-- and its length is not multiple of 8.
toByteString :: Bitstream (Packet d) => Bitstream d -> ByteString
-- | O(n) Explicitly convert a Bitstream into a Stream
-- of Bool.
--
-- Bitstream operations are automatically fused whenever it's
-- possible, safe, and effective to do so, but sometimes you may find the
-- rules are too conservative. These two functions stream and
-- unstream provide a means for coercive stream fusion.
--
-- You should be careful when you use stream. Most functions in
-- this package are optimised to minimise frequency of memory allocations
-- and copyings, but getting Bitstreams back from
-- Stream Bool requires the whole Bitstream
-- to be constructed from scratch. Moreover, for lazy Bitstreams
-- this leads to be an incorrect strictness behaviour because lazy
-- Bitstreams are represented as lists of strict Bitstream
-- chunks but stream can't preserve the original chunk structure.
-- Let's say you have a lazy Bitstream with the following chunks:
--
--
-- bs = [chunk1, chunk2, chunk3, ...]
--
--
-- and you want to drop the first bit of such stream. Our tail is
-- only strict on the chunk1 and will produce the following
-- chunks:
--
--
-- tail bs = [chunk0, chunk1', chunk2, chunk3, ...]
--
--
-- where chunk0 is a singleton vector of the first packet of
-- chunk1 whose first bit is dropped, and chunk1' is a
-- vector of remaining packets of the chunk1. Neither
-- chunk2 nor chunk3 have to be evaluated here as you
-- might expect.
--
-- But think about the following expression:
--
--
-- import qualified Data.Vector.Fusion.Stream as Stream
-- unstream $ Stream.tail $ stream bs
--
--
-- the resulting chunk structure will be:
--
--
-- [chunk1', chunk2', chunk3', ...]
--
--
-- where each and every chunks are slightly different from the original
-- chunks, and this time chunk1' has the same length as
-- chunk1 but the last bit of chunk1' is from the first
-- bit of chunk2. This means when you next time apply some
-- functions strict on the first chunk, you end up fully evaluating
-- chunk2 as well as chunk1 and this can be a serious
-- misbehaviour for lazy Bitstreams.
--
-- The automatic fusion rules are carefully designed to fire only when
-- there aren't any reason to preserve the original packet / chunk
-- structure.
stream :: Bitstream α => α -> Stream Bool
-- | O(n) Convert a Stream of Bool into a
-- Bitstream.
unstream :: Bitstream α => Stream Bool -> α
-- | O(n) Convert a Bitstream Left into a
-- Bitstream Right. Bit directions only affect
-- octet-based operations such as toByteString.
directionLToR :: Bitstream Left -> Bitstream Right
-- | O(n) Convert a Bitstream Right into a
-- Bitstream Left. Bit directions only affect
-- octet-based operations such as toByteString.
directionRToL :: Bitstream Right -> Bitstream Left
-- | strict: O(n), lazy: O(1) cons is an analogous to
-- (:) for lists.
cons :: Bitstream α => Bool -> α -> α
-- | O(n) For strict Bitstreams, cons' is exactly the
-- same as cons.
--
-- For lazy ones, cons' is strict in the Bitstream we are
-- consing onto. More precisely, it forces the first chunk to be
-- evaluated. It does this because, for space efficiency, it may coalesce
-- the new bit onto the first chunk rather than starting a new chunk.
cons' :: Bitstream α => Bool -> α -> α
-- | O(n) Append a bit to the end of a Bitstream.
snoc :: Bitstream α => α -> Bool -> α
-- | O(n) Append two Bitstreams.
append :: Bitstream α => α -> α -> α
-- | (⧺) = append
--
-- U+29FA, DOUBLE PLUS
(⧺) :: Bitstream α => α -> α -> α
-- | O(1) Extract the first bit of a non-empty Bitstream. An
-- exception will be thrown if empty.
head :: Bitstream α => α -> Bool
-- | strict: O(1), lazy: O(n) Extract the last bit of a finite
-- Bitstream. An exception will be thrown if empty.
last :: Bitstream α => α -> Bool
-- | O(1) Extract the bits after the head of a non-empty
-- Bitstream. An exception will be thrown if empty.
tail :: Bitstream α => α -> α
-- | O(n) Return all the bits of a Bitstream except the last
-- one. An exception will be thrown if empty.
init :: Bitstream α => α -> α
-- | O(1) Test whether a Bitstream is empty.
null :: Bitstream α => α -> Bool
-- | O(n) Retern the length of a finite Bitstream.
length :: Bitstream α => Num n => α -> n
-- | O(n) Map a function over a Bitstream.
map :: Bitstream α => (Bool -> Bool) -> α -> α
-- | O(n) Reverse a Bitstream.
reverse :: Bitstream α => α -> α
-- | O(n) foldl, applied to a binary operator, a starting
-- value (typically the left-identity of the operator), and a
-- Bitstream, reduces the Bitstream using the binary
-- operator, from left to right:
--
--
-- foldl f z [x1, x2, ..., xn] == (...((z f x1) f x2) f...) f xn
--
--
-- The Bitstream must be finite.
foldl :: Bitstream α => (β -> Bool -> β) -> β -> α -> β
-- | O(n) foldl' is a variant of foldl that is strict
-- on the accumulator.
foldl' :: Bitstream α => (β -> Bool -> β) -> β -> α -> β
-- | O(n) foldl1 is a variant of foldl that has no
-- starting value argument, and thus must be applied to non-empty
-- Bitstreams.
foldl1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> Bool
-- | O(n) A strict version of foldl1.
foldl1' :: Bitstream α => (Bool -> Bool -> Bool) -> α -> Bool
-- | O(n) foldr, applied to a binary operator, a starting
-- value (typically the right-identity of the operator), and a
-- Bitstream, reduces the Bitstream using the binary
-- operator, from right to left:
--
--
-- foldr f z [x1, x2, ..., xn] == x1 f (x2 f ... (xn f z)...)
--
foldr :: Bitstream α => (Bool -> β -> β) -> β -> α -> β
-- | O(n) foldr1 is a variant of foldr that has no
-- starting value argument, and thus must be applied to non-empty
-- Bitstreams.
foldr1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> Bool
-- | O(n) Concatenate all Bitstreams in the list.
concat :: Bitstream α => [α] -> α
-- | Map a function over a Bitstream and concatenate the results.
concatMap :: Bitstream α => (Bool -> α) -> α -> α
-- | O(n) and returns the conjunction of a Bool list.
-- For the result to be True, the Bitstream must be finite;
-- False, however, results from a False value at a finite
-- index of a finite or infinite Bitstream. Note that strict
-- Bitstreams are always finite.
and :: Bitstream α => α -> Bool
-- | O(n) or returns the disjunction of a Bool list.
-- For the result to be False, the Bitstream must be
-- finite; True, however, results from a True value at a
-- finite index of a finite or infinite Bitstream. Note that
-- strict Bitstreams are always finite.
or :: Bitstream α => α -> Bool
-- | O(n) Applied to a predicate and a Bitstream, any
-- determines if any bit of the Bitstream satisfies the predicate.
-- For the result to be False, the Bitstream must be
-- finite; True, however, results from a True value for the
-- predicate applied to a bit at a finite index of a finite or infinite
-- Bitstream.
any :: Bitstream α => (Bool -> Bool) -> α -> Bool
-- | O(n) Applied to a predicate and a Bitstream, all
-- determines if all bits of the Bitstream satisfy the predicate.
-- For the result to be True, the Bitstream must be finite;
-- False, however, results from a False value for the
-- predicate applied to a bit at a finite index of a finite or infinite
-- Bitstream.
all :: Bitstream α => (Bool -> Bool) -> α -> Bool
-- | O(n) scanl is similar to foldl, but returns a
-- Bitstream of successive reduced bits from the left:
--
--
-- scanl f z [x1, x2, ...] == [z, z f x1, (z f x1) f x2, ...]
--
--
-- Note that
--
--
-- last (scanl f z xs) == foldl f z xs
--
scanl :: Bitstream α => (Bool -> Bool -> Bool) -> Bool -> α -> α
-- | O(n) scanl1 is a variant of scanl that has no
-- starting value argument:
--
--
-- scanl1 f [x1, x2, ...] == [x1, x1 f x2, ...]
--
scanl1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> α
-- | O(n) scanr is the right-to-left dual of scanl.
-- Note that
--
--
-- head (scanr f z xs) == foldr f z xs
--
scanr :: Bitstream α => (Bool -> Bool -> Bool) -> Bool -> α -> α
-- | O(n) scanr1 is a variant of scanr that has no
-- starting value argument.
scanr1 :: Bitstream α => (Bool -> Bool -> Bool) -> α -> α
-- | O(n) iterate f x returns an infinite
-- Bitstream of repeated applications of f to x:
--
--
-- iterate f x == [x, f x, f (f x), ...]
--
iterate :: Bitstream (Packet d) => (Bool -> Bool) -> Bool -> Bitstream d
-- | O(n) repeat x is an infinite Bitstream,
-- with x the value of every bits.
repeat :: Bitstream (Packet d) => Bool -> Bitstream d
-- | O(n) replicate n x is a Bitstream of
-- length n with x the value of every bit.
replicate :: (Bitstream α, Integral n) => n -> Bool -> α
-- | O(n) cycle ties a finite Bitstream into a
-- circular one, or equivalently, the infinite repetition of the original
-- Bitstream. It is the identity on infinite Bitstreams.
cycle :: Bitstream (Packet d) => Bitstream d -> Bitstream d
-- | O(n) The unfoldr function is a `dual' to foldr:
-- while foldr reduces a Bitstream to a summary value,
-- unfoldr builds a Bitstream from a seed value. The
-- function takes the element and returns Nothing if it is done
-- producing the Bitstream or returns Just (a, b),
-- in which case, a is a prepended to the Bitstream and
-- b is used as the next element in a recursive call.
unfoldr :: Bitstream α => (β -> Maybe (Bool, β)) -> β -> α
-- | O(n) unfoldrN is a variant of unfoldr but
-- constructs a Bitstream with at most n bits.
unfoldrN :: (Bitstream α, Integral n) => n -> (β -> Maybe (Bool, β)) -> β -> α
-- | O(n) take n, applied to a Bitstream
-- xs, returns the prefix of xs of length n,
-- or xs itself if n > length xs.
take :: (Bitstream α, Integral n) => n -> α -> α
-- | O(n) drop n xs returns the suffix of
-- xs after the first n bits, or empty if n
-- > length xs.
drop :: (Bitstream α, Integral n) => n -> α -> α
-- | O(n) takeWhile, applied to a predicate p and a
-- Bitstream xs, returns the longest prefix (possibly
-- empty) of xs of bits that satisfy p.
takeWhile :: Bitstream α => (Bool -> Bool) -> α -> α
-- | O(n) dropWhile p xs returns the suffix
-- remaining after takeWhile p xs.
dropWhile :: Bitstream α => (Bool -> Bool) -> α -> α
-- | O(n) span, applied to a predicate p and a
-- Bitstream xs, returns a tuple where first element is
-- longest prefix (possibly empty) of xs of bits that
-- satisfy p and second element is the remainder of the
-- Bitstream.
--
-- span p xs is equivalent to (takeWhile p xs,
-- dropWhile p xs)
span :: Bitstream α => (Bool -> Bool) -> α -> (α, α)
-- | O(n) break, applied to a predicate p and a
-- Bitstream xs, returns a tuple where first element is
-- longest prefix (possibly empty) of xs of bits that
-- do not satisfy p and second element is the remainder
-- of the Bitstream.
--
-- break p is equivalent to span (not
-- . p).
break :: Bitstream α => (Bool -> Bool) -> α -> (α, α)
-- | O(n) elem is the Bitstream membership predicate,
-- usually written in infix form, e.g., x `elem` xs. For the
-- result to be False, the Bitstream must be finite;
-- True, however, results from an bit equal to x found at
-- a finite index of a finite or infinite Bitstream.
elem :: Bitstream α => Bool -> α -> Bool
-- | (∈) = elem
--
-- U+2208, ELEMENT OF
(∈) :: Bitstream α => Bool -> α -> Bool
-- | (∋) = flip (∈)
--
-- U+220B, CONTAINS AS MEMBER
(∋) :: Bitstream α => α -> Bool -> Bool
-- | O(n) notElem is the negation of elem.
notElem :: Bitstream α => Bool -> α -> Bool
-- | (∉) = notElem
--
-- U+2209, NOT AN ELEMENT OF
(∉) :: Bitstream α => Bool -> α -> Bool
-- | (∌) = flip (∉)
--
-- U+220C, DOES NOT CONTAIN AS MEMBER
(∌) :: Bitstream α => α -> Bool -> Bool
-- | O(n) The find function takes a predicate and a
-- Bitstream and returns the bit in the Bitstream matching
-- the predicate, or Nothing if there is no such bit.
find :: Bitstream α => (Bool -> Bool) -> α -> Maybe Bool
-- | O(n) filter, applied to a predicate and a
-- Bitstream, returns the Bitstream of those bits that
-- satisfy the predicate.
filter :: Bitstream α => (Bool -> Bool) -> α -> α
-- | O(n) The partition function takes a predicate and a
-- Bitstream and returns the pair of Bitstreams of bits
-- which do and do not satisfy the predicate, respectively.
partition :: Bitstream α => (Bool -> Bool) -> α -> (α, α)
-- | O(n) Bitstream index (subscript) operator, starting from
-- 0.
(!!) :: (Bitstream α, Integral n) => α -> n -> Bool
-- | O(n) The elemIndex function returns the index of the
-- first bit in the given Bitstream which is equal to the query
-- bit, or Nothing if there is no such bit.
elemIndex :: (Bitstream α, Integral n) => Bool -> α -> Maybe n
-- | O(n) The elemIndices function extends elemIndex,
-- by returning the indices of all bits equal to the query bit, in
-- ascending order.
elemIndices :: (Bitstream α, Integral n) => Bool -> α -> [n]
-- | O(n) The findIndex function takes a predicate and a
-- Bitstream and returns the index of the first bit in the
-- Bitstream satisfying the predicate, or Nothing if there
-- is no such bit.
findIndex :: (Bitstream α, Integral n) => (Bool -> Bool) -> α -> Maybe n
-- | O(n) The findIndices function extends findIndex,
-- by returning the indices of all bits satisfying the predicate, in
-- ascending order.
findIndices :: (Bitstream α, Integral n) => (Bool -> Bool) -> α -> [n]
-- | O(min(m, n)) zip takes two Bitstreams and returns
-- a list of corresponding bit pairs. If one input Bitstream is
-- short, excess bits of the longer Bitstream are discarded.
zip :: Bitstream α => α -> α -> [(Bool, Bool)]
-- | The zip3 function takes three Bitstreams and returns a
-- list of triples, analogous to zip.
zip3 :: Bitstream α => α -> α -> α -> [(Bool, Bool, Bool)]
-- | The zip4 function takes four lists and returns a list of
-- quadruples, analogous to zip.
zip4 :: Bitstream α => α -> α -> α -> α -> [(Bool, Bool, Bool, Bool)]
-- | The zip5 function takes five Bitstreams and returns a
-- list of five-tuples, analogous to zip.
zip5 :: Bitstream α => α -> α -> α -> α -> α -> [(Bool, Bool, Bool, Bool, Bool)]
-- | The zip6 function takes six Bitstreams and returns a
-- list of six-tuples, analogous to zip.
zip6 :: Bitstream α => α -> α -> α -> α -> α -> α -> [(Bool, Bool, Bool, Bool, Bool, Bool)]
-- | O(min(m, n)) zipWith generalises zip by zipping
-- with the function given as the first argument, instead of a tupling
-- function.
zipWith :: Bitstream α => (Bool -> Bool -> β) -> α -> α -> [β]
-- | The zipWith3 function takes a function which combines three
-- bits, as well as three Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith3 :: Bitstream α => (Bool -> Bool -> Bool -> β) -> α -> α -> α -> [β]
-- | The zipWith4 function takes a function which combines four
-- bits, as well as four Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith4 :: Bitstream α => (Bool -> Bool -> Bool -> Bool -> β) -> α -> α -> α -> α -> [β]
-- | The zipWith5 function takes a function which combines five
-- bits, as well as five Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith5 :: Bitstream α => (Bool -> Bool -> Bool -> Bool -> Bool -> β) -> α -> α -> α -> α -> α -> [β]
-- | The zipWith6 function takes a function which combines six bits,
-- as well as six Bitstreams and returns a list of their
-- point-wise combination, analogous to zipWith.
zipWith6 :: Bitstream α => (Bool -> Bool -> Bool -> Bool -> Bool -> Bool -> β) -> α -> α -> α -> α -> α -> α -> [β]
-- | O(min(m, n)) unzip transforms a list of bit pairs into a
-- Bitstream of first components and a Bitstream of second
-- components.
unzip :: Bitstream α => [(Bool, Bool)] -> (α, α)
-- | The unzip3 function takes a list of triples and returns three
-- Bitstreams, analogous to unzip.
unzip3 :: Bitstream α => [(Bool, Bool, Bool)] -> (α, α, α)
-- | The unzip4 function takes a list of quadruples and returns four
-- Bitstreams, analogous to unzip.
unzip4 :: Bitstream α => [(Bool, Bool, Bool, Bool)] -> (α, α, α, α)
-- | The unzip5 function takes a list of five-tuples and returns
-- five Bitstreams, analogous to unzip.
unzip5 :: Bitstream α => [(Bool, Bool, Bool, Bool, Bool)] -> (α, α, α, α, α)
-- | The unzip6 function takes a list of six-tuples and returns six
-- Bitstreams, analogous to unzip.
unzip6 :: Bitstream α => [(Bool, Bool, Bool, Bool, Bool, Bool)] -> (α, α, α, α, α, α)
-- | O(n) getContents is equivalent to hGetContents
-- stdin. Will read lazily.
getContents :: Bitstream (Packet d) => IO (Bitstream d)
-- | O(n) Write a Bitstream to stdout, equivalent to
-- hPut stdout.
putBits :: Bitstream (Packet d) => Bitstream d -> IO ()
-- | The interact function takes a function of type
-- Bitstream d -> Bitstream d as its argument.
-- The entire input from the stdin is lazily passed to this function as
-- its argument, and the resulting Bitstream is output on the
-- stdout.
interact :: Bitstream (Packet d) => (Bitstream d -> Bitstream d) -> IO ()
-- | O(n) Read an entire file lazily into a Bitstream.
readFile :: Bitstream (Packet d) => FilePath -> IO (Bitstream d)
-- | O(n) Write a Bitstream to a file.
writeFile :: Bitstream (Packet d) => FilePath -> Bitstream d -> IO ()
-- | O(n) Append a Bitstream to a file.
appendFile :: Bitstream (Packet d) => FilePath -> Bitstream d -> IO ()
-- | O(n) Read entire handle contents lazily into a
-- Bitstream. Chunks are read on demand, using the default chunk
-- size.
--
-- Once EOF is encountered, the Handle is closed.
hGetContents :: Bitstream (Packet d) => Handle -> IO (Bitstream d)
-- | hGet h n reads a Bitstream directly from the
-- specified Handle h. First argument h is the
-- Handle to read from, and the second n is the number of
-- octets to read, not bits. It returns the octets read, up
-- to n, or null if EOF has been reached.
--
-- If the handle is a pipe or socket, and the writing end is closed,
-- hGet will behave as if EOF was reached.
hGet :: Bitstream (Packet d) => Handle -> Int -> IO (Bitstream d)
-- | O(n) hGetNonBlocking is similar to hGet, except
-- that it will never block waiting for data to become available, instead
-- it returns only whatever data is available.
hGetNonBlocking :: Bitstream (Packet d) => Handle -> Int -> IO (Bitstream d)
-- | O(n) Write a Bitstream to the given Handle.
hPut :: Bitstream (Packet d) => Handle -> Bitstream d -> IO ()
instance Bitstream (Packet d) => Bitstream (Bitstream d)
instance Bitstream (Packet d) => Monoid (Bitstream d)
instance Bitstream (Packet d) => Ord (Bitstream d)
instance Bitstream (Packet d) => Eq (Bitstream d)
instance Show (Packet d) => Show (Bitstream d)