Gibt es eine Haskell-Bibliothek, die mir erlaubt, eine Karte von Bereichen zu Werten zu haben? (Bevorzugte etwas effizienter.)Haskell Range Map-Bibliothek
let myRangeMap = RangeMap [(range 1 3, "foo"),(range 2 7, "bar"),(range 9 12, "baz")]
in rangeValues 2
==> ["foo","bar"]
Diese Aufgabe wird als Stichprobenabfrage in einer Reihe von Intervallen bezeichnet. Eine effiziente Datenstruktur dafür nennt man (eindimensional) segment tree.
Die SegmentTree package bietet eine Implementierung dieser Datenstruktur, aber leider kann ich nicht herausfinden, wie man es benutzt. (Ich denke, dass die Schnittstelle dieses Pakets nicht die richtige Abstraktionsebene bietet.)
Vielleicht ist die rangemin library tut, was Sie wollen?
gute alte Data.Map (und seine effizienter Data.IntMap Cousin) eine Funktion
splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
, die eine Karte in Submaps der Schlüssel aufteilt kleiner/größer als ein gegebener Schlüssel. Dies kann für bestimmte Arten der Bereichssuche verwendet werden.
Ja, Data.Map sicherlich nützlich ist hier. Ich habe dies recht erfolgreich für das Routing von Netzwerknachrichten mit der "nächsten Adresse" verwendet. die 'minView' und' maxView' zusammen mit ihren '* WithKeys' Cousins sind ebenfalls nützlich. –
Ich habe eine Bibliothek geschrieben, um in überlappenden Intervallen zu suchen, weil die vorhandenen nicht meinen Anforderungen entsprachen. Ich denke, es kann eine mehr ansprechbar Schnittstelle haben als zum Beispiel SegmentTree:
http://www.chr-breitkopf.de/comp/IntervalMap/index.html
Es ist auch auf Hackage verfügbar: http://hackage.haskell.org/package/IntervalMap
Ich liebe es immer, zum ersten Mal von Datenstrukturen zu hören. Sehr cool. –