Safe Haskell | Safe |
---|---|

Language | Haskell98 |

Lazy quaternary random-access lists.

This module is intended to be imported qualified.

- data Seq a
- cons :: a -> Seq a -> Seq a
- unCons :: Seq a -> Maybe (a, Seq a)
- null :: Seq a -> Bool
- length :: Seq a -> Int
- empty :: Seq a
- toList :: Seq a -> [a]
- fromList :: [a] -> Seq a
- singleton :: a -> Seq a
- pair :: a -> a -> Seq a
- triple :: a -> a -> a -> Seq a
- quad :: a -> a -> a -> a -> Seq a
- head :: Seq a -> a
- tail :: Seq a -> Seq a
- last :: Seq a -> a
- mbHead :: Seq a -> Maybe a
- mbTail :: Seq a -> Maybe (Seq a)
- tails :: Seq a -> [Seq a]
- mbLast :: Seq a -> Maybe a
- lookup :: Int -> Seq a -> a
- mbLookup :: Int -> Seq a -> Maybe a
- update :: (a -> a) -> Int -> Seq a -> Seq a
- replace :: Int -> a -> Seq a -> Seq a
- drop :: Int -> Seq a -> Seq a
- append :: Seq a -> Seq a -> Seq a
- take :: Int -> Seq a -> Seq a
- init :: Seq a -> Seq a
- mbInit :: Seq a -> Maybe (Seq a)
- snoc :: Seq a -> a -> Seq a
- unSnoc :: Seq a -> Maybe (Seq a, a)
- toListNaive :: Seq a -> [a]
- checkInvariant :: Seq a -> Bool
- showInternal :: Show a => Seq a -> String
- graphviz :: Show a => Seq a -> String

# Documentation

The lazy sequence type.

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

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

Furthermore we maintain the invariant that `Zero Nil`

never appears.

# 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)`

.

# Basic queries

# Basic construction

# Short sequences

# Unsafe head and tail

# Safe head and tail

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)`

.

# 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.

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.

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

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

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`

checkInvariant :: Seq a -> Bool Source #

We maintain the invariant that `(Z Nil)`

never appears. This function
checks whether this is satisfied. Used only for testing.