Safe Haskell | Safe |
---|---|
Language | Haskell98 |
Strict ternary 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 strict sequence type. See Data.Nested.Seq.Ternary.Lazy for more information.
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.