fingertree-0.0.1.0: Generic finger-tree structure, with example instances

Portabilitynon-portable (MPTCs and functional dependencies)
Stabilityexperimental
Maintainerross@soi.city.ac.uk

Data.FingerTree

Contents

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 Source

Finger trees with element type a, annotated with measures of type v. The operations enforce the constraint Measured v a.

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) 
Measured v a => Monoid (FingerTree v a) 

class Monoid v => Measured v a | a -> v whereSource

Things that can be measured.

Methods

measure :: a -> vSource

Instances

Measured v a => Measured v (Digit a) 
Measured v a => Measured v (FingerTree v a) 
Monoid v => Measured v (Node v a) 
Ord v => Measured (IntInterval v) (Node v a) 
Ord k => Measured (Prio k v) (Entry k v) 

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

EmptyL

empty sequence

a :< (s a)

leftmost element and the rest of the sequence

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

EmptyR

empty sequence

(s a) :> a

the sequence minus the rightmost element, and the rightmost element

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.

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.