<div dir="ltr">(Forgive me if I shouldn't be posting on libraries@. I did a little searching and couldn't determine if this list is supposed to be a public forum or not)<div><br></div><div>> [D]<span style="color:rgb(33,33,33)">o you have anything else you think should be stuck in the new module?</span></div><div><br></div><div>As a user, I would expect to find the `...By` variants in the same location, but that precludes reusing `Set` without relying on complicated machinery like `reflection`, doesn't it?</div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Oct 16, 2017 at 3:45 PM David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div>I would imagine</div><div dir="auto"><br></div><div dir="auto"><span style="font-family:sans-serif">ordNub :: (Foldable t, Ord a)</span></div><div dir="auto"><span style="font-family:sans-serif"> => t a -> [a]</span><br style="font-family:sans-serif"><span style="font-family:sans-serif">ordNub xs = foldr go (const []) xs Set.empty where</span></div><div dir="auto"><span style="font-family:sans-serif"> go x r s</span></div><div dir="auto"><span style="font-family:sans-serif"> | x `Set.member` s = r s</span></div><div dir="auto"><span style="font-family:sans-serif"> | otherwise = x : r (Set.insert x s)</span></div><div dir="auto"><br></div><div dir="auto">which would suggest also</div><div dir="auto"><br></div><div dir="auto"><div dir="auto" style="font-family:sans-serif">ordNubR :: (Foldable t, Ord a)</div><div dir="auto" style="font-family:sans-serif"> => t a -> [a]<br>ordNubR xs = foldl go (const []) xs Set.empty where</div><div dir="auto" style="font-family:sans-serif"> go r x s</div><div dir="auto" style="font-family:sans-serif"> | x `Set.member` s = r s</div><div dir="auto" style="font-family:sans-serif"> | otherwise = x : r (Set.insert x s)</div><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">For containers biased the other way.</div><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">Another question: do you have anything else you think should be stuck in the new module?</div></div></div><div dir="auto"><div dir="auto"><div class="gmail_extra" dir="auto"><br><div class="gmail_quote">On Oct 16, 2017 6:18 PM, "Gershom B" <<a href="mailto:gershomb@gmail.com" target="_blank">gershomb@gmail.com</a>> wrote:<br type="attribution"><blockquote class="m_-3544761891068950560quote" 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/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/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>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">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-bin/mailman/listinfo/libraries</a><br>
</blockquote></div><br></div></div></div>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">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-bin/mailman/listinfo/libraries</a><br>
</blockquote></div>