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.