[Haskell-cafe] Data.Map - visiting tree nodes within a given key range ?

Compl Yue compl.yue at icloud.com
Sun Mar 15 11:20:43 UTC 2020


I have a question regarding 'Data.Map' api, filed an issue 

And may be I can ask here at the same time?

I'm not sure why|Data.Map|doesn't have a key range based visiting API, I 
figured out I can do it this way:

|indexKeyRange :: IndexKey -> IndexKey -> Map IndexKey Object -> 
[(IndexKey, Object)] indexKeyRange !minKey !maxKey = toList . 
takeWhileAntitone (<= maxKey) . dropWhileAntitone (< minKey) |

But wouldn't it save the computation needed to re-balance the 
intermediate tree generated ? Or that re-balancing can be optimized out 
actually ?

I am creating an in-memory graph database, using|Data.Map.Strict.Map|as 
business object indices with specified object attributes. The typical 
scenario will be querying a small number of entries by key range, out of 
possibly all business objects of a certain class globally, so the 
implementation above would work, but not reasonable by far as it seems.

I think a lazy list returned by mere node visiting (i.e. no new node 
creation) would satisfy my needs, or I missed something ?



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20200315/55e2c4f9/attachment.html>

More information about the Haskell-Cafe mailing list