Status of nubOrd (Proposal #2629)
bart at cs.pdx.edu
Sat Oct 4 03:26:25 EDT 2008
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
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.
bart <at> cs.pdx.edu
More information about the Libraries