Containers for intervals, with efficient search.

Version on this page:
LTS Haskell 13.25:
Stackage Nightly 2019-06-12:
Latest on Hackage:

See all snapshots IntervalMap appears in

BSD-3-Clause licensed by Christoph Breitkopf
Maintained by Christoph Breitkopf

Module documentation for

There are no documented modules for this package.

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)

Changes Improve Semigroup instances. Add safe versions of find... functions. Support ghc 8.4, desupport ghc 7.x. Remove HPC flag. Add lookupLT... functions. Bugfix: exported Prelude functions instead of correct ones. Improve performance of findLast. Major performance improvements. Improve performance of combine.
Fix wrong doc comments. Change return type of containing, ... to a map.
Add splitAt, splitIntersecting, flatten... functions.
Minor performance tweaks. Fix bug in benchmark. Add IntervalSet.
Minor performance tweaks.
Documentation updates.
Moved to GitHub. Documentation update. Wrong portability info fixed. Major update adding support for user-defined key intervals. Updated benchmark to use Criterion 1.0. Tested with ghc 7.8.3. Dropped upper constraint on criterion. Tested with ghc 7.6.3.
Migrated repo to Darcs Hub. Bugfixes: Lazy was too strict, Strict too lazy. Split into Lazy and Strict modules, following containers.

Depends on 3 packages:
comments powered byDisqus