-- 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.1.0.1 -- | 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
--
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 -- | 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) -- | Fold a binary list using an operator. fold :: (a -> a -> a) -> BinList a -> a -- | 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 -- | O(n). Build a linked list from a binary list. toList :: BinList a -> [a] instance Eq a => Eq (BinList a) instance Functor BinList instance Show a => Show (BinList a)