-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Lists of length a power of two.
--   
--   Implementation of lists whose number of elements is a power of two.
--   Binary lists have this property by definition, so it is impossible to
--   build a value with other kind of length. The implementation take
--   advantage of this property to get additional performance.
--   
--   Some algorithms are designed to work only when the input list has
--   length a power of two. Use binary lists to ensure this property in the
--   input. In addition, this library exports some useful functions for
--   this kind of algorithms. An example implementing the Fast Fourier
--   Transform is provided in the <a>Data.BinaryList</a> module.
--   
--   The package contains an additional module with utilities for the
--   (de)serialization of binary lists.
@package binary-list
@version 1.1.1.2


-- | Binary lists are lists whose number of elements is a power of two.
--   This data structure is efficient for some computations like:
--   
--   <ul>
--   <li>Splitting a list in half.</li>
--   <li>Appending two lists of the same length.</li>
--   <li>Extracting an element from the list.</li>
--   </ul>
--   
--   All the functions exported are total except for
--   <a>fromListWithDefault</a>. It is impossible for the user of this
--   library to create a binary list whose length is <i>not</i> a power of
--   two.
--   
--   Since many names in this module clash with the names of some
--   <a>Prelude</a> functions, you probably want to import this module this
--   way:
--   
--   <pre>
--   import Data.BinaryList (BinList,Exponent)
--   import qualified Data.BinaryList as BL
--   </pre>
--   
--   Remember that binary lists are an instance of the <a>Foldable</a> and
--   <a>Traversable</a> classes. If you are missing a function here, look
--   for functions using those instances.
--   
--   Note that some functions like <a>replicate</a>, <a>generate</a>, or
--   <a>take</a>, don't use the length of the list as argument, but the
--   exponent of its length expressed as a power of two. Throughout this
--   document, this is referred as the <i>length exponent</i>. For example,
--   if the list has length 16, its length exponent is 4 since 2^4 = 16.
--   Therefore <tt>replicate 4 0</tt> will create a list with 16 zeroes.
--   Keep this in mind when using this library. Note as well that this
--   implies that there is no need to check that the length argument is or
--   is not a power of two.
module Data.BinaryList

-- | A binary list is a list containing a power of two elements. Note that
--   a binary list is never empty because it has at least <tt>2^0 = 1</tt>
--   element.
data BinList a

-- | An exponent.
type Exponent = Word8

-- | <i>O(1)</i>. Build a list with a single element.
singleton :: a -> BinList a

-- | <i>O(1)</i>. Append two binary lists. This is only possible if both
--   lists have the same length. If this condition is not hold,
--   <a>Nothing</a> is returned.
append :: BinList a -> BinList a -> Maybe (BinList a)

-- | <i>O(log n)</i>. Calling <tt>replicate n x</tt> builds a binary list
--   with <tt>2^n</tt> occurences of <tt>x</tt>.
replicate :: Exponent -> a -> BinList a

-- | Calling <tt>replicateA n f</tt> builds a binary list collecting the
--   results of executing <tt>2^n</tt> times the applicative action
--   <tt>f</tt>.
replicateA :: Applicative f => Exponent -> f a -> f (BinList a)

-- | The same as <a>replicateA</a>, but the actions are executed in
--   reversed order.
replicateAR :: Applicative f => Exponent -> f a -> f (BinList a)

-- | <i>O(n)</i>. Build a binary list with the given length exponent (see
--   <a>lengthExponent</a>) by applying a function to each index.
generate :: Exponent -> (Int -> a) -> BinList a

-- | Like <a>generate</a>, but the generator function returns a value in a
--   <a>Monad</a>. Therefore, the result is as well contained in a
--   <a>Monad</a>.
generateM :: (Applicative m, Monad m) => Exponent -> (Int -> m a) -> m (BinList a)

-- | <i>O(1)</i>. Given a binary list <tt>l</tt> with length <tt>2^k</tt>:
--   
--   <pre>
--   lengthExponent l = k
--   </pre>
lengthExponent :: BinList a -> Exponent

-- | <i>O(log n)</i>. Lookup an element in the list by its index (starting
--   from 0). If the index is out of range, <a>Nothing</a> is returned.
lookup :: BinList a -> Int -> Maybe a

