Copyright | (c) Ross Paterson, Ralf Hinze 2006 |
---|---|
License | BSD-style |
Maintainer | ross@soi.city.ac.uk |
Stability | experimental |
Portability | non-portable (MPTCs and functional dependencies) |
Safe Haskell | Safe-Inferred |
Language | Haskell98 |
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://staff.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
A representation of a sequence of values of type a
, allowing
access to the ends in constant time, and append and split in time
logarithmic in the size of the smaller piece.
The collection is also parameterized by a measure type v
, which
is used to specify a position in the sequence for the split
operation.
The types of the operations enforce the constraint
,
which also implies that the type Measured
v av
is determined by a
.
A variety of abstract data types can be implemented by using different element types and measurements.
Measured v a => Measured v (FingerTree v a) | O(1). The cached measure of a tree. |
Foldable (FingerTree v) | |
Eq a => Eq (FingerTree v a) | |
Ord a => Ord (FingerTree v a) | |
Show a => Show (FingerTree v a) | |
Measured v a => Monoid (FingerTree v a) |
class Monoid v => Measured v a | a -> v where Source
Things that can be measured.
Measured v a => Measured v (FingerTree v a) | O(1). The cached measure of a tree. |
Construction
empty :: Measured v a => FingerTree v a Source
O(1). The empty sequence.
singleton :: Measured v a => a -> FingerTree v a Source
O(1). A singleton sequence.
(<|) :: Measured v a => a -> FingerTree v a -> FingerTree v a infixr 5 Source
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 infixl 5 Source
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 infixr 5 Source
O(log(min(n1,n2))). Concatenate two sequences.
fromList :: Measured v a => [a] -> FingerTree v a Source
O(n). Create a sequence from a finite list of elements.
Deconstruction
null :: Measured v a => FingerTree v a -> Bool Source
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) a Source
O(1). Analyse the left end of a sequence.
viewr :: Measured v a => FingerTree v a -> ViewR (FingerTree v) a Source
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 a Source
dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a Source
Transformation
reverse :: Measured v a => FingerTree v a -> FingerTree v a Source
O(n). The reverse of a sequence.
fmap' :: (Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 Source
Like fmap
, but with a more constrained type.
fmapWithPos :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 Source
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 b Source
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.
Example
Particular abstract data types may be implemented by defining
element types with suitable Measured
instances.
(from section 4.5 of the paper)
Simple sequences can be implemented using a Sum
monoid as a measure:
newtype Elem a = Elem { getElem :: a } instance Measured (Sum Int) (Elem a) where measure (Elem _) = Sum 1 newtype Seq a = Seq (FingerTree (Sum Int) (Elem a))
Then the measure of a subsequence is simply its length. This representation supports log-time extraction of subsequences:
take :: Int -> Seq a -> Seq a take k (Seq xs) = Seq (takeUntil (> Sum k) xs) drop :: Int -> Seq a -> Seq a drop k (Seq xs) = Seq (dropUntil (> Sum k) xs)
The module Data.Sequence
is an optimized instantiation of this type.
For further examples, see Data.IntervalMap.FingerTree and Data.PriorityQueue.FingerTree.