Status of nubOrd (Proposal #2629)

[Bart Massey]

I need to know what the community wants me to do to close
out my proposal to add nubOrd to the standard libraries.
After ruling out a lot of marginal choices, I guess I see
three leading alternatives, all of which have negatives.
I'd love to have some feedback on these so I can start
thinking about other things.

1) Stick nubOrd' from my previous message into Data.List and
   call it a day.

   Advantages: Does no violence to the current library
   structure.  Provides a nubOrd that has O(n log m)
   asymptotic performance, and performs reasonably in
   practice with large m.

   Disadvantages: In the worst case, 5x performance is left
   on the floor.  Not particularly lazy: will work with
   infinite lists, but not with lists terminating in bottom;
   will only randomly work with lists containing bottom
   elements.  Quite ugly implementation.  No nubWith.

   My score: 2/5

2) Stick (non-StopList) nubWith in Data.List.  Stick nubOrd
   in Data.Set, implemented using nubWith.

   Advantages: Provides a highly efficient, fully lazy
   nubOrd.  Provides nubWith.  Reasonable implementation.

   Disadvantages:  Sticking nubOrd in Data.Set is weird.

   My score: 4/5

3) Leave well enough alone.

   Advantages: Full-on inherency.  Leaves no weird mess for
   future librarians.

   Disadvantages: No nubOrd means that folks keep writing
   nubSort and/or using nub in situations where it might
   fall over from poor performance.  Everyone having their
   own nub* implementations is a maintenance problem.  No
   nubWith means that it's more work to implement one's own
   nub*, making this problem worse.

   My score: 1/5

Comments gratefully received.  Based on them, I'll supersede
Proposal #2629 with the appropriate replacement Proposal.
My patch for (2) works fine with GHC 6.8.3.  I'm working on
compiling for current top-of-tree right now; should
have it shortly.

Thanks.

    Bart Massey
    bart <at> cs.pdx.edu