Y a-t-il une bibliothèque Haskell qui me permet d'avoir une carte de plages à valeurs? (Préférable peu efficace.)Bibliothèque Haskell Range Map
let myRangeMap = RangeMap [(range 1 3, "foo"),(range 2 7, "bar"),(range 9 12, "baz")]
in rangeValues 2
==> ["foo","bar"]
Cette tâche est appelée une requête lancinante sur un ensemble d'intervalles. Une structure de données efficace est appelée (unidimensionnelle) segment tree.
Le SegmentTree package fournit une implémentation de cette structure de données, mais malheureusement je n'arrive pas à comprendre comment l'utiliser. (Je pense que l'interface de ce paquet ne fournit pas le bon niveau d'abstraction.)
Peut-être le rangemin library fait ce que vous voulez?
Bonne vieille Data.Map (et son cousin Data.IntMap plus efficace) a une fonction
splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
qui divise une carte en sous-cartes de clés moins/supérieure à une clé donnée. Cela peut être utilisé pour certains types de recherche de plage.
Oui, Data.Map est certainement utile ici. Je l'ai utilisé avec beaucoup de succès pour le routage de type "adresse la plus proche" des messages réseau. les 'minView' et' maxView' avec leurs cousins '* WithKeys' sont également utiles. –
J'ai écrit une bibliothèque pour rechercher dans les intervalles de chevauchement, parce que ceux qui existaient ne correspondaient pas à mes besoins. Je pense qu'il peut avoir une interface plus accessible que par exemple SegmentTree:
http://www.chr-breitkopf.de/comp/IntervalMap/index.html
Il est également disponible sur Hackage: http://hackage.haskell.org/package/IntervalMap
J'ai toujours aimé entendre parler des structures de données pour la première fois. Très sympa. –