11

是否有一个 Haskell 库可以让我拥有从范围到值的映射?(最好有点效率。)

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

3 回答 3

8

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

https://www.chr-breitkopf.de/comp/IntervalMap/index.html

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

于 2011-12-13T22:28:26.950 回答
7

也许rangemin图书馆做你想做的事?

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

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

它将映射拆分为小于/大于给定键的键的子图。这可用于某些类型的范围搜索。

于 2010-10-08T19:27:03.737 回答
7

此任务称为对一组间隔的 stabbing 查询。一种有效的数据结构称为(一维)段树

SegmentTree提供了这种数据结构的实现,但不幸的是我不知道如何使用它。(我觉得这个包的接口没有提供正确的抽象级别。)

于 2010-10-08T22:18:40.950 回答