Haskell范围映射库

Question

有没有一个Haskell库可以让我拥有从范围到值的Map？（最好是相对高效的）

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

- mrueg

Answer 1

我写了一个用于搜索重叠区间的库，因为现有的库不符合我的需求。我认为它可能比例如SegmentTree更易使用： https://www.chr-breitkopf.de/comp/IntervalMap/index.html 它也可以在Hackage上获得： https://hackage.haskell.org/package/IntervalMap

- Chris

Answer 2

也许rangemin库可以满足你的需求？

经典的Data.Map（以及效率更高的Data.IntMap）有一个函数。

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

这个功能将一个地图分成小的子地图，其中键小于/大于给定的键。这可以用于某些类型的范围搜索。

- keegan

---

是的，Data.Map在这里确实很有用。我已经成功地将其用于网络消息的“最接近地址”类型路由。minView和maxView以及它们的*WithKeys同类也很有用。 - Thomas M. DuBuisson

如果适用的话，比如说lookupLE和其他新的方法，对于这个目的来说更加高效，因为它们不需要构建新的树。 - dfeuer

Answer 3

这项任务称为对一组区间进行刺探查询。用于此目的的高效数据结构被称为（一维）线段树。 SegmentTree包提供了这种数据结构的实现，但不幸的是我无法弄清如何使用它。（我觉得这个包的接口没有提供正确的抽象层次。）

- Tsuyoshi Ito

---

我总是喜欢第一次听到数据结构的时候。非常酷。 - Tikhon Jelvis