Haskell Interval Containers

An implementation of sets of intervals and maps from intervals to values. The intervals may overlap, and the implementation supports efficient queries for all intervals containing a point or intersecting a given interval.

You should normally install it from Hackage with

    cabal install IntervalMap
I try to keep the interface stable between minor releases, so if you have this as a dependency in a cabal project, use constraints like this:
    Build-depends: IntervalMap >= 0.6 < 0.7

Source on GitHub.


API docs on Hackage.

A simple example. (Old version not requiring language extensions)

If IntervalMap does not fit your needs, you might want to look at these packages on Hackage: SegmentTree FingerTree SplayTree Ranged-sets 2018-03-16 Support GHC 8.4. Drop support for GHC 7. 2017-11-05 Add looupLT... functions. 2016-11-21 Bugfix: exported Prelude functions instead of correct ones. 2016-06-01 Major performance improvements. 2016-01-13 Changed containing... to return a Map instead of a list (breaking change).
Added splitAt, splitIntersecting, and flatten... functions.
Minor performance tweaks. 2015-12-03 IntervalSet added. Minor performance tweaks and documentation fixes. 2014-08-29 Documentation updated and portability info fixed. 2014-08-29 Major update. It is now possible to use any type as key interval by making it an instance of Data.IntervalMap.Generic.Interval. This requires the languages extensions MultiParamTypeClasses and FlexibleInstances. The old interface is still supported for compatibility. 2014-08-11 Updated benchmark to use Criterion 1.0; tested with ghc 7.8.3. 2013-08-08 Dropped upper constraint on criterion; tested with ghc 7.6.3; migrated repo to Darcs Hub. 2012-08-07 Bugfixes: Lazy was too strict, Strict too lazy. 2012-08-03 Split into Lazy and Strict modules, following containers. 2012-04-24 Fixed error when building benchmarks with ghc 7.4.1.
Improved performance of deleteMin family of functions by about 30%.
Added benchmarks for deleteMin family of functions.
Reduced benchmark data size for more reasonable run times.
Added source-repository section to cabal spec. 2012-04-20 Added benchmarks, including a benchmark section in the cabal spec, so you can use cabal bench to run the benchmark. Here is a sample report.
Fixed cabal spec so that the test suites no longer require installing the package first. 2012-02-15 Improved documentation.
Removed ineffective INLINE pragmas.
0.2.3 2012-01-09 Added minView... family of functions.
Added isSubmap... family of functions.
Rewrote mapKeysMonotonic te be O(n).
0.2.2 2012-01-05 Improved performance of insert... and fromList... functions.
Added some example code.
0.2.1 2012-01-03 Documentation update: Added Big-O annotations.
0.2.0 2011-12-14 Changed argument order and name: searchPoint -> containing, searchInterval -> intersecting.
Added functions: within, findLast, updateMin/Max....
0.1.2 2011-12-12 Initial release.