<div dir="auto">I am convinced that we should add<div dir="auto"><br></div><div dir="auto">ordNub :: Ord a => [a] -> [a]</div><div dir="auto">ordNubOn :: Ord b => (a -> b) -> [a] -> [b]</div><div dir="auto">intNub :: [Int] -> [Int]</div><div dir="auto">intNubOn :: (a -> Int) -> [a] -> [a]</div><div dir="auto"><br></div><div dir="auto">And because nub preserves non-emptiness, I believe we should also offer</div><div dir="auto"><br></div><div dir="auto"><div dir="auto" style="font-family:sans-serif">ordNub1 :: Ord a => NonEmpty a -> NonEmpty a</div><div dir="auto" style="font-family:sans-serif">ordNubOn1 :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty a</div><div dir="auto" style="font-family:sans-serif">intNub1 :: NonEmpty Int -> NonEmpty Int</div><div dir="auto" style="font-family:sans-serif">intNubOn1 :: (a -> Int) -> NonEmpty a -> NonEmpty a</div><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">I imagine we should also add these operations for Data.Sequence.Seq. </div></div><div dir="auto"><br></div><div dir="auto">I'm not yet convinced that we should add</div><div dir="auto"><br></div><div dir="auto">ordNubBy :: (a -> a -> Ordering) -> [a] -> [a]</div><div dir="auto"><br></div><div dir="auto">but I'm open to further discussion of that question. My main concern is that the properties of the comparison argument require careful documentation. In its favor, using it improperly cannot *expose* a broken Set to later operations.</div><div dir="auto"><br></div><div dir="auto">I would very much like to hear further bikeshedding around names and namespaces.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Oct 16, 2017 6:18 PM, "Gershom B" <<a href="mailto:gershomb@gmail.com">gershomb@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">There have been many discussions over the years about adding an<br>
efficient order preserving nub somewhere to our core libraries. It<br>
always comes down to the same issue: an efficient nub wants to be<br>
backed by an efficient `Set`, but the API of the `nub` itself doesn't<br>
make reference to any other data structures besides lists. So it feels<br>
a bit conceptually strange to put an efficient nub anywhere besides<br>
`Data.List` even though it can't go there without inverting our<br>
dependency tree in a weird way or inlining an efficient set<br>
implementation into the middle of it.<br>
<br>
Nonetheless, the convenience of having a good `nub` lying around in a<br>
core library is undeniable, and after writing the "usual" one in my<br>
code for the zillionth time, I decided to raise an issue about it:<br>
<br>
<a href="https://github.com/haskell/containers/issues/439" rel="noreferrer" target="_blank">https://github.com/haskell/<wbr>containers/issues/439</a><br>
<br>
I was promptly directed here to make a proper proposal.<br>
<br>
So, here:<br>
<br>
1) I propose two new functions,<br>
<br>
`ordNub` and `intNub`<br>
<br>
with the standard implementation (from <a href="https://github.com/nh2/haskell-ordnub" rel="noreferrer" target="_blank">https://github.com/nh2/<wbr>haskell-ordnub</a>):<br>
<br>
import qualified Data.Set as Set<br>
<br>
ordNub :: (Ord a) => [a] -> [a]<br>
ordNub l = go Set.empty l<br>
  where<br>
    go _ [] = []<br>
    go s (x:xs) = if x `Set.member` s then go s xs<br>
                                      else x : go (Set.insert x s) xs<br>
<br>
and the same implementation, but specialized to `Int` and using `IntSet`s.<br>
<br>
The rationale for the names is that the former has a long history of<br>
use in folklore, and the latter is the obvious specialization of it.<br>
<br>
2) I propose these functions be added to a new module in the<br>
`containers` library: `Data.Containers.ListUtils`. This can also<br>
potentially in the future add efficient list intersection, etc. as<br>
documented on the above reference link.<br>
<br>
The rationale for the new module is that it can provide a meaningful<br>
home for such functions which operate on lists, but require other data<br>
structures to be implemented efficiently...<br>
<br>
Discussion period: 2 weeks.<br>
<br>
--Gershom<br>
______________________________<wbr>_________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/libraries</a><br>
</blockquote></div></div>