IntervalMap: Containers for intervals, with efficient search.

[ bsd3, data, library ] [ Propose Tags ]
Versions 0.2.0, 0.2.1, 0.2.2, 0.2.3,,,,,,,,,,,,,,,,,,
Change log changelog
Dependencies base (==4.*), containers, deepseq [details]
License BSD-3-Clause
Copyright 2011-2018 Christoph Breitkopf
Author Christoph Breitkopf
Maintainer Christoph Breitkopf <>
Category Data
Home page
Bug tracker
Source repo head: git clone
Uploaded by ChristophBreitkopf at Fri Mar 16 09:32:12 UTC 2018
Distributions LTSHaskell:, NixOS:, Stackage:, openSUSE:
Downloads 8070 total (99 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-03-16 [all 1 reports]
Hackage Matrix CI

Ordered containers of intervals, with efficient search for all keys containing a point or overlapping an interval. See the example code on the home page for a quick introduction.

[Skip to Readme]




Maintainer's Corner

For package maintainers and hackage trustees

Readme for IntervalMap-

[back to package description]

IntervalMap Hackage Build Status

Containers for intervals. Like Data.Set and Data.Map with Intervals as keys and functions for efficiently getting the subset of all intervals containing a point, intersecting an interval, and more.

Home page and documentation:

Getting started

Enable necessary language extensions:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

In most cases, you should use the value-strict version:

import qualified Data.IntervalMap.Generic.Strict as IM

Make tuples an instance of Interval:

instance Ord e => IM.Interval (e,e) e where
    lowerBound (a,_) = a
    upperBound (_,b) = b
    rightClosed _ = False

By using rightClosed _ = False we have defined tuples to be half-open intervals - they include the starting value, but not the end value.

Let's create a map from (Int,Int) intervals to strings:

type MyMap = IM.IntervalMap (Int,Int) String

sample :: MyMap
sample = IM.fromList [((1,6), "Foo"), ((2,4), "Bar"), ((4,7), "Baz")]

Lookup intervals containing a given point ("stabbing query"):

> IM.toAscList (sample `IM.containing` 3)
> IM.toAscList (sample `IM.containing` 4)