fingertree-0.0: Generic finger-tree structureSource codeContentsIndex
Data.FingerTree
Portabilitynon-portable (MPTCs and functional dependencies)
Stabilityexperimental
Maintainerross@soi.city.ac.uk
Contents
Construction
Deconstruction
Transformation
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
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
= EmptyL
| a :< (s a)
data ViewR s a
= EmptyR
| (s a) :> 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
traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2)
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.
show/hide Instances
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)
class Monoid v => Measured v a | a -> v whereSource
Things that can be measured.
Methods
measure :: a -> vSource
show/hide Instances
Measured v a => Measured v (Digit a)
Measured v a => Measured v (FingerTree v a)
Monoid v => Measured v (Node 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?
data ViewL s a Source
View of the left end of a sequence.
Constructors
EmptyLempty sequence
a :< (s a)leftmost element and the rest of the sequence
show/hide Instances
Functor s => Functor (ViewL s)
(Eq a, Eq (s a)) => Eq (ViewL s a)
(Ord a, Ord (s a)) => Ord (ViewL s a)
(Read a, Read (s a)) => Read (ViewL s a)
(Show a, Show (s a)) => Show (ViewL s a)
data ViewR s a Source
View of the right end of a sequence.
Constructors
EmptyRempty sequence
(s a) :> athe sequence minus the rightmost element, and the rightmost element
show/hide Instances
Functor s => Functor (ViewR s)
(Eq a, Eq (s a)) => Eq (ViewR s a)
(Ord a, Ord (s a)) => Ord (ViewR s a)
(Read a, Read (s a)) => Read (ViewR s a)
(Show a, Show (s a)) => Show (ViewR s a)
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
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 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.
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.
Produced by Haddock version 2.4.2