Feedback request: priority queues in containers

Jean-Marie Gaillourdet jmg at gaillourdet.net
Tue Mar 16 13:17:59 EDT 2010


Hi,

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.

Best regards,
Jean-Marie


More information about the Glasgow-haskell-users mailing list