Haskell Range Map library

Question

Is there a Haskell library that allows me to have a Map from ranges to values? (Preferable somewhat efficient.)

let myRangeMap = RangeMap [(range 1 3, "foo"),(range 2 7, "bar"),(range 9 12, "baz")]
in  rangeValues 2
==> ["foo","bar"]

Answer 1

Perhaps the rangemin library does what you want?

Good old Data.Map (and its more efficient Data.IntMap cousin) has a function

splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)

which splits a map into submaps of keys less than / greater than a given key. This can be used for certain kinds of range searching.

Answer 2

This task is called a stabbing query on a set of intervals. An efficient data structure for it is called (one-dimensional) segment tree.

The SegmentTree package provides an implementation of this data structure, but unfortunately I cannot figure out how to use it. (I feel that the interface of this package does not provide the right level of abstraction.)