<div dir="auto">nubOn :: Ord b => (a -> b) -> [a] -> [a],<div dir="auto">or the Foldable version, seem just a bit safer, but less convenient.<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Oct 17, 2017 2:09 AM, "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">Good point on the by variants. (And indeed this is a public forum).<br>
<br>
Those can be written without any fancy machinery, just keeping the<br>
`by` data in the set, in the straightforward way. I agree it makes<br>
sense to add them.<br>
<br>
-g<br>
<br>
<br>
On October 17, 2017 at 1:44:30 AM, Alex Rozenshteyn<br>
(<a href="mailto:rpglover64@gmail.com">rpglover64@gmail.com</a>) wrote:<br>
> (Forgive me if I shouldn't be posting on libraries@. I did a little<br>
> searching and couldn't determine if this list is supposed to be a public<br>
> forum or not)<br>
><br>
> > [D]o you have anything else you think should be stuck in the new module?<br>
><br>
> As a user, I would expect to find the `...By` variants in the same<br>
> location, but that precludes reusing `Set` without relying on complicated<br>
> machinery like `reflection`, doesn't it?<br>
><br>
> On Mon, Oct 16, 2017 at 3:45 PM David Feuer wrote:<br>
><br>
> > I would imagine<br>
> ><br>
> > ordNub :: (Foldable t, Ord a)<br>
> > => t a -> [a]<br>
> > ordNub xs = foldr go (const []) xs Set.empty where<br>
> > go x r s<br>
> > | x `Set.member` s = r s<br>
> > | otherwise = x : r (Set.insert x s)<br>
> ><br>
> > which would suggest also<br>
> ><br>
> > ordNubR :: (Foldable t, Ord a)<br>
> > => t a -> [a]<br>
> > ordNubR xs = foldl go (const []) xs Set.empty where<br>
> > go r x s<br>
> > | x `Set.member` s = r s<br>
> > | otherwise = x : r (Set.insert x s)<br>
> ><br>
> > For containers biased the other way.<br>
> ><br>
> > Another question: do you have anything else you think should be stuck in<br>
> > the new module?<br>
> ><br>
> > On Oct 16, 2017 6:18 PM, "Gershom B" wrote:<br>
> ><br>
> > 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<br>
> > <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>
> ><br>
> ><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>
> ><br>
><br>
</blockquote></div></div>