Proposal: priority queues in containers

[Isaac Dupree]

On 03/19/10 09:39, Louis Wasserman wrote:
> Yo,
>
>
>>   * I'm not comfortable with having two redundant modules, one for Min- and
>> one for MaxQueue

> I'm pretty sure there won't be a containers-compatible solution, certainly
> not a solution compatible with the style of containers as it's currently
> written

On 03/19/10 06:26, Ross Paterson wrote:
> If keys are separate, the two versions could be easily achieved using
> an inversion adaptor on Ord, which has been proposed before and would
> have many other uses.

I agree with Ross. We should add Data.Ord.Opposite, or whatever we 
decide to call it,
(newtype Opposite a = Opposite { getOpposite :: a } deriving (Eq, Show, 
...), and the obvious Ord instance.)

This works with Data.Map too.  Additionally I suggest, since folding a 
Map produces keys lowest-first, that we choose the same behavior for the 
priority queue.

On the other hand, separating the key and the value gives us the same 
Data.Map vs. Data.Set mess (which maybe is not a bad mess, but, it would 
suggest there should be two different PQ modules too, one with 
associated non-ordered data and the other with only the priorities).

-Isaac