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

Language | Haskell98 |

Simple but efficient lazy list-like sequence type based on a nested data type and polymorphic recursion. Also called "binary random-access list"

It is like a list, but instead of `O(1)`

cons/uncons and `O(k)`

lookup,
we have amortized `O(1)`

cons/uncons and `O(log(k))`

lookup (both are `O(log(n))`

in the worst case).
This is somewhat similar to a finger tree (which is also represented by a nested data type), but
much simpler. Memory usage is basically the same as with lists: on average
3 words per element, plus the data itself.

However, modifying the right end of the sequence is still slow: `O(n)`

. This affects the functions
`snoc`

, `unSnoc`

, `append`

, `take`

, `init`

. Somewhat surprisingly, *extracting* the last element is
still fast.

An example usage is a stack.

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 binary representation of the length of the list. It looks like this:

data Seq a = Nil | Even (Seq (a,a)) | Odd a (Seq (a,a))

Furthermore we maintain the invariant that `Even Nil`

never appears.

If the `Odd`

constructor was missing, this would be a *full binary tree*. Note that the
nested data type representation has two advantages compared to a naive binary tree type
(by which we mean the usual `data Tree a = Node a a | Leaf a`

construction):
First, the type system guarantees the fullness; second, it has smaller memory footprint, since
in the naive case, the `Leaf`

constructors introduce two extra words (a tag word and a pointer).

With the `Odd`

constructor thrown in, this is a sequence of larger and larger full
binary trees. Looking at the binary representation of the length of the list, we will have full
binary trees corresponding to the positions of `1`

digits.

For example, here are how sequences of lengths 4, 5, 6 and 7 are represented:

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