Proposal: Tidy up and export PSQ from base

Edward Z. Yang ezyang at MIT.EDU
Mon May 2 01:58:37 CEST 2011

OK, to summarize the current discussion:

- It would be nice to have a general-purpose priority queue in containers.
  I'm not interested in this goal per se, but I do view it as the cleanest way
  to get what I want.

- The IO event manager, as a primary client of PSQ, is concerned
  about the following possible implications of moving PSQ entirely
  to containers:
    - As a general purpose interface, it would be more difficult to
      performance tune and/or specialize the queue for its application.
      (What a limitation of GHC Haskell! We should fix that :-)
    - Specialization on keys and priority values is necessary for good
      performance with the event manager.
    - There is a fear that if PSQ gets in containers, updating it will
      be much more difficult for the IO event manager.

First, a philosophical statement: I hate code duplication.  I'm already pretty
unhappy with the fact that base grew its own copy of IntMap, the only real
functional difference being that this IntMap appears to be strict in values.
It might be the only way to achieve other desirable properties (for example,
having IntMap in containers and not in base), but it makes me die a little

One reason why I'm so adamant about this is that each of these modules
contains nontrivial algorithmic content, and as recent events with
Data.Map have shown, it's still possible for us to have gotten it wrong
(and subtle fixes to be necessary).  Thus, any contributor who wants
to submit a performance improvement to IntMap also has to know that
base has its own private copy of IntMap.  That just seems poor.

Though, it seems I'm already too late to the party: GHC.Event.PSQ is
stolen from the PSQueue Hackage package, with some modifications (I
didn't realize this when I originally made my proposal).  So I hereby
amend my proposal:

    I propose we move PSQueue into containers, hereby putting it
    on even ground with IntMap.  Its notability for inclusion is hereby
    established by its use in the IO Event Manager and its projected
    use in Hoopl.

On a completely theoretical note, I wonder if there is a way to take
advantage of the fact that keys are integers to improve the PSQueue
structure, much in the same way IntMap improves on Map.


More information about the Libraries mailing list