Proposal: add ordNub somewhere in containers

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
26 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Proposal: add ordNub somewhere in containers

Gershom Bazerman
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

David Feuer
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" <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Alex Rozenshteyn
(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)

> [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 <[hidden email]> 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" <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

David Feuer
Not really. We have access to the internals, so we *can* do that sort of thing. Should we?

On Oct 17, 2017 1:44 AM, "Alex Rozenshteyn" <[hidden email]> wrote:
(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)

> [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 <[hidden email]> 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" <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Gershom Bazerman
In reply to this post by Alex Rozenshteyn
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
([hidden email]) wrote:

> (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)
>
> > [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
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
> >
> > _______________________________________________
> > Libraries mailing list
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

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

On Oct 17, 2017 2:09 AM, "Gershom B" <[hidden email]> 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
([hidden email]) wrote:
> (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)
>
> > [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
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
> >
> > _______________________________________________
> > Libraries mailing list
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
>

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Henning Thielemann
In reply to this post by David Feuer

On Mon, 16 Oct 2017, David Feuer wrote:

> I would imagine
>
> ordNub :: (Foldable t, Ord a)
>        => t a -> [a]


The kind of generalization where the input is Foldable but the output is
just a list looks pretty unnatural to me. I think it means that we still
do not have the proper generalization that allows us to define

   ordNub :: (??? f, Ord a) => f a -> f a

I would just leave it as ordNub :: (Ord a) => [a] -> [a]
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Haskell - Libraries mailing list
As a tangent I am interested in knowing what would be the typeclass for this sort of operation:

 - take all the elements out of `f a`
 - do something with them with a function a -> b
 - insert the results back to get the same "original shape" `f b`

In this case "do something with them" is "order them" but it could also be 
"invoke a function with all the 'a's and dispatch back the results" to allow "batching" function calls.


------------------------------------------------
Eric TORREBORRE
T +49 176 420 8383 4
E [hidden email]
P http://specs2.org
B http://etorreborre.blogspot.com
------------------------------------------------


Le mardi 17 octobre 2017 à 11:05:43 UTC+2, Henning Thielemann <[hidden email]> a écrit :



On Mon, 16 Oct 2017, David Feuer wrote:

> I would imagine
>
> ordNub :: (Foldable t, Ord a)
>        => t a -> [a]



The kind of generalization where the input is Foldable but the output is
just a list looks pretty unnatural to me. I think it means that we still
do not have the proper generalization that allows us to define

  ordNub :: (??? f, Ord a) => f a -> f a

I would just leave it as ordNub :: (Ord a) => [a] -> [a]
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Henning Thielemann

On Tue, 17 Oct 2017, Eric Torreborre via Libraries wrote:

> As a tangent I am interested in knowing what would be the typeclass for this sort of operation:
>
>  - take all the elements out of `f a`
>  - do something with them with a function a -> b
>  - insert the results back to get the same "original shape" `f b`

I guess, this one can only be Functor.

> In this case "do something with them" is "order them"

A function of type (a -> b) would not be able to order elements.


ordNub could be implemented using Traversable:

    catMaybes (traverse ??? xs :: [Maybe a])

You would only need a generalization for catMaybes like mfilter.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Michael Walker
> ordNub could be implemented using Traversable:
>
>    catMaybes (traverse ??? xs :: [Maybe a])
>
> You would only need a generalization for catMaybes like mfilter.

The witherable package
(https://hackage.haskell.org/package/witherable) has a typeclass
generalising Traversable to containers which can remove elements.  So
I suspect Witherable is exactly the abstraction needed to write a
polymorphic function:

ordNub :: (Witherable f, Ord a) => f a -> f a
ordNub = catMaybes . ordNub'

ordNub' :: (Traversable f, Ord a) => f a -> f (Maybe a)
ordNub; = ...

--
Michael Walker (http://www.barrucadu.co.uk)
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Henning Thielemann
In reply to this post by Henning Thielemann

On Tue, 17 Oct 2017, Henning Thielemann wrote:

> ordNub could be implemented using Traversable:
>
>   catMaybes (traverse ??? xs :: [Maybe a])
>
> You would only need a generalization for catMaybes like mfilter.

ordNub :: (Traversable f, MonadPlus f, Ord a) => f a -> f a
ordNub =
    join . snd .
    Trav.mapAccumL
       (\s x ->
          if Set.member x s
            then (s,mzero)
            else (Set.insert x s, return x))
       Set.empty


We don't need mplus, only Monad and mzero.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Alex Rozenshteyn
In reply to this post by David Feuer
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" <[hidden email]> 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
([hidden email]) wrote:
> (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)
>
> > [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
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
> >
> > _______________________________________________
> > Libraries mailing list
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
>

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Andreas Abel
+1 for nubOn.  This is a very useful generalization and no more work
than implementing just nub.

On 17.10.2017 17:21, Alex Rozenshteyn wrote:

>     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" <[hidden email]
>     <mailto:[hidden email]>> 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
>         ([hidden email] <mailto:[hidden email]>) wrote:
>          > (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)
>          >
>          > > [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
>          > > [hidden email] <mailto:[hidden email]>
>          > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>          > >
>          > >
>          > > _______________________________________________
>          > > Libraries mailing list
>          > > [hidden email] <mailto:[hidden email]>
>          > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>          > >
>          >
>
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>


--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www.cse.chalmers.se/~abela/
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Herbert Valerio Riedel-3
In reply to this post by Gershom Bazerman

On 2017-10-16 at 18:17:19 -0400, Gershom B wrote:

[...]

> 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.
I'm generally +1 for an 'ordNub'; I don't mind the particular color of
the shed.

While at it, I'd like to use the occasion to point out two minor things
with that specific implementation:

 a) One thing I've been missing from `container's API are "UPSERT"-ish
    operations; In the case of `Set`, the implementation above performs
    a lookup, and then has to start the insertion from scratch.

    If we had something like,

       Set.tryInsert :: Ord a => a -> Set a -> (Set a, Bool)

    or

       Set.tryInsert :: Ord a => a -> Set a -> Maybe (Set a)

    `ordNub` would benefit.


 b) This is more of an observation, as there's not much we can do here
    with little effort:

    iirc, `nub` has a worst-case space complexity (if the input list is
    made up of N distinct values, e.g. (`nub [1..n] :: [Int])) of 3N
    words for the [a]-spine to keep track of the already seen values.

    Using `Set` however trades time-complexity for memory-complexity,
    and needs 5N words for the 'Set a'-spine.

    c.f. http://blog.johantibell.com/2011/06/memory-footprints-of-some-common-data.html


-- hvr

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (834 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Niklas Hambüchen
In reply to this post by Gershom Bazerman
I guess it goes without saying that I'm +1 on this issue.

Like you have I copied ordNub hundreds of times, and debugged clients'
code slow performance for hours and hours, as due to lack of an easily
available nub alternative they longed for nub.

It would be great if this could finally come to an end.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

David Feuer
In reply to this post by Gershom Bazerman
I am convinced that we should add

ordNub :: Ord a => [a] -> [a]
ordNubOn :: Ord b => (a -> b) -> [a] -> [b]
intNub :: [Int] -> [Int]
intNubOn :: (a -> Int) -> [a] -> [a]

And because nub preserves non-emptiness, I believe we should also offer

ordNub1 :: Ord a => NonEmpty a -> NonEmpty a
ordNubOn1 :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty a
intNub1 :: NonEmpty Int -> NonEmpty Int
intNubOn1 :: (a -> Int) -> NonEmpty a -> NonEmpty a

I imagine we should also add these operations for Data.Sequence.Seq. 

I'm not yet convinced that we should add

ordNubBy :: (a -> a -> Ordering) -> [a] -> [a]

but I'm open to further discussion of that question. My main concern is that the properties of the comparison argument require careful documentation. In its favor, using it improperly cannot *expose* a broken Set to later operations.

I would very much like to hear further bikeshedding around names and namespaces.

On Oct 16, 2017 6:18 PM, "Gershom B" <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Gershom Bazerman
I agree that `ordNubOn` suffices and we don't need `ordNubBy` since
there's nothing lawful you can do with the latter that you can't do
with the former. I'm indifferent on the NonEmpty and Seq case as I
don't suspect that they will yield much more efficient implementations
than going via lists, especially if we setup (and we should!) the
fusion rules correctly. I have no objection to adding them for
completeness however.

If we do add them, then the proposed module name
`Data.Containers.ListUtils` becomes slightly less appropriate, but I
think still fine, since these are "morally" all lists of various
sorts.

-g


On Wed, Oct 18, 2017 at 1:49 PM, David Feuer <[hidden email]> wrote:

> I am convinced that we should add
>
> ordNub :: Ord a => [a] -> [a]
> ordNubOn :: Ord b => (a -> b) -> [a] -> [b]
> intNub :: [Int] -> [Int]
> intNubOn :: (a -> Int) -> [a] -> [a]
>
> And because nub preserves non-emptiness, I believe we should also offer
>
> ordNub1 :: Ord a => NonEmpty a -> NonEmpty a
> ordNubOn1 :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty a
> intNub1 :: NonEmpty Int -> NonEmpty Int
> intNubOn1 :: (a -> Int) -> NonEmpty a -> NonEmpty a
>
> I imagine we should also add these operations for Data.Sequence.Seq.
>
> I'm not yet convinced that we should add
>
> ordNubBy :: (a -> a -> Ordering) -> [a] -> [a]
>
> but I'm open to further discussion of that question. My main concern is that
> the properties of the comparison argument require careful documentation. In
> its favor, using it improperly cannot *expose* a broken Set to later
> operations.
>
> I would very much like to hear further bikeshedding around names and
> namespaces.
>
> On Oct 16, 2017 6:18 PM, "Gershom B" <[hidden email]> 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
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

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

case ordNub (toList xs) of
  [] -> error "can't happen!"
  x : xs -> x :| xs

I hate "can't happen" errors!

The case for sequences is less compelling with fusion, for sure, but it seems a bit strange to leave them out.

On Oct 18, 2017 5:28 PM, "Gershom B" <[hidden email]> wrote:
I agree that `ordNubOn` suffices and we don't need `ordNubBy` since
there's nothing lawful you can do with the latter that you can't do
with the former. I'm indifferent on the NonEmpty and Seq case as I
don't suspect that they will yield much more efficient implementations
than going via lists, especially if we setup (and we should!) the
fusion rules correctly. I have no objection to adding them for
completeness however.

If we do add them, then the proposed module name
`Data.Containers.ListUtils` becomes slightly less appropriate, but I
think still fine, since these are "morally" all lists of various
sorts.

-g


On Wed, Oct 18, 2017 at 1:49 PM, David Feuer <[hidden email]> wrote:
> I am convinced that we should add
>
> ordNub :: Ord a => [a] -> [a]
> ordNubOn :: Ord b => (a -> b) -> [a] -> [b]
> intNub :: [Int] -> [Int]
> intNubOn :: (a -> Int) -> [a] -> [a]
>
> And because nub preserves non-emptiness, I believe we should also offer
>
> ordNub1 :: Ord a => NonEmpty a -> NonEmpty a
> ordNubOn1 :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty a
> intNub1 :: NonEmpty Int -> NonEmpty Int
> intNubOn1 :: (a -> Int) -> NonEmpty a -> NonEmpty a
>
> I imagine we should also add these operations for Data.Sequence.Seq.
>
> I'm not yet convinced that we should add
>
> ordNubBy :: (a -> a -> Ordering) -> [a] -> [a]
>
> but I'm open to further discussion of that question. My main concern is that
> the properties of the comparison argument require careful documentation. In
> its favor, using it improperly cannot *expose* a broken Set to later
> operations.
>
> I would very much like to hear further bikeshedding around names and
> namespaces.
>
> On Oct 16, 2017 6:18 PM, "Gershom B" <[hidden email]> 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
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Gershom Bazerman
Vis a vis NonEmpty, base provides a partial `fromList`, much as I
dislike it. Hence, the proper "roll your own" is `fromList . ordNub .
toList`.

--Gershom

On Wed, Oct 18, 2017 at 5:40 PM, David Feuer <[hidden email]> wrote:

> 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
>
> case ordNub (toList xs) of
>   [] -> error "can't happen!"
>   x : xs -> x :| xs
>
> I hate "can't happen" errors!
>
> The case for sequences is less compelling with fusion, for sure, but it
> seems a bit strange to leave them out.
>
> On Oct 18, 2017 5:28 PM, "Gershom B" <[hidden email]> wrote:
>>
>> I agree that `ordNubOn` suffices and we don't need `ordNubBy` since
>> there's nothing lawful you can do with the latter that you can't do
>> with the former. I'm indifferent on the NonEmpty and Seq case as I
>> don't suspect that they will yield much more efficient implementations
>> than going via lists, especially if we setup (and we should!) the
>> fusion rules correctly. I have no objection to adding them for
>> completeness however.
>>
>> If we do add them, then the proposed module name
>> `Data.Containers.ListUtils` becomes slightly less appropriate, but I
>> think still fine, since these are "morally" all lists of various
>> sorts.
>>
>> -g
>>
>>
>> On Wed, Oct 18, 2017 at 1:49 PM, David Feuer <[hidden email]>
>> wrote:
>> > I am convinced that we should add
>> >
>> > ordNub :: Ord a => [a] -> [a]
>> > ordNubOn :: Ord b => (a -> b) -> [a] -> [b]
>> > intNub :: [Int] -> [Int]
>> > intNubOn :: (a -> Int) -> [a] -> [a]
>> >
>> > And because nub preserves non-emptiness, I believe we should also offer
>> >
>> > ordNub1 :: Ord a => NonEmpty a -> NonEmpty a
>> > ordNubOn1 :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty a
>> > intNub1 :: NonEmpty Int -> NonEmpty Int
>> > intNubOn1 :: (a -> Int) -> NonEmpty a -> NonEmpty a
>> >
>> > I imagine we should also add these operations for Data.Sequence.Seq.
>> >
>> > I'm not yet convinced that we should add
>> >
>> > ordNubBy :: (a -> a -> Ordering) -> [a] -> [a]
>> >
>> > but I'm open to further discussion of that question. My main concern is
>> > that
>> > the properties of the comparison argument require careful documentation.
>> > In
>> > its favor, using it improperly cannot *expose* a broken Set to later
>> > operations.
>> >
>> > I would very much like to hear further bikeshedding around names and
>> > namespaces.
>> >
>> > On Oct 16, 2017 6:18 PM, "Gershom B" <[hidden email]> 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
>> >> [hidden email]
>> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: add ordNub somewhere in containers

Michael Sloan
In reply to this post by David Feuer
On Wed, Oct 18, 2017 at 10:49 AM, David Feuer <[hidden email]> wrote:
> I am convinced that we should add
>
> ordNub :: Ord a => [a] -> [a]
> ordNubOn :: Ord b => (a -> b) -> [a] -> [b]
> intNub :: [Int] -> [Int]
> intNubOn :: (a -> Int) -> [a] -> [a]

+1 to ordNub / ordNubOn, and having the documentation for nub mention
that you probably want ordNub in nearly all cases.

+1 to intNub / intNubOn, with RULES pragma to specialize ordNub /
ordNubOn to it.

> And because nub preserves non-emptiness, I believe we should also offer
>
> ordNub1 :: Ord a => NonEmpty a -> NonEmpty a
> ordNubOn1 :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty a
> intNub1 :: NonEmpty Int -> NonEmpty Int
> intNubOn1 :: (a -> Int) -> NonEmpty a -> NonEmpty a

I wish these could go in base.  It would be export these from
Data.List.NonEmpty, using the same names as the list operations, but
this is not possible due to the implementation in terms of Set.

> I imagine we should also add these operations for Data.Sequence.Seq.

+1

> I'm not yet convinced that we should add
>
> ordNubBy :: (a -> a -> Ordering) -> [a] -> [a]

Such an operation is quite useful, though unfortunately it does not
fit naturally into an implementation in terms of Set.  There are quite
reasonable use-cases here, where even a hack with a new datatype could
be quite convoluted.    I recently used a "sortNubBy" in a client
project.  Perhaps that should be another proposal - it is something
that could be in base, though less efficient.  In particular, this
function is useful in cases where the ordering depends on some value
other than the value of the element.  Another, more common case, is
ignoring some distinctions between values, such as ignoring a field.
Sure, you can make a newtype and use "coerce" for this, but I don't
like using "coerce" because in general it can break invariants.  Much
better than unsafeCoerce, of course, but still unsafe.  I'd rather not
create an Ord instance just to use it in one place, it seems like
unnecessary plumbing.

> but I'm open to further discussion of that question. My main concern is that
> the properties of the comparison argument require careful documentation. In
> its favor, using it improperly cannot *expose* a broken Set to later
> operations.
>
> I would very much like to hear further bikeshedding around names and
> namespaces.
>
> On Oct 16, 2017 6:18 PM, "Gershom B" <[hidden email]> 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
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
12