Copyright | (c) Ross Paterson, Ralf Hinze 2006 |
---|---|

License | BSD-style |

Maintainer | robdockins AT fastmail DOT fm |

Stability | internal (non-stable) |

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

Safe Haskell | None |

Language | Haskell2010 |

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

This data structure forms the basis of the Data.Edison.Seq.FingerSeq sequence data 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.

- data FingerTree v a
- data Split t a = Split t a t
- empty :: Measured v a => FingerTree v a
- singleton :: Measured v a => a -> FingerTree v a
- lcons :: Measured v a => a -> FingerTree v a -> FingerTree v a
- rcons :: Measured v a => a -> FingerTree v a -> FingerTree v a
- append :: Measured v a => FingerTree v a -> FingerTree v a -> FingerTree v a
- fromList :: Measured v a => [a] -> FingerTree v a
- toList :: FingerTree v a -> [a]
- null :: Measured v a => FingerTree v a -> Bool
- size :: FingerTree v a -> Int
- lview :: (Measured v a, Monad m) => FingerTree v a -> m (a, FingerTree v a)
- rview :: (Measured v a, Monad m) => FingerTree v a -> m (a, 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
- splitTree :: Measured v a => (v -> Bool) -> v -> FingerTree v a -> Split (FingerTree v a) a
- reverse :: Measured v a => FingerTree v a -> FingerTree v a
- mapTree :: Measured v2 a2 => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2
- foldFT :: b -> (b -> b -> b) -> (a -> b) -> FingerTree v a -> b
- reduce1 :: (a -> a -> a) -> FingerTree v a -> a
- reduce1' :: (a -> a -> a) -> FingerTree v a -> a
- strict :: FingerTree v a -> FingerTree v a
- strictWith :: (a -> b) -> FingerTree v a -> FingerTree v a
- structuralInvariant :: (Eq v, Measured v a) => FingerTree v a -> Bool

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

(Measured v a, Eq a) => Eq (FingerTree v a) Source | |

(Measured v a, Ord a) => Ord (FingerTree v a) Source | |

(Measured v a, Show a) => Show (FingerTree v a) Source | |

(Measured v a, Arbitrary a) => Arbitrary (FingerTree v a) Source | |

(Measured v a, CoArbitrary a) => CoArbitrary (FingerTree v a) Source |

empty :: Measured v a => FingerTree v a Source

*O(1)*. The empty sequence.

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

*O(1)*. A singleton sequence.

lcons :: Measured v a => a -> FingerTree v a -> FingerTree v a infixr 5 Source

*O(1)*. Add an element to the left end of a sequence.

rcons :: Measured v a => a -> FingerTree v a -> FingerTree v a Source

*O(1)*. Add an element to the right end of a sequence.

append :: Measured v a => FingerTree v a -> FingerTree v a -> FingerTree v a Source

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

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

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

toList :: FingerTree v a -> [a] Source

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

*O(1)*. Is this the empty sequence?

size :: FingerTree v a -> Int Source

lview :: (Measured v a, Monad m) => FingerTree v a -> m (a, FingerTree v a) Source

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

rview :: (Measured v a, Monad m) => FingerTree v a -> m (a, FingerTree v a) Source

*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 a Source

dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a Source

splitTree :: Measured v a => (v -> Bool) -> v -> FingerTree v a -> Split (FingerTree v a) a Source

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

*O(n)*. The reverse of a sequence.

mapTree :: Measured v2 a2 => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 Source

foldFT :: b -> (b -> b -> b) -> (a -> b) -> FingerTree v a -> b Source

reduce1 :: (a -> a -> a) -> FingerTree v a -> a Source

reduce1' :: (a -> a -> a) -> FingerTree v a -> a Source

strict :: FingerTree v a -> FingerTree v a Source

strictWith :: (a -> b) -> FingerTree v a -> FingerTree v a Source

structuralInvariant :: (Eq v, Measured v a) => FingerTree v a -> Bool Source