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

Copyright (c) Ross Paterson Ralf Hinze 2006 BSD-style R.Paterson@city.ac.uk experimental non-portable (MPTCs and functional dependencies) Safe Haskell2010

Data.FingerTree

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

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

# 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. Methodsmeasure :: FingerTree v a -> v Source # Source # Elements from left to right. Methodsfold :: 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. Methodscompare :: 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 # MethodsshowsPrec :: Int -> FingerTree v a -> ShowS #show :: FingerTree v a -> String #showList :: [FingerTree v a] -> ShowS # Generic (FingerTree v a) Source # Associated Typestype Rep (FingerTree v a) :: * -> * # Methodsfrom :: FingerTree v a -> Rep (FingerTree v a) x #to :: Rep (FingerTree v a) x -> FingerTree v a # 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 ><. Methodsmempty :: FingerTree v a #mappend :: FingerTree v a -> FingerTree v a -> FingerTree v a #mconcat :: [FingerTree v a] -> FingerTree v a # type Rep (FingerTree v a) Source # type Rep (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. Methodsmeasure :: 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 # Methodsfmap :: (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 # Methodscompare :: 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 # MethodsreadsPrec :: 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 # MethodsshowsPrec :: Int -> ViewL s a -> ShowS #show :: ViewL s a -> String #showList :: [ViewL s a] -> ShowS # Generic (ViewL s a) Source # Associated Typestype Rep (ViewL s a) :: * -> * # Methodsfrom :: ViewL s a -> Rep (ViewL s a) x #to :: Rep (ViewL s a) x -> ViewL s a # type Rep (ViewL s a) Source # type Rep (ViewL s a) = D1 * (MetaData "ViewL" "Data.FingerTree" "fingertree-0.1.4.1-GNuCBfIfWR5LF1bN45m0JD" False) ((:+:) * (C1 * (MetaCons "EmptyL" PrefixI False) (U1 *)) (C1 * (MetaCons ":<" (InfixI RightAssociative 5) False) ((:*:) * (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * a)) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * (s a)))))) 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 # Methodsfmap :: (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 # Methodscompare :: 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 # MethodsreadsPrec :: 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 # MethodsshowsPrec :: Int -> ViewR s a -> ShowS #show :: ViewR s a -> String #showList :: [ViewR s a] -> ShowS # Generic (ViewR s a) Source # Associated Typestype Rep (ViewR s a) :: * -> * # Methodsfrom :: ViewR s a -> Rep (ViewR s a) x #to :: Rep (ViewR s a) x -> ViewR s a # type Rep (ViewR s a) Source # type Rep (ViewR s a) = D1 * (MetaData "ViewR" "Data.FingerTree" "fingertree-0.1.4.1-GNuCBfIfWR5LF1bN45m0JD" False) ((:+:) * (C1 * (MetaCons "EmptyR" PrefixI False) (U1 *)) (C1 * (MetaCons ":>" (InfixI LeftAssociative 5) False) ((:*:) * (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * (s a))) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * a)))))

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.

Since: 0.1.2.0

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 # Methodscompare :: 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 # MethodsshowsPrec :: Int -> SearchResult v a -> ShowS #show :: SearchResult v a -> String #showList :: [SearchResult v a] -> ShowS # Generic (SearchResult v a) Source # Associated Typestype Rep (SearchResult v a) :: * -> * # Methodsfrom :: SearchResult v a -> Rep (SearchResult v a) x #to :: Rep (SearchResult v a) x -> SearchResult v a # type Rep (SearchResult v a) Source # type Rep (SearchResult v a) = D1 * (MetaData "SearchResult" "Data.FingerTree" "fingertree-0.1.4.1-GNuCBfIfWR5LF1bN45m0JD" False) ((:+:) * ((:+:) * (C1 * (MetaCons "Position" PrefixI False) ((:*:) * (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * (FingerTree v a))) ((:*:) * (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * a)) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * (FingerTree v a)))))) (C1 * (MetaCons "OnLeft" PrefixI False) (U1 *))) ((:+:) * (C1 * (MetaCons "OnRight" PrefixI False) (U1 *)) (C1 * (MetaCons "Nowhere" PrefixI False) (U1 *))))

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.

Since: 0.1.2.0

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

Since: 0.1.2.0

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.

Since: 0.1.2.0

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.