# Data.Map: Enumerating ordered subset of keys

 Classic List Threaded
8 messages
Reply | Threaded
Open this post in threaded view
|

## Data.Map: Enumerating ordered subset of keys

 I would like to enumerate a subset of keys in a Map satisfying \ key >= key1 && key <= key2 but in the expected, reasonable amount of time (e.g. < O(log(n)) + O(m) for n total keys and m keys in the subset). (Or key > key1 and/or key < key2 or some such combination). Is there an appropriate idiom or combination of library functions to accomplish this, short of digging into the code for Data.Map and writing such a function for a forked version of Data.Map? For example I could try something like a Set.split of a Set.split of Map.keysSet of my original map, but will laziness magically do what I really want? which is to walk down the tree to key1 (or the nearest key > key1) and enumerate keys in order until key2 is reached? Data.Map almost looks like what I need if I can do this.   Jared. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Data.Map: Enumerating ordered subset of keys

 It looks like two "Map.split"s will do what I need except for allowing more exact testing of <= vs. < (since == elements are left out of both maps...?)   Jared. On 2/8/09, Jared Updike <[hidden email]> wrote: > I would like to enumerate a subset of keys in a Map satisfying \ key >  >= key1 && key <= key2 but in the expected, reasonable amount of time >  (e.g. < O(log(n)) + O(m) for n total keys and m keys in the subset). >  (Or key > key1 and/or key < key2 or some such combination). > >  Is there an appropriate idiom or combination of library functions to >  accomplish this, short of digging into the code for Data.Map and >  writing such a function for a forked version of Data.Map? > >  For example I could try something like a Set.split of a Set.split of >  Map.keysSet of my original map, but will laziness magically do what I >  really want? which is to walk down the tree to key1 (or the nearest >  key > key1) and enumerate keys in order until key2 is reached? > >  Data.Map almost looks like what I need if I can do this. > > >   Jared. > _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Re: Data.Map: Enumerating ordered subset of keys

 Maybe you want  Data.Map.partition (\key -> key >= key1 && key <= key2) map HTH, Anish On Sun, 08 Feb 2009 23:02:37 -0800, Jared Updike <[hidden email]> wrote: > It looks like two "Map.split"s will do what I need except for allowing > more exact testing of <= vs. < (since == elements are left out of both > maps...?) > >   Jared. > > On 2/8/09, Jared Updike <[hidden email]> wrote: >> I would like to enumerate a subset of keys in a Map satisfying \ key >>  >= key1 && key <= key2 but in the expected, reasonable amount of time >>  (e.g. < O(log(n)) + O(m) for n total keys and m keys in the subset). >>  (Or key > key1 and/or key < key2 or some such combination). >> >>  Is there an appropriate idiom or combination of library functions to >>  accomplish this, short of digging into the code for Data.Map and >>  writing such a function for a forked version of Data.Map? >> >>  For example I could try something like a Set.split of a Set.split of >>  Map.keysSet of my original map, but will laziness magically do what I >>  really want? which is to walk down the tree to key1 (or the nearest >>  key > key1) and enumerate keys in order until key2 is reached? >> >>  Data.Map almost looks like what I need if I can do this. >> >> >>   Jared. >> > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Re: Data.Map: Enumerating ordered subset of keys

 In reply to this post by Jared Updike On Mon, Feb 9, 2009 at 8:02 AM, Jared Updike <[hidden email]> wrote: > It looks like two "Map.split"s will do what I need except for allowing > more exact testing of <= vs. < (since == elements are left out of both > maps...?) > If your key is an instance of Enum, you can use succ/pred to work around that little problem. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Data.Map: Enumerating ordered subset of keys

 In reply to this post by Jared Updike On Mon, Feb 9, 2009 at 2:57 PM, Jared Updike <[hidden email]> wrote: > I would like to enumerate a subset of keys in a Map satisfying \ key >>= key1 && key <= key2 but in the expected, reasonable amount of time > (e.g. < O(log(n)) + O(m) for n total keys and m keys in the subset). > (Or key > key1 and/or key < key2 or some such combination). > > Is there an appropriate idiom or combination of library functions to > accomplish this, short of digging into the code for Data.Map and > writing such a function for a forked version of Data.Map? I have a little util library with various map functions.  'within' is almost what you want, except it's half-open.  You can make an inclusive one by pulling the lowest element off the above map. I'm also curious if there's a better way to do this... -- | Like Map.split, except include a matched key in the above map. split_map :: (Ord k) => k -> Map.Map k a -> (Map.Map k a, Map.Map k a) split_map k fm = (pre, post')     where     (pre, at, post) = Map.splitLookup k fm     post' = maybe post (\v -> Map.insert k v post) at -- | Split the map into the maps below, within, and above the given range. -- @low@ to @high@ is half-open, as usual. split3_map :: (Ord k) => k -> k -> Map.Map k a     -> (Map.Map k a, Map.Map k a, Map.Map k a) split3_map low high fm = (below, within, way_above)     where     (below, above) = split_map low fm     (within, way_above) = split_map high above within low high fm = let (_, m, _) = split3_map low high fm in m _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Re: Data.Map: Enumerating ordered subset of keys

 In reply to this post by Svein Ove Aas I had a similar thought. That will probably do the trick.   Jared. On 2/8/09, Svein Ove Aas <[hidden email]> wrote: > On Mon, Feb 9, 2009 at 8:02 AM, Jared Updike <[hidden email]> wrote: >  > It looks like two "Map.split"s will do what I need except for allowing >  > more exact testing of <= vs. < (since == elements are left out of both >  > maps...?) >  > > > If your key is an instance of Enum, you can use succ/pred to work >  around that little problem. > _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Re: Data.Map: Enumerating ordered subset of keys

 In reply to this post by anymane On 2/8/09, Anish Muttreja <[hidden email]> wrote: > Maybe you wantData.Map.partition (\key -> key >= key1 && key <= key2) map This will return what I want, but partition is O(n) and touches all the keys, so if I had a million keys and only 2 of them matched the key1..key2 range, it would still visit all of them before it enumerated the ones that satisify the predicate. I don't believe laziness would help here. >  HTH, >  Anish > > >  On Sun, 08 Feb 2009 23:02:37 -0800, Jared Updike <[hidden email]> wrote: > > > > > > It looks like two "Map.split"s will do what I need except for allowing > > more exact testing of <= vs. < (since == elements are left out of both > > maps...?) > > > >  Jared. > > > > On 2/8/09, Jared Updike <[hidden email]> wrote: > > > > > I would like to enumerate a subset of keys in a Map satisfying \ key > > >  >= key1 && key <= key2 but in the expected, reasonable amount of time > > >  (e.g. < O(log(n)) + O(m) for n total keys and m keys in the subset). > > >  (Or key > key1 and/or key < key2 or some such combination). > > > > > >  Is there an appropriate idiom or combination of library functions to > > >  accomplish this, short of digging into the code for Data.Map and > > >  writing such a function for a forked version of Data.Map? > > > > > >  For example I could try something like a Set.split of a Set.split of > > >  Map.keysSet of my original map, but will laziness magically do what I > > >  really want? which is to walk down the tree to key1 (or the nearest > > >  key > key1) and enumerate keys in order until key2 is reached? > > > > > >  Data.Map almost looks like what I need if I can do this. > > > > > > > > >  Jared. > > > > > > > > _______________________________________________ > > Haskell-Cafe mailing list > > [hidden email] > > http://www.haskell.org/mailman/listinfo/haskell-cafe> > > > > > > _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Data.Map: Enumerating ordered subset of keys

 In reply to this post by Evan Laforge On 2/8/09, Evan Laforge <[hidden email]> wrote: > I have a little util library with various map functions.  'within' is >  almost what you want, except it's half-open.  You can make an >  inclusive one by pulling the lowest element off the above map. > >  I'm also curious if there's a better way to do this... > >  -- | Like Map.split, except include a matched key in the above map. >  split_map :: (Ord k) => k -> Map.Map k a -> (Map.Map k a, Map.Map k a) >  split_map k fm = (pre, post') >     where >     (pre, at, post) = Map.splitLookup k fm >     post' = maybe post (\v -> Map.insert k v post) at > >  -- | Split the map into the maps below, within, and above the given range. >  -- @low@ to @high@ is half-open, as usual. >  split3_map :: (Ord k) => k -> k -> Map.Map k a >     -> (Map.Map k a, Map.Map k a, Map.Map k a) >  split3_map low high fm = (below, within, way_above) >     where >     (below, above) = split_map low fm >     (within, way_above) = split_map high above > >  within low high fm = let (_, m, _) = split3_map low high fm in m This looks right to me (correct time complexity). It should do what I need. I will test it and see what I discover. Thanks,   Jared. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe