Copyright | (c) Ross Paterson, Ralf Hinze, Paweł Nowak 2014 |
---|---|
License | BSD-style |
Maintainer | pawel834@gmail.com |
Stability | provisional |
Portability | non-portable (TypeFamilies) |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
A version of Data.FingerTree from package fingertree modified to use associated types instead of functional dependencies and MPTCs.
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 a
- class Monoid (Measure a) => Measured a where
- empty :: Measured a => FingerTree a
- singleton :: Measured a => a -> FingerTree a
- (<|) :: Measured a => a -> FingerTree a -> FingerTree a
- (|>) :: Measured a => FingerTree a -> a -> FingerTree a
- (><) :: Measured a => FingerTree a -> FingerTree a -> FingerTree a
- fromList :: Measured a => [a] -> FingerTree a
- null :: Measured a => FingerTree a -> Bool
- data ViewL s a
- data ViewR s a
- viewl :: Measured a => FingerTree a -> ViewL FingerTree a
- viewr :: Measured a => FingerTree a -> ViewR FingerTree a
- split :: Measured a => (Measure a -> Bool) -> FingerTree a -> (FingerTree a, FingerTree a)
- takeUntil :: Measured a => (Measure a -> Bool) -> FingerTree a -> FingerTree a
- dropUntil :: Measured a => (Measure a -> Bool) -> FingerTree a -> FingerTree a
- reverse :: Measured a => FingerTree a -> FingerTree a
- fmap' :: (Measured a, Measured b) => (a -> b) -> FingerTree a -> FingerTree b
- fmapWithPos :: (Measured a, Measured b) => (Measure a -> a -> b) -> FingerTree a -> FingerTree b
- unsafeFmap :: (Measure a ~ Measure b) => (a -> b) -> FingerTree a -> FingerTree b
- traverse' :: (Measured a, Measured b, Applicative f) => (a -> f b) -> FingerTree a -> f (FingerTree b)
- traverseWithPos :: (Measured a, Measured b, Applicative f) => (Measure a -> a -> f b) -> FingerTree a -> f (FingerTree b)
- unsafeTraverse :: (Measure a ~ Measure b, Applicative f) => (a -> f b) -> FingerTree a -> f (FingerTree b)
Documentation
data FingerTree 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.
Foldable FingerTree | |
Eq a => Eq (FingerTree a) | |
Ord a => Ord (FingerTree a) | |
Show a => Show (FingerTree a) | |
Measured a => Monoid (FingerTree a) | |
Measured a => Measured (FingerTree a) | O(1). The cached measure of a tree. |
type Measure (FingerTree a) = Measure a |
class Monoid (Measure a) => Measured a where Source
Things that can be measured.
Measured a => Measured (FingerTree a) | O(1). The cached measure of a tree. |
Construction
empty :: Measured a => FingerTree a Source
O(1). The empty sequence.
singleton :: Measured a => a -> FingerTree a Source
O(1). A singleton sequence.
(<|) :: Measured a => a -> FingerTree a -> FingerTree 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 a => FingerTree a -> a -> FingerTree 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 a => FingerTree a -> FingerTree a -> FingerTree a infixr 5 Source
O(log(min(n1,n2))). Concatenate two sequences.
fromList :: Measured a => [a] -> FingerTree a Source
O(n). Create a sequence from a finite list of elements.
Deconstruction
null :: Measured a => FingerTree 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 a => FingerTree a -> ViewL FingerTree a Source
O(1). Analyse the left end of a sequence.
viewr :: Measured a => FingerTree a -> ViewR FingerTree a Source
O(1). Analyse the right end of a sequence.
split :: Measured a => (Measure a -> Bool) -> FingerTree a -> (FingerTree a, FingerTree a) Source
takeUntil :: Measured a => (Measure a -> Bool) -> FingerTree a -> FingerTree a Source
dropUntil :: Measured a => (Measure a -> Bool) -> FingerTree a -> FingerTree a Source
Transformation
reverse :: Measured a => FingerTree a -> FingerTree a Source
O(n). The reverse of a sequence.
fmap' :: (Measured a, Measured b) => (a -> b) -> FingerTree a -> FingerTree b Source
Like fmap
, but with a more constrained type.
fmapWithPos :: (Measured a, Measured b) => (Measure a -> a -> b) -> FingerTree a -> FingerTree b 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 :: (Measure a ~ Measure b) => (a -> b) -> FingerTree a -> FingerTree b Source
Like fmap
, but safe only if the function preserves the measure.
traverse' :: (Measured a, Measured b, Applicative f) => (a -> f b) -> FingerTree a -> f (FingerTree b) Source
Like traverse
, but with a more constrained type.
traverseWithPos :: (Measured a, Measured b, Applicative f) => (Measure a -> a -> f b) -> FingerTree a -> f (FingerTree b) 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 :: (Measure a ~ Measure b, Applicative f) => (a -> f b) -> FingerTree a -> f (FingerTree b) Source
Like traverse
, but safe only if the function preserves the measure.