Proposal: add ordNub somewhere in containers

[Gershom B]

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
> >
>