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

Copyright | (c) Ross Paterson Ralf Hinze 2006
License | BSD-style
Maintainer | R.Paterson@city.ac.uk
Stability | experimental
Portability | non-portable (MPTCs and functional dependencies)
Safe Haskell | Safe
Language | Haskell2010

Data.FingerTree

Contents

- Construction
- Deconstruction
  - Examining the ends
  - Search
  - Splitting
- Transformation
  - Maps
  - Traversals
- Example

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

- Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", Journal of Functional Programming 16:2 (2006) pp 197-217. http://staff.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.

Synopsis

- data FingerTree v a
- class Monoid v => Measured v a | a -> v where
- 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 :: FingerTree v a -> Bool
- data ViewL s a
  - = EmptyL
  - | a :< (s a)
- viewl :: Measured v a => FingerTree v a -> ViewL (FingerTree v) a
- data ViewR s a
  - = EmptyR
  - | (s a) :> a
- viewr :: Measured v a => FingerTree v a -> ViewR (FingerTree v) a
- data SearchResult v a
  - = Position (FingerTree v a) a (FingerTree v a)
  - | OnLeft
  - | OnRight
  - | Nowhere
- search :: Measured v a => (v -> v -> Bool) -> FingerTree v a -> SearchResult 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
- fmapWithContext :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> v1 -> 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)
- traverseWithContext :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> v1 -> 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 ``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

Measured v a => Measured v (FingerTree v a) Source # | O(1). The cached measure of a tree.
Methods measure :: FingerTree v a -> v Source #
Foldable (FingerTree v) Source # | Elements from left to right.

Methods

fold :: Monoid m => FingerTree v m -> m #

foldMap :: Monoid m => (a -> m) -> FingerTree v a -> m #

foldr :: (a -> b -> b) -> b -> FingerTree v a -> b #

foldr' :: (a -> b -> b) -> b -> FingerTree v a -> b #

foldl :: (b -> a -> b) -> b -> FingerTree v a -> b #

foldl' :: (b -> a -> b) -> b -> FingerTree v a -> b #

foldr1 :: (a -> a -> a) -> FingerTree v a -> a #

foldl1 :: (a -> a -> a) -> FingerTree v a -> a #

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

null :: FingerTree v a -> Bool #

length :: FingerTree v a -> Int #

elem :: Eq a => a -> FingerTree v a -> Bool #

maximum :: Ord a => FingerTree v a -> a #

minimum :: Ord a => FingerTree v a -> a #

sum :: Num a => FingerTree v a -> a #

product :: Num a => FingerTree v a -> a #

Eq a => Eq (FingerTree v a) Source # |
Methods (==) :: FingerTree v a -> FingerTree v a -> Bool # (/=) :: FingerTree v a -> FingerTree v a -> Bool #
Ord a => Ord (FingerTree v a) Source # | Lexicographical order from left to right.
Methods compare :: FingerTree v a -> FingerTree v a -> Ordering # (<) :: FingerTree v a -> FingerTree v a -> Bool # (<=) :: FingerTree v a -> FingerTree v a -> Bool # (>) :: FingerTree v a -> FingerTree v a -> Bool # (>=) :: FingerTree v a -> FingerTree v a -> Bool # max :: FingerTree v a -> FingerTree v a -> FingerTree v a # min :: FingerTree v a -> FingerTree v a -> FingerTree v a #
Show a => Show (FingerTree v a) Source # |
Methods showsPrec :: Int -> FingerTree v a -> ShowS # show :: FingerTree v a -> String # showList :: [FingerTree v a] -> ShowS #
Measured v a => Semigroup (FingerTree v a) Source # |
Methods (<>) :: FingerTree v a -> FingerTree v a -> FingerTree v a # sconcat :: NonEmpty (FingerTree v a) -> FingerTree v a # stimes :: Integral b => b -> FingerTree v a -> FingerTree v a #
Measured v a => Monoid (FingerTree v a) Source # | `empty` and `><`.
Methods mempty :: FingerTree v a # mappend :: FingerTree v a -> FingerTree v a -> FingerTree v a # mconcat :: [FingerTree v a] -> FingerTree v a #

class Monoid v => Measured v a | a -> v where Source #

Things that can be measured.

Minimal complete definition

measure

Methods

measure :: a -> v Source #

Instances

Measured v a => Measured v (FingerTree v a) Source # | O(1). The cached measure of a tree.
Methods measure :: FingerTree v a -> v Source #

# Construction

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.

(<|) :: 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. Mnemonic: a triangle with the single element at the pointy end.

(|>) :: Measured v a => FingerTree v a -> a -> FingerTree v a infixl 5 Source #

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 a infixr 5 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. The opposite operation `toList` is supplied by the `Foldable` instance.

# Deconstruction

null :: FingerTree v a -> Bool Source #

O(1). Is this the empty sequence?

## Examining the ends

data ViewL s a Source #

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) Source # |
Methods fmap :: (a -> b) -> ViewL s a -> ViewL s b # (<$) :: a -> ViewL s b -> ViewL s a #
(Eq (s a), Eq a) => Eq (ViewL s a) Source # |
Methods (==) :: ViewL s a -> ViewL s a -> Bool # (/=) :: ViewL s a -> ViewL s a -> Bool #
(Ord (s a), Ord a) => Ord (ViewL s a) Source # |
Methods compare :: ViewL s a -> ViewL s a -> Ordering # (<) :: ViewL s a -> ViewL s a -> Bool # (<=) :: ViewL s a -> ViewL s a -> Bool # (>) :: ViewL s a -> ViewL s a -> Bool # (>=) :: ViewL s a -> ViewL s a -> Bool # max :: ViewL s a -> ViewL s a -> ViewL s a # min :: ViewL s a -> ViewL s a -> ViewL s a #
(Read (s a), Read a) => Read (ViewL s a) Source # |
Methods readsPrec :: Int -> ReadS (ViewL s a) # readList :: ReadS [ViewL s a] # readPrec :: ReadPrec (ViewL s a) # readListPrec :: ReadPrec [ViewL s a] #
(Show (s a), Show a) => Show (ViewL s a) Source # |
Methods showsPrec :: Int -> ViewL s a -> ShowS # show :: ViewL s a -> String # showList :: [ViewL s a] -> ShowS #

