Haskell范围地图库

Question

是否有一个Haskell库允许我从范围到值有一个Map？(优选有点效率.)

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

Answer 1

也许rangemin图书馆做你想要的？

好老Data.Map(及其更高效的Data.IntMap堂兄)有一个功能

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

它将地图分成小于/大于给定键的键的子图.这可以用于某些范围的搜索.

Answer 2

此任务称为一组间隔的刺穿查询.它的有效数据结构称为(一维)分段树.

该线段树包提供了这种数据结构的实现,但不幸的是我无法弄清楚如何使用它.(我觉得这个包的接口没有提供正确的抽象级别.)

Answer 3

我写了一个库来重叠间隔搜索,因为现有的库不符合我的需要.我认为它可能比SegmentTree具有更平易近人的界面:

它也可以在Hackage上找到:http://hackage.haskell.org/package/IntervalMap