nested-sequence-0.2: List-like data structures with O(log(n)) random access

Data.Nested.Seq.Ternary.Lazy

Description

Lazy ternary random-access lists.

This module is intended to be imported qualified.

Synopsis

# Documentation

data Seq a Source #

The lazy sequence type.

The underlying (nested) data structure corresponds to the binary representation of the length of the list. It looks like this:

data Seq a
= Nil
| Zero     (Seq (a,a,a))
| One    a (Seq (a,a,a))
| Two  a a (Seq (a,a,a))

Furthermore we maintain the invariant that Zero Nil never appears.

Instances

 # Methodsfmap :: (a -> b) -> Seq a -> Seq b #(<\$) :: a -> Seq b -> Seq a # # Methodsfold :: Monoid m => Seq m -> m #foldMap :: Monoid m => (a -> m) -> Seq a -> m #foldr :: (a -> b -> b) -> b -> Seq a -> b #foldr' :: (a -> b -> b) -> b -> Seq a -> b #foldl :: (b -> a -> b) -> b -> Seq a -> b #foldl' :: (b -> a -> b) -> b -> Seq a -> b #foldr1 :: (a -> a -> a) -> Seq a -> a #foldl1 :: (a -> a -> a) -> Seq a -> a #toList :: Seq a -> [a] #null :: Seq a -> Bool #length :: Seq a -> Int #elem :: Eq a => a -> Seq a -> Bool #maximum :: Ord a => Seq a -> a #minimum :: Ord a => Seq a -> a #sum :: Num a => Seq a -> a #product :: Num a => Seq a -> a # Eq a => Eq (Seq a) # Methods(==) :: Seq a -> Seq a -> Bool #(/=) :: Seq a -> Seq a -> Bool # Ord a => Ord (Seq a) # Methodscompare :: Seq a -> Seq a -> Ordering #(<) :: Seq a -> Seq a -> Bool #(<=) :: Seq a -> Seq a -> Bool #(>) :: Seq a -> Seq a -> Bool #(>=) :: Seq a -> Seq a -> Bool #max :: Seq a -> Seq a -> Seq a #min :: Seq a -> Seq a -> Seq a # Show a => Show (Seq a) # MethodsshowsPrec :: Int -> Seq a -> ShowS #show :: Seq a -> String #showList :: [Seq a] -> ShowS # Monoid (Seq a) # Methodsmempty :: Seq a #mappend :: Seq a -> Seq a -> Seq a #mconcat :: [Seq a] -> Seq a #

# Accessing the left end of the sequence

cons :: a -> Seq a -> Seq a Source #

Prepending an element. Worst case O(log(n)), but amortized O(1).

unCons :: Seq a -> Maybe (a, Seq a) Source #

Worst case O(log(n)), amortized O(1)

# Basic queries

null :: Seq a -> Bool Source #

Checks whether the sequence is empty. This is O(1).

length :: Seq a -> Int Source #

The length of a sequence. O(log(n)).

# Basic construction

The empty sequence.

toList :: Seq a -> [a] Source #

Conversion to a list. O(n).

fromList :: [a] -> Seq a Source #

Conversion from a list. O(n).

# Short sequences

singleton :: a -> Seq a Source #

pair :: a -> a -> Seq a Source #

triple :: a -> a -> a -> Seq a Source #

quad :: a -> a -> a -> a -> Seq a Source #

head :: Seq a -> a Source #

First element of the sequence. Worst case O(log(n)), amortized O(1).

tail :: Seq a -> Seq a Source #

Tail of the sequence. Worst case O(log(n)), amortized O(1).

last :: Seq a -> a Source #

Last element of the sequence. O(log(n)).

mbHead :: Seq a -> Maybe a Source #

First element of the sequence. Worst case O(log(n)), amortized O(1).

mbTail :: Seq a -> Maybe (Seq a) Source #

Tail of the sequence. Worst case O(log(n)), amortized O(1).

tails :: Seq a -> [Seq a] Source #

All tails of the sequence (starting with the sequence itself)

mbLast :: Seq a -> Maybe a Source #

Last element of the sequence. O(log(n))

# Indexing

lookup :: Int -> Seq a -> a Source #

Lookup the k-th element of a sequence. This is worst case O(log(n)) and amortized O(log(k)), and quite efficient.

mbLookup :: Int -> Seq a -> Maybe a Source #

update :: (a -> a) -> Int -> Seq a -> Seq a Source #

Update the k-th element of a sequence.

replace :: Int -> a -> Seq a -> Seq a Source #

Replace the k-th element. replace n x == update (const x) n

drop :: Int -> Seq a -> Seq a Source #

Drop is efficient: drop k is amortized O(log(k)), worst case maybe O(log(n)^2) ?

# Slow operations

append :: Seq a -> Seq a -> Seq a Source #

O(n) (for large n at least), where n is the length of the first sequence.

take :: Int -> Seq a -> Seq a Source #

Take is slow: O(n)

init :: Seq a -> Seq a Source #

The sequence without the last element. Warning, this is slow, O(n)

mbInit :: Seq a -> Maybe (Seq a) Source #

The sequence without the last element. Warning, this is slow, O(n)

snoc :: Seq a -> a -> Seq a Source #

Warning, this is slow: O(n) (with bad constant factor).

unSnoc :: Seq a -> Maybe (Seq a, a) Source #

Stripping the last element from a sequence is a slow operation, O(n). If you only need extracting the last element, use mbLast instead, which is fast.

# Debugging

toListNaive :: Seq a -> [a] Source #

Naive implementation of toList

We maintain the invariant that (Z Nil) never appears. This function checks whether this is satisfied. Used only for testing.

showInternal :: Show a => Seq a -> String Source #

Show the internal structure of the sequence. The constructor names Z and O come from "zero" and "one", respectively.

graphviz :: Show a => Seq a -> String Source #

Generates a graphviz DOT file, showing the internal structure of a sequence