Haskell Range Harita kütüphanesi

Question

Haritadan menzile değerler almamı sağlayan bir Haskell kütüphanesi var mı? (Tercih biraz verimli.)

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

Answer 1

Bu görev, bir dizi aralıkta bir kesme sorgusu olarak adlandırılır. Bunun için verimli bir veri yapısı (tek boyutlu) segment tree olarak adlandırılır.

SegmentTree package, bu veri yapısının bir uygulamasını sağlar, ancak maalesef bunu nasıl kullanacağımı anlayamıyorum. (Bu paketin arayüzünün doğru soyutlamayı sağlamadığını hissediyorum.)

Answer 2

Belki rangemin library sen ne istiyor ki?

İyi eski Data.Map (ve daha verimli Data.IntMap kuzeni) bir fonksiyonu belirli bir anahtar daha büyük tuşların submaps içine bir harita daha az/böler

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

sahiptir. Bu, belirli aralıktaki aramalarda kullanılabilir.

Answer 3

Çakışan aralıklarla arama yapmak için bir kitaplık yazdım çünkü mevcut olanlar ihtiyaçlarıma uymuyordu. Bunun örneği SegmentTree için daha cana arayüze sahip olabilir düşünüyorum:

http://www.chr-breitkopf.de/comp/IntervalMap/index.html

O Hackage üzerinde de kullanılabilir: http://hackage.haskell.org/package/IntervalMap