one PQueue datatype with type parameter for priority order

[amigalemming]

Currently you define MaxPQueue as wrapper around MinPQueue. I would prefer a general PQueue data type with a type parameter that chooses between the Min and Max variant.
That would save the wrapper code in Data.PQueue.Max and code duplication in custom utility functions.
I think it can still be Haskell 98 with definitions like these:

class Dir dir where dirCompare :: (Ord a) => dir -> a -> a -> Ordering
data Min = Min; instance Dir Min where dirCompare Min = compare
data Max = Max; instance Dir Max where dirCompare Max = flip compare

[lspitzner]

I think I understand what you have in mind there and although I cannot really imagine the advantage of this yet, in general I currently see no issues with this approach either - performance impact of the additional indirection should be insignificant and it should be possible to implement it in a backwards-compatible fashion (right? function signatures would change but that change would be nothing more than a constraint on the type argument that can be hidden behind an alias..).
(To clarify: I only consider the haskell98 route here.)

If this is correct and existing users won't be disturbed by such a change, I'll happily merge a PR. However I won't implement this myself.

Sorry for the late answer; It took me a moment to realize how the haskell98-route would work and how exactly it would change the interface.

[amigalemming]

On Thu, 2 Mar 2017, Lennart Spitzner wrote: I think I understand what you have in mind there and although I cannot really imagine the advantage of this yet, in general I currently see no issues with this approach either - performance impact of the additional indirection should be insignificant and it should be possible to implement it in a backwards-compatible fashion (right? function signatures would change but that change would be nothing more than a constraint on the type argument that can be hidden behind an alias..). (To clarify: I only consider the haskell98 route here.)

It is not completely backwards compatible because type class instances on the current types would become instances on type synonyms. That is, users would need to add FlexibleInstances, or better, they would merge their instances of Max and Min queues into unified instances.

[amigalemming]

On Thu, 2 Mar 2017, Lennart Spitzner wrote: If this is correct and existing users won't be disturbed by such a change, I'll happily merge a PR. However I won't implement this myself.

I think now that I can do it in a completely backwards-compatible way. However, I am nervous that there is no test-suite that can check whether the modified code is still correct and some warnings are disabled. E.g. name shadowing warnings are disabled certainly because (<=) is locally used for different kind of comparisons.

[lspitzner]

Yeah, I know. I never bothered to clean up the shadowing (I'd certainly have non-shadowing names consistently) and for the little changes I have made recently, I only did some basic manual testing, and checked that some reverse-dep that uses pqueue in a deterministic manner still had the same results. But I completely agree that this is not at all sufficient, especially with a larger redesign in mind.

Unfortunately I currently was planning on spending some time on a different open-source project, so I will not promise to work on these pqueue issues in the near future (sorry). If you have any changes to propose, I will make time to review them.

[amigalemming]

On Sun, 5 Mar 2017, Lennart Spitzner wrote: Yeah, I know. I never bothered to clean up the shadowing (I'd certainly have non-shadowing names consistently) and for the little changes I have made recently, I only did some basic manual testing, and checked that some reverse-dep that uses pqueue in a deterministic manner still had the same results. But I completely agree that this is not at all sufficient, especially with a larger redesign in mind.

The original darcs repository contained a test-suite named PQueueTests.hs. I'll try to turn that into a Cabal Test-Suite.

[lspitzner]

great!

[treeowl]

There is now a test suite, although more testing work remains to be done. I still don't understand the goal behind this ticket. Could you explain? Or give some examples of how doing it this way would make the implementation better? If not, I'd like to close it.