viewl :: Measured v a => FingerTree v a -> ViewL (FingerTree v) a Source #

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

data ViewR s a Source #

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) Source # |
Methods fmap :: (a -> b) -> ViewR s a -> ViewR s b # (<$) :: a -> ViewR s b -> ViewR s a #
(Eq (s a), Eq a) => Eq (ViewR s a) Source # |
Methods (==) :: ViewR s a -> ViewR s a -> Bool # (/=) :: ViewR s a -> ViewR s a -> Bool #
(Ord (s a), Ord a) => Ord (ViewR s a) Source # |
Methods compare :: ViewR s a -> ViewR s a -> Ordering # (<) :: ViewR s a -> ViewR s a -> Bool # (<=) :: ViewR s a -> ViewR s a -> Bool # (>) :: ViewR s a -> ViewR s a -> Bool # (>=) :: ViewR s a -> ViewR s a -> Bool # max :: ViewR s a -> ViewR s a -> ViewR s a # min :: ViewR s a -> ViewR s a -> ViewR s a #
(Read (s a), Read a) => Read (ViewR s a) Source # |
Methods readsPrec :: Int -> ReadS (ViewR s a) # readList :: ReadS [ViewR s a] # readPrec :: ReadPrec (ViewR s a) # readListPrec :: ReadPrec [ViewR s a] #
(Show (s a), Show a) => Show (ViewR s a) Source # |
Methods showsPrec :: Int -> ViewR s a -> ShowS # show :: ViewR s a -> String # showList :: [ViewR s a] -> ShowS #

viewr :: Measured v a => FingerTree v a -> ViewR (FingerTree v) a Source #

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

## Search

data SearchResult v a Source #

A result of `search`, attempting to find a point where a predicate on splits of the sequence changes from `False` to `True`.

Constructors

Position (FingerTree v a) a (FingerTree v a) | A tree opened at a particular element: the prefix to the left, the element, and the suffix to the right.
OnLeft | A position to the left of the sequence, indicating that the predicate is `True` at both ends.
OnRight | A position to the right of the sequence, indicating that the predicate is `False` at both ends.
Nowhere | No position in the tree, returned if the predicate is `True` at the left end and `False` at the right end. This will not occur if the predicate in monotonic on the tree.

Instances

Eq a => Eq (SearchResult v a) Source # |
Methods (==) :: SearchResult v a -> SearchResult v a -> Bool # (/=) :: SearchResult v a -> SearchResult v a -> Bool #
Ord a => Ord (SearchResult v a) Source # |

Methods

compare :: SearchResult v a -> SearchResult v a -> Ordering #

(<) :: SearchResult v a -> SearchResult v a -> Bool #

(<=) :: SearchResult v a -> SearchResult v a -> Bool #

(>) :: SearchResult v a -> SearchResult v a -> Bool #

(>=) :: SearchResult v a -> SearchResult v a -> Bool #

max :: SearchResult v a -> SearchResult v a -> SearchResult v a #

min :: SearchResult v a -> SearchResult v a -> SearchResult v a #

Show a => Show (SearchResult v a) Source # |
Methods showsPrec :: Int -> SearchResult v a -> ShowS # show :: SearchResult v a -> String # showList :: [SearchResult v a] -> ShowS #

search :: Measured v a => (v -> v -> Bool) -> FingerTree v a -> SearchResult v a Source #

O(log(min(i,n-i))). Search a sequence for a point where a predicate on splits of the sequence changes from `False` to `True`.

The argument `p` is a relation between the measures of the two sequences that could be appended together to form the sequence `t`. If the relation is `False` at the leftmost split and `True` at the rightmost split, i.e.

    not (p mempty (measure t)) && p (measure t) mempty

then there must exist an element `x` in the sequence such that `p` is `False` for the split immediately before `x` and `True` for the split just after it:

In this situation, ``search` p t` returns such an element `x` and the pieces `l` and `r` of the sequence to its left and right respectively. That is, it returns ``Position` l x r` such that

-     l >< (x <| r) = t

-     not (p (measure l) (measure (x <| r))

-     p (measure (l |> x)) (measure r)

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

## Splitting

These functions are special cases of `search`.

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 of the prefix 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 v a => (v -> Bool) -> FingerTree v a -> FingerTree v a Source #

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 v a => (v -> Bool) -> FingerTree v a -> FingerTree v a Source #

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 v a => FingerTree v a -> FingerTree v a Source #

O(n). The reverse of a sequence.

## Maps

fmap' :: (Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 Source #

Like `fmap`, but with constraints on the element types.

fmapWithPos :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 Source #

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.

fmapWithContext :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> v1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 Source #

Map all elements of the tree with a function that also takes the measure of the prefix to the left and of the suffix to the right of the element.

unsafeFmap :: (a -> b) -> FingerTree v a -> FingerTree v b Source #

Like `fmap`, but safe only if the function preserves the measure.

## Traversals

traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) Source #

Like `traverse`, but with constraints on the element types.

traverseWithPos :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) Source #

Traverse the tree from left to right with a function that also takes the measure of the prefix of the tree to the left of the element.

traverseWithContext :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> v1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) Source #

Traverse the tree from left to right with a function that also takes the measure of the prefix to the left and the measure of the suffix to the right 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.