Proposal: add ordNub somewhere in containers

[Gershom B]

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

[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" <***@gmail.com> 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

[Alex Rozenshteyn]

(Forgive me if I shouldn't be posting on ***@. 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?

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?
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[David Feuer]

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

Post by Alex Rozenshteyn
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?

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?
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from https://github.com/nh2/
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[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

Post by Alex Rozenshteyn
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?

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?
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[David Feuer]

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

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

Post by Alex Rozenshteyn
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?

Post by Alex Rozenshteyn
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?

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

Post by Alex Rozenshteyn

the new module?
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from
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.

Post by Alex Rozenshteyn

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Alex Rozenshteyn]

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 (<=)`.

Post by David Feuer

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

Post by Alex Rozenshteyn
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?

Post by Alex Rozenshteyn
As a user, I would expect to find the `...By` variants in the same
location, but that precludes reusing `Set` without relying on

complicated

Post by Alex Rozenshteyn
machinery like `reflection`, doesn't it?

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

Post by Alex Rozenshteyn

the new module?
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from
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.

Post by Alex Rozenshteyn

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Andreas Abel]

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

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 (<=)`.
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
little

Post by Alex Rozenshteyn
searching and couldn't determine if this list is supposed to

be a public

Post by Alex Rozenshteyn
forum or not)

[D]o you have anything else you think should be stuck in

the new module?

Post by Alex Rozenshteyn
As a user, I would expect to find the `...By` variants in the

same

Post by Alex Rozenshteyn
location, but that precludes reusing `Set` without relying on

complicated

Post by Alex Rozenshteyn
machinery like `reflection`, doesn't it?

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

Post by Alex Rozenshteyn

the new module?
There have been many discussions over the years about adding an
efficient order preserving nub somewhere to our core

libraries. It

Post by Alex Rozenshteyn

always comes down to the same issue: an efficient nub wants

to be

Post by Alex Rozenshteyn

backed by an efficient `Set`, but the API of the `nub`

itself doesn't

Post by Alex Rozenshteyn

make reference to any other data structures besides lists.

So it feels

Post by Alex Rozenshteyn

a bit conceptually strange to put an efficient nub anywhere

besides

Post by Alex Rozenshteyn

`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

Post by Alex Rozenshteyn

core library is undeniable, and after writing the "usual"

one in my

Post by Alex Rozenshteyn

code for the zillionth time, I decided to raise an issue
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from
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.

Post by Alex Rozenshteyn

The rationale for the names is that the former has a long

history of

Post by Alex Rozenshteyn

use in folklore, and the latter is the obvious

specialization of it.

Post by Alex Rozenshteyn

2) I propose these functions be added to a new module in the
`containers` library: `Data.Containers.ListUtils`. This can

also

Post by Alex Rozenshteyn

potentially in the future add efficient list intersection,

etc. as

Post by Alex Rozenshteyn

documented on the above reference link.
The rationale for the new module is that it can provide a

meaningful

Post by Alex Rozenshteyn

home for such functions which operate on lists, but require

other data

Post by Alex Rozenshteyn

structures to be implemented efficiently...
Discussion period: 2 weeks.
--Gershom
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

[Henning Thielemann]

Post by David Feuer
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]

[Henning Thielemann]

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

[Michael Walker]

Post by Henning Thielemann
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; = ...

[Henning Thielemann]

Post by Henning Thielemann
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.

[Herbert Valerio Riedel]

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

[...]

Post by Gershom B
1) I propose two new functions,
`ordNub` and `intNub`
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

[Niklas Hambüchen]

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.

[David Feuer]

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.

Post by Gershom B
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from https://github.com/nh2/
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Gershom B]

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

Post by David Feuer
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.

Post by Gershom B
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

Post by Gershom B
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

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

Post by David Feuer
the properties of the comparison argument require careful documentation.

In

Post by David Feuer
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.

Post by Gershom B
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from
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.

Post by David Feuer

Post by Gershom B
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Gershom B]

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

Post by 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.

Post by Gershom B
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

Post by David Feuer
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.

Post by Gershom B
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Henning Thielemann]

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

My idea of NonEmpty is to prove totality by implementation. I'd prefer a
custom obviously total implementation of NonEmpty.ordNub.

[Michael Sloan]

Post by David Feuer
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.

Post by David Feuer
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.

Post by David Feuer
I imagine we should also add these operations for Data.Sequence.Seq.

+1

Post by David Feuer
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.

Post by David Feuer
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.

Post by Gershom B
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
https://github.com/haskell/containers/issues/439
I was promptly directed here to make a proper proposal.
1) I propose two new functions,
`ordNub` and `intNub`
with the standard implementation (from
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

[Andreas Abel]

Your current proposal sounds fine, I think it is safe to go ahead.

Post by David Feuer
ordNubBy :: (a -> a -> Ordering) -> [a] -> [a]

can be taken at a second step, if there is no consensus now.

Personally, I would include it.

Post by David Feuer
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.
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
https://github.com/haskell/containers/issues/439
<https://github.com/haskell/containers/issues/439>
I was promptly directed here to make a proper proposal.
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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
<http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Joachim Breitner]

Hi,

Post by David Feuer
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]

can we shed the names a bit? I think the operation “nubbing” should be
first, and the details (”
On”, “
By”, “
OrdOn”, “Ord”, “Int”) should be
the second component. This would also have the advantage of listing all
”nub” variants together in an index.

So:

nubOrd :: Ord a => [a] -> [a]
nubOrdOn :: Ord b => (a -> b) -> [a] -> [b]
nubInt :: [Int] -> [Int]
nubIntOn :: (a -> Int) -> [a] -> [a]

This is consistent with, say “map” vs. “mapM” and other suffix-based
naming in the libraries.


Greetings,
Joachim

[Elliot Cameron]

That's also consistent with the commonly used "extra" package:
https://hackage.haskell.org/package/extra-1.6/docs/Data-List-Extra.html#v:nubOrd

Post by Joachim Breitner
Hi,

Post by David Feuer
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]

can we shed the names a bit? I think the operation “nubbing” should be
first, and the details (”
On”, “
By”, “
OrdOn”, “Ord”, “Int”) should be
the second component. This would also have the advantage of listing all
”nub” variants together in an index.
nubOrd :: Ord a => [a] -> [a]
nubOrdOn :: Ord b => (a -> b) -> [a] -> [b]
nubInt :: [Int] -> [Int]
nubIntOn :: (a -> Int) -> [a] -> [a]
This is consistent with, say “map” vs. “mapM” and other suffix-based
naming in the libraries.
Greetings,
Joachim
--
Joachim Breitner
http://www.joachim-breitner.de/
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Henning Thielemann]

The discussion period is well over and it seems the consensus is for
adding this, basically as David proposes. -- i.e. ordNub, and
ordNubOn, but not ordNubBy. (and also the -1 variants and the int-
variants). I think the only module name proposed to add them to is
Data.Containers.ListUtils, so I guess that stands.

I think there should be some more thoughts on a good module name. E.g. use
of plural (Utils vs. Util) - singular makes more sense in qualified
identifiers, use of abbreviations (Util vs. Utility) - we have 'import ...
as' for abbreviations, consistency with other data structures - where
would we put ordNub for Seq, in Data.Container.SequenceUtility or in
Data.Sequence?