Making Int{Map,Set} polymorphic over the key type

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

Making Int{Map,Set} polymorphic over the key type

Georg Rudoy
Hi folks,

What do you think about making IntMap and IntSet polymorphic over the keys as long as the key type k is Coercible to Int?

The motivation is that oftentimes one needs to have a collection of newtype wrappers around Int, and then they have to either unpack/repack it around the relevant containers (which is not nice), or just use HashMap/HashSet (which is perhaps suboptimal).

If this is a direction the community might deem reasonable, I'd be happy to work on this and make a PR to the containers repo (perhaps after discussing the specific details about naming, etc).

--
  Georg Rudoy

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

Re: Making Int{Map,Set} polymorphic over the key type

Carter Schonwald
Off hand that seems like it’d break every single piece of code that uses those data structures today or at the very least possibly weaken type inference in some cases. 

Or maybe I’m over thinking things. 

I do think it’d be super to experiment with that as a child package so we can all try it out and see how the ux compares vs the usual approaches people do today


One possible gotcha / law that would need to be true for such new types is that the Ord and Eq instanced would have to be the same as INT.  AT least for some parts of the container api.  

On Sat, Jun 29, 2019 at 12:46 PM Georg Rudoy <[hidden email]> wrote:
Hi folks,

What do you think about making IntMap and IntSet polymorphic over the keys as long as the key type k is Coercible to Int?

The motivation is that oftentimes one needs to have a collection of newtype wrappers around Int, and then they have to either unpack/repack it around the relevant containers (which is not nice), or just use HashMap/HashSet (which is perhaps suboptimal).

If this is a direction the community might deem reasonable, I'd be happy to work on this and make a PR to the containers repo (perhaps after discussing the specific details about naming, etc).


--
  Georg Rudoy
_______________________________________________
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: Making Int{Map,Set} polymorphic over the key type

Henning Thielemann
In reply to this post by Georg Rudoy

On Sat, 29 Jun 2019, Georg Rudoy wrote:

> The motivation is that oftentimes one needs to have a collection of
> newtype wrappers around Int, and then they have to either unpack/repack
> it around the relevant containers (which is not nice), or just use
> HashMap/HashSet (which is perhaps suboptimal).

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

Re: Making Int{Map,Set} polymorphic over the key type

Georg Rudoy
In reply to this post by Carter Schonwald
сб, 29 июн. 2019 г. в 12:57, Carter Schonwald <[hidden email]>:
> Off hand that seems like it’d break every single piece of code that uses those data structures today or at the very least possibly weaken type inference in some cases.

Even if the change would be (disregarding the specific naming) to
change `IntSet` to `IntSetPoly k` and have `type IntSet = IntSetPoly
Int`? I don't have much experience reasoning about this, but looks
like it shouldn't really break much.

> I do think it’d be super to experiment with that as a child package so we can all try it out and see how the ux compares vs the usual approaches people do today

More on formalities, should it be a fork or a separate package with
just intmap/intset or something else?

> One possible gotcha / law that would need to be true for such new types is that the Ord and Eq instanced would have to be the same as INT.  AT least for some parts of the container api.

Great catch! I haven't thought about that.

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

Re: Making Int{Map,Set} polymorphic over the key type

Georg Rudoy
In reply to this post by Henning Thielemann
сб, 29 июн. 2019 г. в 13:01, Henning Thielemann <[hidden email]>:
> There is already the enummapset package.

Isn't it using fromEnum/toEnum under the hood, which might have bigger
performance penalty than `coerce`?

On the other hand, sure, the original suggestion can also be made as a
separate library wrapping IntMap/IntSet and all the calls to coerce.
I'm happy with that approach too.

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

Re: Making Int{Map,Set} polymorphic over the key type

Henning Thielemann

On Sat, 29 Jun 2019, Georg Rudoy wrote:

> сб, 29 июн. 2019 г. в 13:01, Henning Thielemann <[hidden email]>:
>> There is already the enummapset package.
>
> Isn't it using fromEnum/toEnum under the hood, which might have bigger
> performance penalty than `coerce`?

Right. However, I am using the package mostly for tasks where I do a lot
of 'union' and 'intersection' where there is no need to convert individual
elements. I only initialize sets with say, EnumSet.fromList, do a lot of
'union', 'intersection', 'difference', that is, simple bit field
operations, and then fetch the results with EnumSet.toAscList.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Making Int{Map,Set} polymorphic over the key type

David Feuer
In reply to this post by Georg Rudoy
toEnum and fromEnum will be coercions for the types you're talking about anyway.

On Sat, Jun 29, 2019, 1:06 PM Georg Rudoy <[hidden email]> wrote:
сб, 29 июн. 2019 г. в 13:01, Henning Thielemann <[hidden email]>:
> There is already the enummapset package.

Isn't it using fromEnum/toEnum under the hood, which might have bigger
performance penalty than `coerce`?

On the other hand, sure, the original suggestion can also be made as a
separate library wrapping IntMap/IntSet and all the calls to coerce.
I'm happy with that approach too.

--
  Georg Rudoy
_______________________________________________
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: Making Int{Map,Set} polymorphic over the key type

Carter Schonwald
In reply to this post by Georg Rudoy
make it a tiny little library thats its own! :) 

yeah, you'd probably want there to be Eq respecting Coercions flavor and the Ord respecting flavor

On Sat, Jun 29, 2019 at 1:04 PM Georg Rudoy <[hidden email]> wrote:
сб, 29 июн. 2019 г. в 12:57, Carter Schonwald <[hidden email]>:
> Off hand that seems like it’d break every single piece of code that uses those data structures today or at the very least possibly weaken type inference in some cases.

Even if the change would be (disregarding the specific naming) to
change `IntSet` to `IntSetPoly k` and have `type IntSet = IntSetPoly
Int`? I don't have much experience reasoning about this, but looks
like it shouldn't really break much.

> I do think it’d be super to experiment with that as a child package so we can all try it out and see how the ux compares vs the usual approaches people do today

More on formalities, should it be a fork or a separate package with
just intmap/intset or something else?

> One possible gotcha / law that would need to be true for such new types is that the Ord and Eq instanced would have to be the same as INT.  AT least for some parts of the container api.

Great catch! I haven't thought about that.

--
  Georg Rudoy

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