Data.Ord and Heaps

[Ross Paterson]

[redirecting to libraries]

On Mon, Feb 04, 2008 at 01:09:00PM +0100, Stephan Friedrichs wrote:
> apfelmus at 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.