Feedback request: priority queues in containers
jmg at gaillourdet.net
Tue Mar 16 13:17:59 EDT 2010
I think this is my first post to this list although I've been reading it
for a long time. So, please, be patient with me and my post.
On 03/16/2010 02:29 PM, Louis Wasserman wrote:
> * We offer Functor, Foldable, and Traversable instances that do not
> respect key ordering. All are linear time, but Functor and
> Traversable in particular assume the function is monotonic. The
> Foldable instance is a good way to access the elements of the
> priority queue in an unordered fashion. (We also export
> mapMonotonic and traverseMonotonic, and encourage the use of those
> functions instead of the Functor or Traversable instances.)
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.
More information about the Glasgow-haskell-users