-- | <i>O(log n)</i>. Get the first element of a binary list.
head :: BinList a -> a

-- | <i>O(log n)</i>. Get the last element of a binary list.
last :: BinList a -> a

-- | <i>O(1)</i>. Split a binary list into two sublists of half the length,
--   unless the list only contains one element. In that case, it just
--   returns that element.
split :: BinList a -> Either a (BinList a, BinList a)

-- | <i>O(log n)</i>. Calling <tt>take n xs</tt> returns the first <tt>min
--   (2^n) (length xs)</tt> elements of <tt>xs</tt>.
take :: Exponent -> BinList a -> BinList a

-- | <i>O(log n)</i>. Calling <tt>takeEnd n xs</tt> returns the last
--   <tt>min (2^n) (length xs)</tt> elements of <tt>xs</tt>.
takeEnd :: Exponent -> BinList a -> BinList a

-- | <i>O(log n)</i>. Replace a single element in the list. If the index is
--   out of range, returns the original list.
replace :: Int -> a -> BinList a -> BinList a

-- | <i>O(n)</i>. Reverse a binary list.
reverse :: BinList a -> BinList a

-- | <i>O(n)</i>. Transform a list of pairs into a flat list. The resulting
--   list will have twice more elements than the original.
joinPairs :: BinList (a, a) -> BinList a

-- | <i>O(n)</i>. Opposite transformation of <a>joinPairs</a>. It halves
--   the number of elements of the input. As a result, when applied to a
--   binary list with a single element, it returns <a>Nothing</a>.
disjoinPairs :: BinList a -> Maybe (BinList (a, a))

-- | <i>O(n)</i>. Zip two binary lists in pairs.
zip :: BinList a -> BinList b -> BinList (a, b)

-- | <i>O(n)</i>. Unzip a binary list of pairs.
unzip :: BinList (a, b) -> (BinList a, BinList b)

-- | <i>O(n)</i>. Zip two binary lists using an operator.
zipWith :: (a -> b -> c) -> BinList a -> BinList b -> BinList c

-- | <i>O(n)</i>. Build a binary list from a linked list. If the input list
--   has length different from a power of two, it returns <a>Nothing</a>.
fromList :: [a] -> Maybe (BinList a)

-- | <i>O(n)</i>. Build a binary list from a linked list. If the input list
--   has length different from a power of two, fill to the next power of
--   two with a default element.
--   
--   <i>Warning: this function crashes if the input list length is larger
--   than any</i> <i>power of two in the type <a>Int</a>. However, this is
--   very unlikely.</i>
fromListWithDefault :: a -> [a] -> BinList a

-- | <i>O(n)</i>. Build a binary list from a linked list. It returns a
--   binary list with length <tt>2 ^ n</tt> (where <tt>n</tt> is the
--   supplied <a>Int</a> argument), and the list of elements of the
--   original list that were not used. If the input list is shorter than
--   <tt>2 ^ n</tt>, a default element will be used to complete the binary
--   list. This method for building binary lists is faster than both
--   <a>fromList</a> and <a>fromListWithDefault</a>.
fromListSplit :: a -> Exponent -> [a] -> (BinList a, [a])

-- | <i>O(n)</i>. Create a list from the elements of a binary list matching
--   a given condition.
toListFilter :: (a -> Bool) -> BinList a -> [a]

-- | <i>O(n)</i>. Create a list extracting a sublist of elements from a
--   binary list.
toListSegment :: Int -> Int -> BinList a -> [a]

-- | Apply an applicative action to every element in a segment of a binary
--   list, from left to right.
traverseSegment :: Applicative f => (a -> f ()) -> Int -> Int -> BinList a -> f ()
instance GHC.Show.Show a => GHC.Show.Show (Data.BinaryList.Internal.BinList a)
instance GHC.Base.Functor Data.BinaryList.Internal.BinList
instance Data.Foldable.Foldable Data.BinaryList.Internal.BinList
instance Data.Traversable.Traversable Data.BinaryList.Internal.BinList


-- | Serialization methods for binary lists.
module Data.BinaryList.Serialize

-- | Encode a binary list using the <a>Binary</a> instance of its elements.
encode :: Binary a => BinList a -> ByteString

