HORIZON HASKELLDocslts/ghc-9.10.xc74966e2026-09-27Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · c74966e · 2026-09-27

Modulehw-fingertree-0.1.2.1Haskell2010

HaskellWorks.Data.FingerTree

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.

  • 5 types
  • 1 class
  • 23 values
datadata FingerTree v a
#

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.

Constructors

Instances14Measured, Foldable, Eq, Ord, Show, Generic, …
datadata Digit a
#

Constructors

Instances7Functor, Foldable, Measured, Show, Generic, NFData, …
datadata Node v a
#

Constructors

Instances6Measured, Foldable, Show, Generic, NFData, Rep
classclass Monoid v => Measured v a | a -> v where
#

Things that can be measured.

Methods

Instances5Measured
  • Measured v a => Measured v (Digit a)Defined in hw-fingertree-0.1.2.1 · HaskellWorks.Data.FingerTree
  • Monoid v => Measured v (Node v a)Defined in hw-fingertree-0.1.2.1 · HaskellWorks.Data.FingerTree
  • Measured v a => Measured v (FingerTree v a)Defined in hw-fingertree-0.1.2.1 · HaskellWorks.Data.FingerTree

    O(1). The cached measure of a tree.

  • Ord v => Measured (IntInterval v) (Node v a)Defined in hw-fingertree-0.1.2.1 · HaskellWorks.Data.IntervalMap.FingerTree
  • Ord k => Measured (Prio k v) (Entry k v)Defined in hw-fingertree-0.1.2.1 · HaskellWorks.Data.PriorityQueue.FingerTree

Construction

4 declarations

Deconstruction

8 declarations
datadata ViewL (s :: Type -> Type) a
#

View of the left end of a sequence.

Constructors

  • EmptyL

    empty sequence

  • a :< s ainfixr 5

    leftmost element and the rest of the sequence

Instances8Functor, Eq, Ord, Read, Show, Generic, …
datadata ViewR (s :: Type -> Type) a
#

View of the right end of a sequence.

Constructors

  • EmptyR

    empty sequence

  • s a :> ainfixl 5

    the sequence minus the rightmost element, -- and the rightmost element

Instances8Functor, Eq, Ord, Read, Show, Generic, …
valuesplit
  1. :: Measured v a
  2. => v -> Bool
  3. -> FingerTree v a
  4. -> (FingerTree v a, FingerTree v a)
#

O(log(min(i,n-i))). Split a sequence at a point where the predicate on the accumulated measure 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.

Transformation

7 declarations

Example

3 declarations

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.