[GHC] #3909: Priority queues in containers

[GHC]

#3909: Priority queues in containers
-------------------------------------------+--------------------------------
    Reporter:  LouisWasserman              |        Owner:  LouisWasserman
        Type:  feature request             |       Status:  assigned      
    Priority:  normal                      |    Milestone:                
   Component:  libraries (other)           |      Version:  6.12.1        
    Keywords:  containers, priority queue  |   Difficulty:                
          Os:  Unknown/Multiple            |     Testcase:                
Architecture:  Unknown/Multiple            |      Failure:  None/Unknown  
-------------------------------------------+--------------------------------

Comment(by LouisWasserman):

 Hmmmkay.

 I'm going to make my own vote for {{{Maybe (a, PQueue a)}}}, and change
 it, since we appear to be in charge...

 After doing my own experiments with lazy pairing heaps, I'm still not sure
 I'm willing to support lazy pairing heaps, again out of concern for the
 real-time-performance crowd.  The distinction is really the following:

 Binomial queues support amortized O(1) insertion, but worst-case O(log n).
 Pairing heaps support amortized O(log n) delete-min, but worst-case O(n).
 Okasaki doesn't debate worst-case performance.

 I'm convinced that this approach doesn't risk O(n^2) performance in a
 persistent context, now, which is a significant improvement, but I'm not
 fully convinced it's enough yet.

 Uploading my updated versions now.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:24>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler