Esiste una libreria Haskell che mi consente di avere una mappa da intervalli a valori? (Preferibile un po 'efficiente.)Libreria Haskell Range Map
let myRangeMap = RangeMap [(range 1 3, "foo"),(range 2 7, "bar"),(range 9 12, "baz")]
in rangeValues 2
==> ["foo","bar"]
Questa attività è denominata query di accoltellamento su un insieme di intervalli. Una struttura dati efficiente per questo è chiamata (unidimensionale) segment tree.
Il SegmentTree package fornisce un'implementazione di questa struttura dati, ma sfortunatamente non riesco a capire come usarlo. (Sento che l'interfaccia di questo pacchetto non fornisce il giusto livello di astrazione.)
Forse il rangemin library fa ciò che vuoi?
Buon vecchio Data.Map (e il suo più efficiente Data.IntMap cugino) ha una funzione
splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
che si divide una mappa in sottomappe di chiavi inferiore/superiore a una determinata chiave. Questo può essere usato per determinati tipi di ricerca di intervalli.
Sì, Data.Map certamente è utile qui. Ho usato questo abbastanza con successo per il routing tipo "indirizzo più vicino a" dei messaggi di rete. anche i 'minView' e' maxView' insieme ai loro cugini '* WithKeys' sono utili. –
Ho scritto una libreria da cercare in intervalli sovrapposti, perché quelli esistenti non corrispondevano alle mie esigenze. Penso che possa avere un'interfaccia più accessibile rispetto ad esempio SegmentTree:
http://www.chr-breitkopf.de/comp/IntervalMap/index.html
E 'disponibile anche su Hackage: http://hackage.haskell.org/package/IntervalMap
Mi piace sempre ascoltare le strutture dati per la prima volta. Molto bello –