Proposal: add ordNub somewhere in containers

[Alex Rozenshteyn]

>
> nubOn :: Ord b => (a -> b) -> [a] -> [a],
> or the Foldable version, seem just a bit safer, but less convenient.
>

I actually find the `...On` variants more convenient. I will often want to
`nubBy ((==) `on` fst` (or `groupBy`), but rarely `nubBy (<=)`.


> On Oct 17, 2017 2:09 AM, "Gershom B" <gershomb at gmail.com> wrote:
>
>> Good point on the by variants. (And indeed this is a public forum).
>>
>> Those can be written without any fancy machinery, just keeping the
>> `by` data in the set, in the straightforward way. I agree it makes
>> sense to add them.
>>
>> -g
>>
>>
>> On October 17, 2017 at 1:44:30 AM, Alex Rozenshteyn
>> (rpglover64 at gmail.com) wrote:
>> > (Forgive me if I shouldn't be posting on libraries at . I did a little
>> > searching and couldn't determine if this list is supposed to be a public
>> > forum or not)
>> >
>> > > [D]o you have anything else you think should be stuck in the new
>> module?
>> >
>> > 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?
>> >
>> > On Mon, Oct 16, 2017 at 3:45 PM David Feuer wrote:
>> >
>> > > I would imagine
>> > >
>> > > ordNub :: (Foldable t, Ord a)
>> > > => t a -> [a]
>> > > ordNub xs = foldr go (const []) xs Set.empty where
>> > > go x r s
>> > > | x `Set.member` s = r s
>> > > | otherwise = x : r (Set.insert x s)
>> > >
>> > > which would suggest also
>> > >
>> > > ordNubR :: (Foldable t, Ord a)
>> > > => t a -> [a]
>> > > ordNubR xs = foldl go (const []) xs Set.empty where
>> > > go r x s
>> > > | x `Set.member` s = r s
>> > > | otherwise = x : r (Set.insert x s)
>> > >
>> > > For containers biased the other way.
>> > >
>> > > Another question: do you have anything else you think should be stuck
>> in
>> > > the new module?
>> > >
>> > > On Oct 16, 2017 6:18 PM, "Gershom B" wrote:
>> > >
>> > > There have been many discussions over the years about adding an
>> > > efficient order preserving nub somewhere to our core libraries. It
>> > > always comes down to the same issue: an efficient nub wants to be
>> > > backed by an efficient `Set`, but the API of the `nub` itself doesn't
>> > > make reference to any other data structures besides lists. So it feels
>> > > a bit conceptually strange to put an efficient nub anywhere besides
>> > > `Data.List` even though it can't go there without inverting our
>> > > dependency tree in a weird way or inlining an efficient set
>> > > implementation into the middle of it.
>> > >
>> > > Nonetheless, the convenience of having a good `nub` lying around in a
>> > > core library is undeniable, and after writing the "usual" one in my
>> > > code for the zillionth time, I decided to raise an issue about it:
>> > >
>> > > https://github.com/haskell/containers/issues/439
>> > >
>> > > I was promptly directed here to make a proper proposal.
>> > >
>> > > So, here:
>> > >
>> > > 1) I propose two new functions,
>> > >
>> > > `ordNub` and `intNub`
>> > >
>> > > with the standard implementation (from
>> > > https://github.com/nh2/haskell-ordnub):
>> > >
>> > > import qualified Data.Set as Set
>> > >
>> > > ordNub :: (Ord a) => [a] -> [a]
>> > > ordNub l = go Set.empty l
>> > > where
>> > > go _ [] = []
>> > > go s (x:xs) = if x `Set.member` s then go s xs
>> > > else x : go (Set.insert x s) xs
>> > >
>> > > and the same implementation, but specialized to `Int` and using
>> `IntSet`s.
>> > >
>> > > The rationale for the names is that the former has a long history of
>> > > use in folklore, and the latter is the obvious specialization of it.
>> > >
>> > > 2) I propose these functions be added to a new module in the
>> > > `containers` library: `Data.Containers.ListUtils`. This can also
>> > > potentially in the future add efficient list intersection, etc. as
>> > > documented on the above reference link.
>> > >
>> > > The rationale for the new module is that it can provide a meaningful
>> > > home for such functions which operate on lists, but require other data
>> > > structures to be implemented efficiently...
>> > >
>> > > Discussion period: 2 weeks.
>> > >
>> > > --Gershom
>> > > _______________________________________________
>> > > Libraries mailing list
>> > > Libraries at haskell.org
>> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> > >
>> > >
>> > > _______________________________________________
>> > > Libraries mailing list
>> > > Libraries at haskell.org
>> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> > >
>> >
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20171017/dc700ed3/attachment.html>