Skip to content

HORIZON HASKELL Docs lts/ghc-10.0.x8fef28d2026-11-02Search packagesCtrl K

Theme: |

GHC 10.0.0.20260917 · lts/ghc-10.0.x · 8fef28d · 2026-11-02

Modulefingertree-0.1.6.3Haskell2010

Data.IntervalMap.FingerTree

Interval maps implemented using the FingerTree type, following section 4.8 of

Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", Journal of Functional Programming 16:2 (2006) pp 197-217. https://staff.city.ac.uk/~ross/papers/FingerTree.html

An amortized running time is given for each operation, with n referring to the size of the priority queue. 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.

Contents

Intervals
Interval maps
Searching
Extraction

Synopsis

data Interval
value low
value high
value point
newtype IntervalMap
value empty
value singleton
value insert
value union
value search
value intersections
value dominators
value bounds
value leastView
value splitAfter

Packagefingertree-0.1.6.3
Exports15
LanguageHaskell2010
LicenceBSD-3-Clause
SourceFingerTree.hs

Intervals

datadata Interval v

A closed interval. The lower bound should be less than or equal to the upper bound.

Constructors

Interval v v
Lower and upper bounds of the interval.

Instances7Eq, Ord, Read, Show, Generic, NFData, …

Eq v => Eq (Interval v)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Ord v => Ord (Interval v)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Read v => Read (Interval v)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Show v => Show (Interval v)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Generic (Interval v)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
NFData v => NFData (Interval v)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
type Rep (Interval v) = D1 ('MetaData "Interval" "Data.IntervalMap.FingerTree" "fingertree-0.1.6.3-B8CU734UHLyCZi1QPrWLO3" 'False) (C1 ('MetaCons "Interval" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 v) :*: S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 v)))Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree

valuelow :: Interval v -> v

Lower bound of the interval

valuehigh :: Interval v -> v

Upper bound of the interval

valuepoint :: v -> Interval v

An interval in which the lower and upper bounds are equal.

Interval maps

newtypenewtype IntervalMap v a

Map of closed intervals, possibly with duplicates.

Instances11Functor, Foldable, Traversable, Eq, Ord, Show, …

Functor (IntervalMap v)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Foldable (IntervalMap v)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Values in lexicographical order of intervals.
Traversable (IntervalMap v)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Traverse the intervals in lexicographical order.
(Eq v, Eq a) => Eq (IntervalMap v a)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
(Ord v, Ord a) => Ord (IntervalMap v a)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Lexicographical ordering
(Show v, Show a) => Show (IntervalMap v a)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Generic (IntervalMap v a)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
Ord v => Semigroup (IntervalMap v a)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
union.
Ord v => Monoid (IntervalMap v a)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
empty and union.
(NFData a, NFData v) => NFData (IntervalMap v a)Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree
type Rep (IntervalMap v a) = D1 ('MetaData "IntervalMap" "Data.IntervalMap.FingerTree" "fingertree-0.1.6.3-B8CU734UHLyCZi1QPrWLO3" 'True) (C1 ('MetaCons "IntervalMap" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (FingerTree (IntInterval v) (Node v a)))))Defined in fingertree-0.1.6.3 · Data.IntervalMap.FingerTree

valueempty :: Ord v => IntervalMap v a

O(1). The empty interval map.

valuesingleton :: Ord v => Interval v -> a -> IntervalMap v a

O(1). Interval map with a single entry.

valueinsert :: Ord v => Interval v -> a -> IntervalMap v a -> IntervalMap v a

O(log n). Insert an interval and associated value into a map. The map may contain duplicate intervals; the new entry will be inserted before any existing entries for the same interval.

valueunion :: Ord v => IntervalMap v a -> IntervalMap v a -> IntervalMap v a

O(m log (n/m)). Merge two interval maps. The map may contain duplicate intervals; entries with equal intervals are kept in the original order.

Searching

valuesearch :: Ord v => v -> IntervalMap v a -> [(Interval v, a)]

O(k log (n/k)). All intervals that contain the given point, in lexicographical order.

valueintersections :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]

O(k log (n/k)). All intervals that intersect with the given interval, in lexicographical order.

valuedominators :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]

O(k log (n/k)). All intervals that contain the given interval, in lexicographical order.

Extraction

valuebounds :: Ord v => IntervalMap v a -> Maybe (Interval v)

O(1). bounds m returns Nothing if m is empty, and otherwise Just i, where i is the smallest interval containing all the intervals in the map.

valueleastView

:: Ord v
=> IntervalMap v a
-> Maybe ((Interval v, a), IntervalMap v a)

O(1). leastView m returns Nothing if m is empty, and otherwise Just ((i, x), m'), where i is the least interval, x is the associated value, and m' is the rest of the map.

valuesplitAfter

:: Ord v
=> v
-> IntervalMap v a
-> (IntervalMap v a, IntervalMap v a)

O(log(min(i,n-i))). splitAfter k m returns a pair of submaps, one consisting of intervals whose lower bound is less than or equal to k, and the other of those whose lower bound is greater.