Re: Feedback request: priority queues in containers
I'm not willing to do this sort of typeclass wrapper thing, primarily because nothing else in containers does -- even though we might have a Mapping type class that handles both IntMap and Map, we don't. I'm inclined to let that design choice stand, as far as containers is concerned. It would make perfect sense to write a new package with such a type class and offering instances for the containers priority queue implementations, but I prefer to stick with the style that containers already seems to use -- that is, exporting separate modules without a unifying type class, but with nearly-identical method signatures. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Tue, Mar 16, 2010 at 11:10 AM, Tyson Whitehead <twhitehead@gmail.com>wrote:
On March 16, 2010 09:29:06 Louis Wasserman wrote:
I'd like to request some more feedback on the proposed<http://hackage.haskell.org/trac/ghc/ticket/3909>implementation for priority queues in containers. Mostly, I feel like adding a new module to containers should be contentious, and there hasn't been as much griping or contention as I expected. The silence is feeling kind of eerie!
Not sure if this is an appropriate question at all as I haven't looked at the code, but would it be possible to put any primary functionality into a class.
I'm thinking something along the lines of how the vector code works. This allows you to use all the higher-order functions (i.e., those implemented using the primary functions) on a different underlying implementation.
I've found this particularly useful in wrapping Perl data types. For the Perl array, all I had to do was write an class instance for the vector module, and I have all these higher-order functions I could use from existing code.
It would be very nice to have had something similar to do for the hash tables. Even to just provide a "native haskell" immutable look into the data so Haskell code can extract the components it needs with standard functions.
Cheers! -Tyson
PS: I'm still working on the wrapping, so I might change my mind as to how useful this really is, but thought I should throw it out there.
Hi, I second that choice. There have been some attempts at using type classes, notably the Edison library, but it never got widespread. So I would follow the current containers design. Milan
I'm not willing to do this sort of typeclass wrapper thing, primarily because nothing else in containers does -- even though we might have a Mapping type class that handles both IntMap and Map, we don't.
I'm inclined to let that design choice stand, as far as containers is concerned. It would make perfect sense to write a new package with such a type class and offering instances for the containers priority queue implementations, but I prefer to stick with the style that containers already seems to use -- that is, exporting separate modules without a unifying type class, but with nearly-identical method signatures.
Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
On Tue, Mar 16, 2010 at 11:10 AM, Tyson Whitehead <twhitehead@gmail.com>wrote:
On March 16, 2010 09:29:06 Louis Wasserman wrote:
I'd like to request some more feedback on the proposed<http://hackage.haskell.org/trac/ghc/ticket/3909>implementation for priority queues in containers. Mostly, I feel like adding a new module to containers should be contentious, and there hasn't been as much griping or contention as I expected. The silence is feeling kind of eerie!
Not sure if this is an appropriate question at all as I haven't looked at the code, but would it be possible to put any primary functionality into a class.
I'm thinking something along the lines of how the vector code works. This allows you to use all the higher-order functions (i.e., those implemented using the primary functions) on a different underlying implementation.
I've found this particularly useful in wrapping Perl data types. For the Perl array, all I had to do was write an class instance for the vector module, and I have all these higher-order functions I could use from existing code.
It would be very nice to have had something similar to do for the hash tables. Even to just provide a "native haskell" immutable look into the data so Haskell code can extract the components it needs with standard functions.
Cheers! -Tyson
PS: I'm still working on the wrapping, so I might change my mind as to how useful this really is, but thought I should throw it out there.
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
Louis Wasserman wrote:
I'm not willing to do this sort of typeclass wrapper thing, primarily because nothing else in containers does -- even though we might have a Mapping type class that handles both IntMap and Map, we don't.
I'm inclined to let that design choice stand, as far as containers is concerned. It would make perfect sense to write a new package with such a type class and offering instances for the containers priority queue implementations, but I prefer to stick with the style that containers already seems to use -- that is, exporting separate modules without a unifying type class, but with nearly-identical method signatures.
Just an aside (and shameless plug ;-): Since the signatures overlap so much, it is in fact easy to wrap these modules into instances for many possible different type classes that one might consider using for containers --- I have a tool that mechanises this instance generation, available at: http://sqrl.mcmaster.ca/~kahl/Haskell/ModuleTools/ More about this in the forthcoming TFP 2009 proceedings paper: @InCollection{Kahl-2009_TFP, author = {Wolfram Kahl}, title = {Haskell Module Tools for Liberating Type Class Design}, crossref = {TFP2009}, pages = {129--144}, chapter = {9}, abstract = {Design of Haskell type class hierarchies for complex purposes, including for standard containers, is a non-trivial exercise, and evolution of such designs is additionally hampered by the large overhead of connecting to existing implementations. We systematically discuss this overhead, and propose a tool solution, implemented using the GHC API, to automate its generation.} } @Book{TFP2009, title = {Trends in Functional Programming, {TFP 2009}}, booktitle = {Trends in Functional Programming, {TFP 2009}}, year = 2010, editor = {Zolt\'an Horv{\'a}th and Vikt\'oia Zs{\'o}k and Peter Achten and Pieter Koopman}, address = {UK}, publisher = {Intellect}, note = {(In press)} } Wolfram
So, it is possible to break the invariants of your priority queue by
using fmap with a non-monotonic function, right? I see that it might be usefull to have such instances, sometimes. As it is not possible to hide instances, once they are definded, I'd propose to not offer those instances by default. Instead you could provide implementations of all the instance functions necessary to define this instances yourself. Or one could have a newtype wrapper around the priority queue for which instances of Function, Foldable, and Traversable are defined. This would allow to "activate" the nice instances on demand but to stay safe by default. Hmmmm. I suggest: - Functor and Traversable should be modified as you suggest, that is, we continue exporting mapMonotonic and traverseMonotonic, but don't export Functor or Traversable instances. - I'm still going to insist that we retain Foldable. The most important reason is that we don't lose any invariants as a result of a fold, and the second reason is that reexporting functions named "foldr" and "foldl" would be awkward. Making this change now. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
On March 16, 2010 13:24:32 kahl@cas.mcmaster.ca wrote:
Just an aside (and shameless plug ;-): Since the signatures overlap so much, it is in fact easy to wrap these modules into instances for many possible different type classes
Yes. I can see the preferred way would be to put the classes on top of the implementation, instead of the implementations on top of the classes. Cheers! -Tyson
On 17/03/2010, at 03:16, Louis Wasserman wrote:
I'm not willing to do this sort of typeclass wrapper thing, primarily because nothing else in containers does -- even though we might have a Mapping type class that handles both IntMap and Map, we don't.
I'm inclined to let that design choice stand, as far as containers is concerned. It would make perfect sense to write a new package with such a type class and offering instances for the containers priority queue implementations, but I prefer to stick with the style that containers already seems to use -- that is, exporting separate modules without a unifying type class, but with nearly-identical method signatures.
FWIW, vector does both. It defines most vector operations generically and then exports appropriate specialisations for each concrete vector type. I think this is the most flexible and convenient approach. I just wish Haskell had some kind of support for it. Roman
participants (5)
-
kahl＠cas.mcmaster.ca -
Louis Wasserman -
Milan Straka -
Roman Leshchinskiy -
Tyson Whitehead