Есть ли библиотека Haskell, которая позволяет мне иметь карту от диапазонов до значений? (Предпочтительно несколько эффективный.)
let myRangeMap = RangeMap [(range 1 3, "foo"),(range 2 7, "bar"),(range 9 12, "baz")]
in rangeValues 2
==> ["foo","bar"]
Эта задача называется запросом колоды на множестве интервалов. Эффективная структура данных для него называется (одномерным) деревом сегментов.
пакет SegmentTree обеспечивает реализацию этой структуры данных, но, к сожалению, я не могу понять, как ее использовать. (Я чувствую, что интерфейс этого пакета не обеспечивает нужный уровень абстракции.)
Я написал библиотеку для поиска в перекрывающиеся интервалы, потому что существующие не соответствовали моим потребностям. Я думаю, что он может иметь более доступный интерфейс, чем, например, SegmentTree:
http://www.chr-breitkopf.de/comp/IntervalMap/index.html
Он также доступен в Hackage: http://hackage.haskell.org/package/IntervalMap
Возможно, rangemin library делает то, что вы хотите?
Старый добрый Data.Map (и его более эффективный кузена Data.IntMap) имеет функцию
splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
который разбивает карту на подмапки ключей, меньших/больше заданного ключа. Это можно использовать для определенных видов поиска диапазона.