Y a-t-il une bibliothèque de haskell qui me permet d'avoir une carte des gammes à des valeurs? (Préférable quelque peu efficace.)
let myRangeMap = RangeMap [(range 1 3, "foo"),(range 2 7, "bar"),(range 9 12, "baz")] in rangeValues 2 ==> ["foo","bar"]
3 Réponses :
Peut-être le Rangemin bibliothèque fait ce que vous voulez?
Bon vieux qui divise une carte dans les sources de clés inférieures à / supérieures à une clé donnée. Ceci peut être utilisé pour certains types de recherche de plage. data.map (et son data.intMap plus efficace.IntMap cousin) a une fonction
Oui, Data.Map est certainement utile ici. J'ai utilisé cela très avec succès pour "l'adresse la plus proche de" type de routage des messages réseau. Le MinView et MaxView avec leur * Les cousins sont également utiles.
lookupple et amis (qui sont plus récents que cette réponse) sont plus efficaces à cet effet, le cas échéant, car ils n'ont pas besoin de construire de nouveaux arbres.
Cette tâche s'appelle une requête de poignardage sur un ensemble d'intervalles. Une structure de données efficace pour elle est appelée (un dimensionnement) arbre de segment .
the package Segmenttree fournit une implémentation de cette structure de données, mais malheureusement, je ne peux pas comprendre comment pour l'utiliser. (Je pense que l'interface de ce paquet ne fournit pas le niveau d'abstraction appropriée.)
J'adore toujours entendre parler des structures de données pour la première fois. Très cool.
J'ai écrit une bibliothèque pour rechercher dans des intervalles qui se chevauchent car les personnes existantes ne correspondaient pas à mes besoins. Je pense que cela peut avoir une interface plus accessible que par exemple segmenttreee:
https://www.chr-breitkopf.de/comp/intervalmap /index.html
Il est également disponible sur Hackage: https://hackage.hakell.org/package/intervalmap - a>