Data.FingerTree

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.

Documentation

data FingerTree a

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 Measured v a, which also implies that the type v is determined by a.

A variety of abstract data types can be implemented by using different element types and measurements.

Instances

Foldable FingerTree

Eq a => Eq (FingerTree a)

Ord a => Ord (FingerTree a)

Show a => Show (FingerTree a)

Measured a => Monoid (FingerTree a)

empty and ><.

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

Things that can be measured.

Associated Types

type Measure a :: *

Methods

measure :: a -> Measure a

Instances

Measured a => Measured (FingerTree a)

O(1). The cached measure of a tree.

Construction

empty :: Measured a => FingerTree a

O(1). The empty sequence.

singleton :: Measured a => a -> FingerTree a

O(1). A singleton sequence.

(<|) :: Measured a => a -> FingerTree a -> FingerTree a infixr 5

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

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

O(log(min(n1,n2))). Concatenate two sequences.

fromList :: Measured a => [a] -> FingerTree a

O(n). Create a sequence from a finite list of elements.

Deconstruction

null :: Measured a => FingerTree a -> Bool

O(1). Is this the empty sequence?

data ViewL s a

View of the left end of a sequence.

Constructors

EmptyL

empty sequence

a :< (s a) infixr 5

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

View of the right end of a sequence.

Constructors

EmptyR

empty sequence

(s a) :> a infixl 5

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 a => FingerTree a -> ViewL FingerTree a

O(1). Analyse the left end of a sequence.

viewr :: Measured a => FingerTree a -> ViewR FingerTree a

O(1). Analyse the right end of a sequence.

split :: Measured a => (Measure a -> Bool) -> FingerTree a -> (FingerTree a, FingerTree a)

O(log(min(i,n-i))). Split a sequence at a point where the predicate on the accumulated measure changes from False to True.

For predictable results, one should ensure that there is only one such point, i.e. that the predicate is monotonic.

takeUntil :: Measured a => (Measure a -> Bool) -> FingerTree a -> FingerTree a

O(log(min(i,n-i))). Given a monotonic predicate p, takeUntil p t is the largest prefix of t whose measure does not satisfy p.

• takeUntil p t = fst (split p t)

dropUntil :: Measured a => (Measure a -> Bool) -> FingerTree a -> FingerTree a

O(log(min(i,n-i))). Given a monotonic predicate p, dropUntil p t is the rest of t after removing the largest prefix whose measure does not satisfy p.

• dropUntil p t = snd (split p t)

Transformation

reverse :: Measured a => FingerTree a -> FingerTree a

O(n). The reverse of a sequence.

fmap' :: (Measured a, Measured b) => (a -> b) -> FingerTree a -> FingerTree b

Like fmap, but with a more constrained type.

fmapWithPos :: (Measured a, Measured b) => (Measure a -> a -> b) -> FingerTree a -> FingerTree b

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

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)

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)

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)

Like traverse, but safe only if the function preserves the measure.