Библиотека карт диапазона Хаскелла

Question

Есть ли библиотека Haskell, которая позволяет мне иметь карту от диапазонов до значений? (Предпочтительно несколько эффективнее.)

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

Answer 1

Эта задача называется запросом с ограничением по интервалам.Эффективная структура данных для этого называется (одномерная) дерево сегментов .

Пакет SegmentTree обеспечивает реализацию этой структуры данных, но, к сожалению, я не могу понятькак это использовать.(Мне кажется, что интерфейс этого пакета не обеспечивает правильный уровень абстракции.)

Answer 2

Я написал библиотеку для поиска через перекрывающиеся интервалы, потому что существующие не соответствовали моим потребностям. Я думаю, что он может иметь более доступный интерфейс, чем, например, SegmentTree:

http://www.chr -breitkopf.de / сост / IntervalMap / index.html

Это также доступно на Hackage: http://hackage.haskell.org/package/IntervalMap

Answer 3

Возможно, rangemin библиотека делает то, что вы хотите?

Старый добрый Data.Map (и его более эффективный Data.IntMap двоюродный брат) имеет функцию

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

, которая разбивает карту на подкарты ключей меньше / больше, чем данный ключ. Это может быть использовано для определенных видов поиска диапазона.