|
Data.FingerTree | Portability | non-portable (MPTCs and functional dependencies) | Stability | experimental | Maintainer | ross@soi.city.ac.uk |
|
|
|
|
|
Description |
A general sequence representation with arbitrary annotations, for
use as a base for implementations of various collection types, as
described in section 4 of
For a directly usable sequence type, see Data.Sequence, which is
a specialization of this structure.
An amortized running time is given for each operation, with n
referring to the length of the sequence. These bounds hold even in
a persistent (shared) setting.
Note: Many of these operations have the same names as similar
operations on lists in the Prelude. The ambiguity may be resolved
using either qualification or the hiding clause.
|
|
Synopsis |
|
|
|
Documentation |
|
data FingerTree v a |
Finger trees with element type a, annotated with measures of type v.
The operations enforce the constraint Measured v a.
| Instances | |
|
|
class Monoid v => Measured v a | a -> v where |
Things that can be measured.
| | Methods | | | Instances | |
|
|
Construction
|
|
empty :: Measured v a => FingerTree v a |
O(1). The empty sequence.
|
|
singleton :: Measured v a => a -> FingerTree v a |
O(1). A singleton sequence.
|
|
(<|) :: Measured v a => a -> FingerTree v a -> FingerTree v a |
O(1). Add an element to the left end of a sequence.
Mnemonic: a triangle with the single element at the pointy end.
|
|
(|>) :: Measured v a => FingerTree v a -> a -> FingerTree v a |
O(1). Add an element to the right end of a sequence.
Mnemonic: a triangle with the single element at the pointy end.
|
|
(><) :: Measured v a => FingerTree v a -> FingerTree v a -> FingerTree v a |
O(log(min(n1,n2))). Concatenate two sequences.
|
|
fromList :: Measured v a => [a] -> FingerTree v a |
O(n). Create a sequence from a finite list of elements.
|
|
Deconstruction
|
|
null :: Measured v a => FingerTree v a -> Bool |
O(1). Is this the empty sequence?
|
|
data ViewL s a |
View of the left end of a sequence.
| Constructors | EmptyL | empty sequence
| a :< (s a) | leftmost element and the rest of the sequence
|
| Instances | |
|
|
data ViewR s a |
View of the right end of a sequence.
| Constructors | EmptyR | empty sequence
| (s a) :> a | the sequence minus the rightmost element,
and the rightmost element
|
| Instances | |
|
|
viewl :: Measured v a => FingerTree v a -> ViewL (FingerTree v) a |
O(1). Analyse the left end of a sequence.
|
|
viewr :: Measured v a => FingerTree v a -> ViewR (FingerTree v) a |
O(1). Analyse the right end of a sequence.
|
|
split :: Measured v a => (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a) |
O(log(min(i,n-i))). Split a sequence at a point where the predicate
on the accumulated measure changes from False to True.
|
|
takeUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a |
|
dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a |
|
Transformation
|
|
reverse :: Measured v a => FingerTree v a -> FingerTree v a |
O(n). The reverse of a sequence.
|
|
fmap' :: (Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 |
Like fmap, but with a more constrained type.
|
|
traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) |
Like traverse, but with a more constrained type.
|
|
Produced by Haddock version 2.3.0 |