-- | Decode a binary list using the <a>Binary</a> instance of its elements.
--   It returns a <a>String</a> in case of decoding failure.
decode :: Binary a => ByteString -> Either String (BinList a)

-- | Direction of encoding. If the direction is <a>FromLeft</a>, the binary
--   list will be encoded from left to right. If the direction is
--   <a>FromRight</a>, the binary list will be encoded in the opposite way.
--   Choose a direction according to the part of the list you want to have
--   access earlier. If you foresee reading only a part of the list, either
--   at its beginning or end, an appropiate choice of direction will allow
--   you to avoid decoding the full list.
data Direction
FromLeft :: Direction
FromRight :: Direction

-- | A binary list encoded, ready to be written in a file or be sent over a
--   network. It can be directly translated to a <a>ByteString</a> using
--   <a>encodedToByteString</a>, or restored using
--   <a>encodedFromByteString</a>.
data EncodedBinList
EncodedBinList :: Direction -> Exponent -> ByteString -> EncodedBinList

-- | Direction of encoding.
[encDirection] :: EncodedBinList -> Direction

-- | Length exponent (see <a>lengthExponent</a>) of the binary list.
[encLength] :: EncodedBinList -> Exponent

-- | Encoded data.
[encData] :: EncodedBinList -> ByteString

-- | Encode a binary list, using a custom serialization for its elements
--   and an user-supplied direction.
encodeBinList :: (a -> Put) -> Direction -> BinList a -> EncodedBinList

-- | A binary list decoded, from where you can extract a binary list. If
--   the decoding process fails in some point, you still will be able to
--   retrieve the binary list of elements that were decoded successfully
--   before the error.
data DecodedBinList a
DecodedBinList :: Direction -> Exponent -> Decoded a -> DecodedBinList a

-- | Direction of encoding.
[decDirection] :: DecodedBinList a -> Direction

-- | Length exponent (see <a>lengthExponent</a>) of the binary list.
[decLength] :: DecodedBinList a -> Exponent

-- | Decoded data.
[decData] :: DecodedBinList a -> Decoded a

-- | The result of decoding a binary list, which produces a list of binary
--   lists of increasing size, ending in either a decoding error or a final
--   binary list. When this is the result of <a>decodeBinList</a>, it
--   contains sublists of order 1, 2, 4, 8, ... up to the order of the
--   total list (unless an error has been encountered first). These
--   sublists are either a section starting at the left, or a section
--   starting at the right, depending on the <a>Direction</a> of encoding.
data Decoded a

-- | Partial binary list, and rest of decoded input.
PartialResult :: (BinList a) -> (Decoded a) -> Decoded a

-- | Full binary list and remaining input.
FinalResult :: (BinList a) -> ByteString -> Decoded a

-- | A decoding error, with an error message and the remaining input.
DecodingError :: String -> ByteString -> Decoded a

-- | Get the final result of a decoding process, unless it returned an
--   error, in which case this error is returned as a <a>String</a>.
fromDecoded :: Decoded a -> Either String (BinList a)

-- | Break a list down to sublists of order 1, 2, 4, 8, ..., 2^k. The
--   result is stored in a <a>Decoded</a> value. Obviously, the output will
--   not have a decoding error.
toDecoded :: BinList a -> Decoded a

-- | Extract the list of binary lists from a <a>Decoded</a> value.
decodedToList :: Decoded a -> [BinList a]

-- | Decode an encoded binary list. The result is given as a
--   <a>DecodedBinList</a> value, which can then be queried to get partial
--   results.
decodeBinList :: Get a -> EncodedBinList -> DecodedBinList a

-- | Translate an encoded binary list to a bytestring.
encodedToByteString :: EncodedBinList -> ByteString

-- | Translate a bytestring to an encoded binary list, in case this is
--   possible. Otherwise, it returns a string with a human-readable error.
encodedFromByteString :: ByteString -> Either String EncodedBinList
instance GHC.Show.Show a => GHC.Show.Show (Data.BinaryList.Serialize.Decoded a)
instance GHC.Show.Show Data.BinaryList.Serialize.Direction
instance GHC.Classes.Eq Data.BinaryList.Serialize.Direction
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.BinaryList.Serialize.Decoded a)
instance GHC.Base.Functor Data.BinaryList.Serialize.Decoded
