Portability | non-portable (MPTCs and functional dependencies) |
---|---|
Stability | experimental |
Maintainer | ross@soi.city.ac.uk |
A general sequence representation with arbitrary annotations, for use as a base for implementations of various collection types, as described in section 4 of
- Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", Journal of Functional Programming 16:2 (2006) pp 197-217. http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
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.
- data FingerTree v a
- class Monoid v => Measured v a | a -> v where
- measure :: a -> v
- empty :: Measured v a => FingerTree v a
- singleton :: Measured v a => a -> FingerTree v a
- (<|) :: Measured v a => a -> FingerTree v a -> FingerTree v a
- (|>) :: Measured v a => FingerTree v a -> a -> FingerTree v a
- (><) :: Measured v a => FingerTree v a -> FingerTree v a -> FingerTree v a
- fromList :: Measured v a => [a] -> FingerTree v a
- null :: Measured v a => FingerTree v a -> Bool
- data ViewL s a
- data ViewR s a
- viewl :: Measured v a => FingerTree v a -> ViewL (FingerTree v) a
- viewr :: Measured v a => FingerTree v a -> ViewR (FingerTree v) a
- split :: Measured v a => (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a)
- takeUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a
- dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a
- reverse :: Measured v a => FingerTree v a -> FingerTree v a
- fmap' :: (Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2
- fmapWithPos :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2
- unsafeFmap :: (a -> b) -> FingerTree v a -> FingerTree v b
- traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)
- traverseWithPos :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)
- unsafeTraverse :: Applicative f => (a -> f b) -> FingerTree v a -> f (FingerTree v b)
Documentation
data FingerTree v a Source
Finger trees with element type a
, annotated with measures of type v
.
The operations enforce the constraint
.
Measured
v a
Measured v a => Measured v (FingerTree v a) | |
Foldable (FingerTree v) | |
(Measured v a, Eq a) => Eq (FingerTree v a) | |
(Measured v a, Ord a) => Ord (FingerTree v a) | |
(Measured v a, Show a) => Show (FingerTree v a) | |
Measured v a => Monoid (FingerTree v a) |
Construction
empty :: Measured v a => FingerTree v aSource
O(1). The empty sequence.
singleton :: Measured v a => a -> FingerTree v aSource
O(1). A singleton sequence.
(<|) :: Measured v a => a -> FingerTree v a -> FingerTree v aSource
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 aSource
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 aSource
O(log(min(n1,n2))). Concatenate two sequences.
fromList :: Measured v a => [a] -> FingerTree v aSource
O(n). Create a sequence from a finite list of elements.
Deconstruction
null :: Measured v a => FingerTree v a -> BoolSource
O(1). Is this the empty sequence?
View of the left end of a sequence.
View of the right end of a sequence.
viewl :: Measured v a => FingerTree v a -> ViewL (FingerTree v) aSource
O(1). Analyse the left end of a sequence.
viewr :: Measured v a => FingerTree v a -> ViewR (FingerTree v) aSource
O(1). Analyse the right end of a sequence.
split :: Measured v a => (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a)Source
takeUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v aSource
dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v aSource
Transformation
reverse :: Measured v a => FingerTree v a -> FingerTree v aSource
O(n). The reverse of a sequence.
fmap' :: (Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2Source
Like fmap
, but with a more constrained type.
fmapWithPos :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2Source
Map all elements of the tree with a function that also takes the measure of the prefix of the tree to the left of the element.
unsafeFmap :: (a -> b) -> FingerTree v a -> FingerTree v bSource
Like fmap
, but safe only if the function preserves the measure.
traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)Source
Like traverse
, but with a more constrained type.
traverseWithPos :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)Source
Traverse the tree with a function that also takes the measure of the prefix of the tree to the left of the element.
unsafeTraverse :: Applicative f => (a -> f b) -> FingerTree v a -> f (FingerTree v b)Source
Like traverse
, but safe only if the function preserves the measure.