Proposal: Add splitL and splitR to container’s Map APIs

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

Proposal: Add splitL and splitR to container’s Map APIs

Joachim Breitner-2
Hi,

I regularly find myself in the need of splitting a map into two maps.
For that we currently have these two functions:

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

Usually, split is useless to me because information (the element right
on the border) gets lost. splitLookup preserves the information, but
often I want the element at the border to simply be in one of the two
output maps. So I would like to see

splitL :: Ord k => k -> Map k a -> (Map k a, Map k a)
splitR :: Ord k => k -> Map k a -> (Map k a, Map k a)

with these properties

uncurry union (splitL k m) == m
uncurry union (splitR k m) == m
all (<= k) (keys (fst (splitL k m))
all (> k)  (keys (snd (splitL k m))
all (< k)  (keys (fst (splitR k m))
all (>= k) (keys (snd (splitR k m))

These new functions should be added to Data.Map, Data.IntMap (in both
variatans each) and, for consistency, Data.Set.

Alternative names (in correspondence with Data.Set.lookup{LT,LE,GT,TE})
would be splitLE (instead of splitL) and splitLT (instead of splitR).

Corresponding issue: https://github.com/haskell/containers/issues/387
Discussion period:   2 weeks (until Feb 14).

Greetings,
Joachim

--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Add splitL and splitR to container’s Map APIs

David Feuer
We recently added

spanAntitone :: (k -> Bool) -> Map k a -> (Map k a, Map k a)

I believe that should get you all the logarithmic splits you want of this type. The only question is whether we should add the simpler proposed functions for convenience.


On Jan 31, 2017 2:45 PM, "Joachim Breitner" <[hidden email]> wrote:
Hi,

I regularly find myself in the need of splitting a map into two maps.
For that we currently have these two functions:

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

Usually, split is useless to me because information (the element right
on the border) gets lost. splitLookup preserves the information, but
often I want the element at the border to simply be in one of the two
output maps. So I would like to see

splitL :: Ord k => k -> Map k a -> (Map k a, Map k a)
splitR :: Ord k => k -> Map k a -> (Map k a, Map k a)

with these properties

uncurry union (splitL k m) == m
uncurry union (splitR k m) == m
all (<= k) (keys (fst (splitL k m))
all (> k)  (keys (snd (splitL k m))
all (< k)  (keys (fst (splitR k m))
all (>= k) (keys (snd (splitR k m))

These new functions should be added to Data.Map, Data.IntMap (in both
variatans each) and, for consistency, Data.Set.

Alternative names (in correspondence with Data.Set.lookup{LT,LE,GT,TE})
would be splitLE (instead of splitL) and splitLT (instead of splitR).

Corresponding issue: https://github.com/haskell/containers/issues/387
Discussion period:   2 weeks (until Feb 14).

Greetings,
Joachim

--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Add splitL and splitR to container’s Map APIs

Joachim Breitner-2
Hi,

good point. I am on an older version, so I did not see that function
yet.


Indeed that function would nicely solve my use case, and

    spanAntitone (<=k)

isn’t much longer than my proposed

    spanLE k


The proposal still stands for the question of convenience, but the need
is much less now.

Greetings,
Joachim

Am Dienstag, den 31.01.2017, 14:54 -0500 schrieb David Feuer:

> We recently added
>
> spanAntitone :: (k -> Bool) -> Map k a -> (Map k a, Map k a)
>
> I believe that should get you all the logarithmic splits you want of
> this type. The only question is whether we should add the simpler
> proposed functions for convenience.
>
>
> On Jan 31, 2017 2:45 PM, "Joachim Breitner" <[hidden email]
> > wrote:
> Hi,
>
> I regularly find myself in the need of splitting a map into two maps.
> For that we currently have these two functions:
>
> split       :: Ord k => k -> Map k a -> (Map k a, Map k a)
> splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a) 
>
> Usually, split is useless to me because information (the element
> right
> on the border) gets lost. splitLookup preserves the information, but
> often I want the element at the border to simply be in one of the two
> output maps. So I would like to see
>
> splitL :: Ord k => k -> Map k a -> (Map k a, Map k a)
> splitR :: Ord k => k -> Map k a -> (Map k a, Map k a)
>
> with these properties
>
> uncurry union (splitL k m) == m
> uncurry union (splitR k m) == m
> all (<= k) (keys (fst (splitL k m))
> all (> k)  (keys (snd (splitL k m))
> all (< k)  (keys (fst (splitR k m))
> all (>= k) (keys (snd (splitR k m))
>
> These new functions should be added to Data.Map, Data.IntMap (in both
> variatans each) and, for consistency, Data.Set.
>
> Alternative names (in correspondence with
> Data.Set.lookup{LT,LE,GT,TE})
> would be splitLE (instead of splitL) and splitLT (instead of splitR).
>
> Corresponding issue: https://github.com/haskell/containers/issues/387
> Discussion period:   2 weeks (until Feb 14).
>
> Greetings,
> Joachim
>
> --
> Joachim “nomeata” Breitner
>   [hidden email]https://www.joachim-breitner.de/
>   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>   Debian Developer: [hidden email]
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Add splitL and splitR to container’s Map APIs

David Feuer
spanAntitone is also a bit more general than any "split at" could be.
For example,

spanAntitone (\ (x :: Rational) -> x^3 < 5)

separates a map into keys less than and greater than the cube root of 5.

On Tue, Jan 31, 2017 at 3:05 PM, Joachim Breitner
<[hidden email]> wrote:

> Hi,
>
> good point. I am on an older version, so I did not see that function
> yet.
>
>
> Indeed that function would nicely solve my use case, and
>
>     spanAntitone (<=k)
>
> isn’t much longer than my proposed
>
>     spanLE k
>
>
> The proposal still stands for the question of convenience, but the need
> is much less now.
>
> Greetings,
> Joachim
>
> Am Dienstag, den 31.01.2017, 14:54 -0500 schrieb David Feuer:
>> We recently added
>>
>> spanAntitone :: (k -> Bool) -> Map k a -> (Map k a, Map k a)
>>
>> I believe that should get you all the logarithmic splits you want of
>> this type. The only question is whether we should add the simpler
>> proposed functions for convenience.
>>
>>
>> On Jan 31, 2017 2:45 PM, "Joachim Breitner" <[hidden email]
>> > wrote:
>> Hi,
>>
>> I regularly find myself in the need of splitting a map into two maps.
>> For that we currently have these two functions:
>>
>> split       :: Ord k => k -> Map k a -> (Map k a, Map k a)
>> splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
>>
>> Usually, split is useless to me because information (the element
>> right
>> on the border) gets lost. splitLookup preserves the information, but
>> often I want the element at the border to simply be in one of the two
>> output maps. So I would like to see
>>
>> splitL :: Ord k => k -> Map k a -> (Map k a, Map k a)
>> splitR :: Ord k => k -> Map k a -> (Map k a, Map k a)
>>
>> with these properties
>>
>> uncurry union (splitL k m) == m
>> uncurry union (splitR k m) == m
>> all (<= k) (keys (fst (splitL k m))
>> all (> k)  (keys (snd (splitL k m))
>> all (< k)  (keys (fst (splitR k m))
>> all (>= k) (keys (snd (splitR k m))
>>
>> These new functions should be added to Data.Map, Data.IntMap (in both
>> variatans each) and, for consistency, Data.Set.
>>
>> Alternative names (in correspondence with
>> Data.Set.lookup{LT,LE,GT,TE})
>> would be splitLE (instead of splitL) and splitLT (instead of splitR).
>>
>> Corresponding issue: https://github.com/haskell/containers/issues/387
>> Discussion period:   2 weeks (until Feb 14).
>>
>> Greetings,
>> Joachim
>>
>> --
>> Joachim “nomeata” Breitner
>>   [hidden email]https://www.joachim-breitner.de/
>>   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>>   Debian Developer: [hidden email]
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> --
> Joachim “nomeata” Breitner
>   [hidden email]https://www.joachim-breitner.de/
>   XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
>   Debian Developer: [hidden email]
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Add splitL and splitR to container’s Map APIs

Joachim Breitner-2
In reply to this post by Joachim Breitner-2
Hi,

Am Dienstag, den 31.01.2017, 14:44 -0500 schrieb Joachim Breitner:
> splitL :: Ord k => k -> Map k a -> (Map k a, Map k a)
> splitR :: Ord k => k -> Map k a -> (Map k a, Map k a)
>
> Corresponding issue: https://github.com/haskell/containers/issues/387
> Discussion period:   2 weeks (until Feb 14).

the discussion showed the existence of spanAntitone, which is better,
and no further interest was raised in this. I therefore conclude the
discussion period with “no, we ain’t gonna take it”

Greetings,
Joachim

--
Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (849 bytes) Download Attachment