Safe Haskell | None |
---|
Binary lists are lists whose number of elements is a power of two. This data structure is efficient for some computations like:
- Splitting a list in half. * Appending two lists of the same length. * Extracting an element from the list.
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
- data BinList a
- singleton :: a -> BinList a
- append :: BinList a -> BinList a -> Maybe (BinList a)
- replicate :: Int -> a -> BinList a
- lengthIndex :: BinList a -> Int
- length :: BinList a -> Int
- lookup :: BinList a -> Int -> Maybe a
- head :: BinList a -> a
- last :: BinList a -> a
- minimum :: Ord a => BinList a -> a
- maximum :: Ord a => BinList a -> a
- split :: BinList a -> Either a (BinList a, BinList a)
- fold :: (a -> a -> a) -> BinList a -> a
- reverse :: BinList a -> BinList a
- joinPairs :: BinList (a, a) -> BinList a
- disjoinPairs :: BinList a -> Maybe (BinList (a, a))
- zip :: BinList a -> BinList b -> BinList (a, b)
- unzip :: BinList (a, b) -> (BinList a, BinList b)
- zipWith :: (a -> b -> c) -> BinList a -> BinList b -> BinList c
- fromList :: [a] -> Maybe (BinList a)
- fromListWithDefault :: a -> [a] -> BinList a
- toList :: BinList a -> [a]
Type
A binary list is a list containing a power of two elements. Note that a binary list is never empty.
Construction
append :: BinList a -> BinList a -> Maybe (BinList a)Source
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.
replicate :: Int -> a -> BinList aSource
O(log n). Calling replicate n x
builds a binary list with
2^n
occurences of x
.
Queries
lengthIndex :: BinList a -> IntSource
O(1). Given a binary list l
with length 2^k
:
lengthIndex l = k
lookup :: BinList a -> Int -> Maybe aSource
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.
Decontruction
split :: BinList a -> Either a (BinList a, BinList a)Source
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.
Transformation
Tuples
joinPairs :: BinList (a, a) -> BinList aSource
O(n). Transform a list of pairs into a flat list. The resulting list will have twice more elements than the original.
disjoinPairs :: BinList a -> Maybe (BinList (a, a))Source
Zipping and Unzipping
zipWith :: (a -> b -> c) -> BinList a -> BinList b -> BinList cSource
O(n). Zip two binary lists using an operator.
Lists
fromList :: [a] -> Maybe (BinList a)Source
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
.
fromListWithDefault :: a -> [a] -> BinList aSource
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.