binary-list-0.3.0.0: Lists of size length a power of two.

Safe HaskellNone

Data.BinaryList

Contents

Description

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

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.

Synopsis

Type

data BinList a Source

A binary list is a list containing a power of two elements. Note that a binary list is never empty.

Instances

Construction

singleton :: a -> BinList aSource

O(1). Build a list with a single element.

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.

replicateA :: Applicative f => Int -> f a -> f (BinList a)Source

Calling replicateA n f builds a binary list collecting the results of executing 2^n times the applicative action f.

replicateAR :: Applicative f => Int -> f a -> f (BinList a)Source

The same as replicateA, but the actions are executed in reversed order.

Queries

lengthIndex :: BinList a -> IntSource

O(1). Given a binary list l with length 2^k: 

 lengthIndex l = k

length :: BinList a -> IntSource

O(1). Number of elements in the list.

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.

head :: BinList a -> aSource

O(log n). Get the first element of a binary list.

last :: BinList a -> aSource

O(log n). Get the last element of a binary list.

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.

fold :: Foldable t => forall m. Monoid m => t m -> m

Combine the elements of a structure using a monoid.

Transformation

reverse :: BinList a -> BinList aSource

O(n). Reverse a binary list.

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

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.

Zipping and Unzipping

zip :: BinList a -> BinList b -> BinList (a, b)Source

O(n). Zip two binary lists in pairs.

unzip :: BinList (a, b) -> (BinList a, BinList b)Source

O(n). Unzip a binary list of pairs.

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.