[redirecting to libraries] On Mon, Feb 04, 2008 at 01:09:00PM +0100, Stephan Friedrichs wrote:
apfelmus@quantentunnel.de wrote:
[newtype Ord a => Reverse a = Reverse { unReverse :: a }]
Yes. I mean "non-standard" in the software-reuse sense, i.e. Ord is for user-defined orderings and should be the only such mechanism in order to enable reuse. In fact, Data.Heap clearly shows that Data.Ord is currently missing functionality.
Ah, now I see. The entire ordering policy mechanism - no matter how it is going to be solved - belongs into Data.Ord and not in Data.Heap. As soon as Data.Ord provides a solution, I'll use it in Data.Heap.
Unfortunately the Data.Ord module is constrained to use only Haskell 98 features, because it is used by all implementations. So it could include the above Reverse (also mentioned in the group-by HW paper), but not the various OrdPolicy proposals. They could go in a separate module, though. Off on a tangent: the containers package, which collects portable implementations of general purpose data structures, could use a good priority queue implementation. However it is also constrained to use only Haskell 98 features, which would rule out using policies. Also, using weight-biased leftist trees (Cho & Sahni, 1996) instead of Knuth's rank-biased leftist trees would offer O(1) size for free. And they come out slightly faster in my test runs.