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.IntervalMap.FingerTree

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

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.

  • 2 types
  • 8 values

Intervals

2 declarations
datadata Interval v
#

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

Constructors

Instances6Eq, Ord, Show, Generic, NFData, Rep
valuepoint :: v -> Interval v
#

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

Interval maps

5 declarations
newtypenewtype IntervalMap v a
#

Map of closed intervals, possibly with duplicates. The Foldable and Traversable instances process the intervals in lexicographical order.

Constructors

Instances8Functor, Foldable, Traversable, Generic, Semigroup, Monoid, …
valueinsert :: Ord v => Interval v -> a -> IntervalMap v a -> IntervalMap v a
#

O(log n). Insert an interval 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

3 declarations
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.