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

Stability | experimental |

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

Safe Haskell | Safe-Infered |

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

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 a`v`

is determined by `a`

.

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

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.

# Example

Particular abstract data types may be implemented by defining
element types with suitable `Measured`

instances.

(from section 4.5 of the paper)
Simple sequences can be implemented using a `Sum`

monoid as a measure:

newtype Elem a = Elem { getElem :: a } instance Measured (Sum Int) (Elem a) where measure (Elem _) = Sum 1 newtype Seq a = Seq (FingerTree (Sum Int) (Elem a))

Then the measure of a subsequence is simply its length. This representation supports log-time extraction of subsequences:

take :: Int -> Seq a -> Seq a take k (Seq xs) = Seq (takeUntil (> Sum k) xs) drop :: Int -> Seq a -> Seq a drop k (Seq xs) = Seq (dropUntil (> Sum k) xs)

The module `Data.Sequence`

is an optimized instantiation of this type.

For further examples, see Data.IntervalMap.FingerTree and Data.PriorityQueue.FingerTree.