<div dir="auto">The trouble with NonEmpty is that I don't like the idea of users having to roll their own. They'd end up looking like<div dir="auto"><br></div><div dir="auto">case ordNub (toList xs) of</div><div dir="auto"> [] -> error "can't happen!"</div><div dir="auto"> x : xs -> x :| xs</div><div dir="auto"><br></div><div dir="auto">I hate "can't happen" errors!</div><div dir="auto"><br></div><div dir="auto">The case for sequences is less compelling with fusion, for sure, but it seems a bit strange to leave them out.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Oct 18, 2017 5:28 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">I agree that `ordNubOn` suffices and we don't need `ordNubBy` since<br>
there's nothing lawful you can do with the latter that you can't do<br>
with the former. I'm indifferent on the NonEmpty and Seq case as I<br>
don't suspect that they will yield much more efficient implementations<br>
than going via lists, especially if we setup (and we should!) the<br>
fusion rules correctly. I have no objection to adding them for<br>
completeness however.<br>
<br>
If we do add them, then the proposed module name<br>
`Data.Containers.ListUtils` becomes slightly less appropriate, but I<br>
think still fine, since these are "morally" all lists of various<br>
sorts.<br>
<br>
-g<br>
<br>
<br>
On Wed, Oct 18, 2017 at 1:49 PM, David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br>
> I am convinced that we should add<br>
><br>
> ordNub :: Ord a => [a] -> [a]<br>
> ordNubOn :: Ord b => (a -> b) -> [a] -> [b]<br>
> intNub :: [Int] -> [Int]<br>
> intNubOn :: (a -> Int) -> [a] -> [a]<br>
><br>
> And because nub preserves non-emptiness, I believe we should also offer<br>
><br>
> ordNub1 :: Ord a => NonEmpty a -> NonEmpty a<br>
> ordNubOn1 :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty a<br>
> intNub1 :: NonEmpty Int -> NonEmpty Int<br>
> intNubOn1 :: (a -> Int) -> NonEmpty a -> NonEmpty a<br>
><br>
> I imagine we should also add these operations for Data.Sequence.Seq.<br>
><br>
> I'm not yet convinced that we should add<br>
><br>
> ordNubBy :: (a -> a -> Ordering) -> [a] -> [a]<br>
><br>
> but I'm open to further discussion of that question. My main concern is that<br>
> the properties of the comparison argument require careful documentation. In<br>
> its favor, using it improperly cannot *expose* a broken Set to later<br>
> operations.<br>
><br>
> I would very much like to hear further bikeshedding around names and<br>
> namespaces.<br>
><br>
> On Oct 16, 2017 6:18 PM, "Gershom B" <<a href="mailto:gershomb@gmail.com">gershomb@gmail.com</a>> 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>
</blockquote></div></div>