data-structures - HaskellRangeMapライブラリ

Question

範囲から値へのマップを作成できるHaskellライブラリはありますか？（ある程度効率的であることが望ましい。）

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

score 8 · Accepted Answer

既存のライブラリが私のニーズに合わなかったため、重複する間隔で検索するライブラリを作成しました。たとえばSegmentTreeよりも親しみやすいインターフェースがあると思います。

score 7 · Accepted Answer

おそらく、rangeminライブラリはあなたが望むことをしますか？

古き良きData.Map（そしてそのより効率的なData.IntMapいとこ）には機能があります

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

これは、マップを特定のキーよりも小さい/大きいキーのサブマップに分割します。これは、特定の種類の範囲検索に使用できます。

score 7 · Accepted Answer

このタスクは、一連の間隔での刺し傷クエリと呼ばれます。そのための効率的なデータ構造は、（1次元）セグメントツリーと呼ばれます。

SegmentTreeパッケージは、このデータ構造の実装を提供しますが、残念ながら、その使用方法を理解できません。（このパッケージのインターフェースは、適切なレベルの抽象化を提供していないと思います。）

3 に答える 3