-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Lists of size length a power of two. -- -- Some algorithmic problems work only when the input list has length a -- power of two. This library provides with a data structure optimized -- for this. @package binary-list @version 0.3.0.0 -- | Binary lists are lists whose number of elements is a power of two. -- This data structure is efficient for some computations like: -- -- -- -- All the functions exported are total except for -- fromListWithDefault. It is impossible for the user of this -- library to create a binary list whose length is not a power of -- two. -- -- Since many names in this module crashes with the names of some -- Prelude functions, you probably want to import this module this -- way: -- -- 
--   import Data.BinaryList (BinList)
--   import qualified Data.BinaryList as BL
--
-- -- Remember that binary lists are an instance of the Foldable and -- Traversable classes. If you are missing a function here, look -- for functions using those instances. module Data.BinaryList -- | A binary list is a list containing a power of two elements. Note that -- a binary list is never empty. data BinList a -- | O(1). Build a list with a single element. singleton :: a -> BinList a -- | O(1). Append two binary lists. This is only possible if both -- lists have the same length. If this condition is not hold, -- Nothing is returned. append :: BinList a -> BinList a -> Maybe (BinList a) -- | O(log n). Calling replicate n x builds a binary list -- with 2^n occurences of x. replicate :: Int -> a -> BinList a -- | Calling replicateA n f builds a binary list collecting the -- results of executing 2^n times the applicative action -- f. replicateA :: Applicative f => Int -> f a -> f (BinList a) -- | The same as replicateA, but the actions are executed in -- reversed order. replicateAR :: Applicative f => Int -> f a -> f (BinList a) -- | O(1). Given a binary list l with length 2^k: -- -- 
--   lengthIndex l = k
--
lengthIndex :: BinList a -> Int -- | O(1). Number of elements in the list. length :: BinList a -> Int -- | O(log n). Lookup an element in the list by its index (starting -- from 0). If the index is out of range, Nothing is returned. lookup :: BinList a -> Int -> Maybe a -- | O(log n). Get the first element of a binary list. head :: BinList a -> a -- | O(log n). Get the last element of a binary list. last :: BinList a -> a -- | O(1). 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) -- | Combine the elements of a structure using a monoid. fold :: Foldable t => forall m. Monoid m => t m -> m -- | O(n). Reverse a binary list. reverse :: BinList a -> BinList a -- | O(n). 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 -- | O(n). Opposite transformation of joinPairs. It halves -- the number of elements of the input. As a result, when applied to a -- binary list with a single element, it returns Nothing. disjoinPairs :: BinList a -> Maybe (BinList (a, a)) -- | O(n). Zip two binary lists in pairs. zip :: BinList a -> BinList b -> BinList (a, b) -- | O(n). Unzip a binary list of pairs. unzip :: BinList (a, b) -> (BinList a, BinList b) -- | O(n). Zip two binary lists using an operator. zipWith :: (a -> b -> c) -> BinList a -> BinList b -> BinList c -- | O(n). Build a binary list from a linked list. If the input list -- has length different from a power of two, it returns Nothing. fromList :: [a] -> Maybe (BinList a) -- | O(n). 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. -- -- Warning: this function crashes if the input list length is larger -- than any power of two in the type 'Int'. However, this is very -- unlikely. fromListWithDefault :: a -> [a] -> BinList a instance Traversable BinList instance Foldable BinList instance Functor BinList instance Show a => Show (BinList a) -- | Serialization methods for binary lists. module Data.BinaryList.Serialize -- | Encode a binary list using the Binary instance of its elements. encode :: Binary a => BinList a -> ByteString -- | Decode a binary list using the Binary instance of its elements. -- It returns a String in case of decoding failure. decode :: Binary a => ByteString -> Either String (BinList a) -- | Direction of encoding. If the direction is FromLeft, the binary -- list will be encoded from left to right. If the direction is -- FromRight, 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 ByteString using -- encodedToByteString, or restored using -- encodedFromByteString. data EncodedBinList EncodedBinList :: Direction -> Int -> ByteString -> EncodedBinList -- | Direction of encoding. encDirection :: EncodedBinList -> Direction -- | Length index (see lengthIndex) of the binary list. encLength :: EncodedBinList -> Int -- | 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 -> Int -> Decoded a -> DecodedBinList a -- | Direction of encoding. decDirection :: DecodedBinList a -> Direction -- | Length index (see lengthIndex) of the binary list. decLength :: DecodedBinList a -> Int -- | 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 decodeBinList, it -- contains sublists of order 1, 2, 4, 8, ... up to the order of the -- total list (unless an error has been encountered first). This sublists -- are either a section starting at the left, or a section starting at -- the right, depending on the Direction 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 String. fromDecoded :: Decoded a -> Either String (BinList a) -- | Decode an encoded binary list. The result is given as a -- DecodedBinList 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 Eq Direction