Portability | non-portable (MPTCs and functional dependencies) |
---|---|

Stability | experimental |

Maintainer | ross@soi.city.ac.uk |

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 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

Finger trees with element type `a`

, annotated with measures of type `v`

.
The operations enforce the constraint

.
`Measured`

v a

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) |

# 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?

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) 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

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.