Data.Map: Enumerating ordered subset of keys

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Data.Map: Enumerating ordered subset of keys

Jared Updike
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

Jared Updike
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

anymane
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

Svein Ove Aas
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

Evan Laforge
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

Jared Updike
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

Jared Updike
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

Jared Updike
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