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

[David Feuer]

Yes, a custom-built fold would be a little faster in general, and
significantly faster if the range only included a few elements. The
challenge is that there are lots of such functions we could add, and it's
not clear which would pay for their API clutter. Someone might want any
combination of including and excluding each endpoint, with (at least) all
the methods of Foldable and also a monomorphic traverse-like function.

On Sun, Mar 15, 2020, 7:21 AM Compl Yue via Haskell-Cafe <
haskell-cafe at haskell.org> wrote:

> Hello,
>
> I have a question regarding 'Data.Map' api, filed an issue
> https://github.com/haskell/containers/issues/708
>
> 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 ?
>
>
> Thanks,
>
> Compl
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20200315/dd265120/attachment.html>