Data.BinaryList

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

Type

data BinList a

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

Instances

Functor BinList

Eq a => Eq (BinList a)

Show a => Show (BinList a)

Construction

singleton :: a -> BinList a

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

append :: BinList a -> BinList a -> Maybe (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.

replicate :: Int -> a -> BinList a

O(log n). Calling replicate n x builds a binary list with 2^n occurences of x.

Queries

lengthIndex :: BinList a -> Int

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

 lengthIndex l = k

length :: BinList a -> Int

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

lookup :: BinList a -> Int -> Maybe a

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 -> a

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

last :: BinList a -> a

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

Decontruction

split :: BinList a -> Either a (BinList a, BinList 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.

fold :: (a -> a -> a) -> BinList a -> a

Fold a binary list using an operator.

Transformation

reverse :: BinList a -> BinList a

O(n). Reverse a binary list.

Tuples

joinPairs :: BinList (a, 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.

disjoinPairs :: BinList a -> Maybe (BinList (a, 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.

Zipping and Unzipping

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

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

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

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

zipWith :: (a -> b -> c) -> BinList a -> BinList b -> BinList c

O(n). Zip two binary lists using an operator.

Lists

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, it returns Nothing.

fromListWithDefault :: a -> [a] -> 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.

toList :: BinList a -> [a]

O(n). Build a linked list from a binary list.