ordNub

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

Re: ordNub

Stijn van Drongelen
On Fri, Oct 18, 2013 at 3:03 PM, Andreas Abel <[hidden email]> wrote:

P.S.: The Agda source has tons of .hs-boot files, I hate them, but what can you do?


Implement support for mutually recursive modules? ;)

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Dan Doel
In reply to this post by Niklas Hambüchen
On Thu, Oct 17, 2013 at 2:52 PM, Niklas Hambüchen <[hidden email]> wrote:
> Can the Data.List <-> Data.Set issue be resolved?
>
> Is it OK to introduce a cyclic dependency between the two, making use of
> a .boot.hs file?


Data.List and Data.Set aren't even members of the same package. So
hs-boot files won't help.

-- Dan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Niklas Hambüchen
> Data.List and Data.Set aren't even members of the same package. So
> hs-boot files won't help.

Damn, you are right. I even mentioned this myself earlier.

It would need a set in base. I wonder if it was ok to use the Data.Set
implementation internally in base, without exposing it.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Yitzchak Gale
Niklas Hambüchen wrote:
> It would need a set in base. I wonder if it was ok to use the Data.Set
> implementation internally in base, without exposing it.

Ah yes, this is what stopped previous attempts at getting
ordNub in.

The GHC team is very keen on getting more things *out* of base.
Unless something has changed, getting them to include new things
in base, even if hidden, would be extremely difficult.
Adding additional dependencies and maintenance burdens would
add extra work for the overburdened GHC team and slow the
GHC release cycle.

How about adding a module named something like Data.List.Nub
to containers and putting ordNub in there? Or just go back to the
idea of putting it in Data.Set.

-Yitz
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

David Thomas
With such a big speedup and not a lot of downside, I'd really rather it wind up central enough to be used in preference to nub wherever possible (including in base!).  Perhaps they can duplicate the minimum functionality necessary from Data.Set, internally behind the scenes?  Alternatively, maybe we can move nub out of base?


On Fri, Oct 18, 2013 at 11:47 AM, Yitzchak Gale <[hidden email]> wrote:
Niklas Hambüchen wrote:
> It would need a set in base. I wonder if it was ok to use the Data.Set
> implementation internally in base, without exposing it.

Ah yes, this is what stopped previous attempts at getting
ordNub in.

The GHC team is very keen on getting more things *out* of base.
Unless something has changed, getting them to include new things
in base, even if hidden, would be extremely difficult.
Adding additional dependencies and maintenance burdens would
add extra work for the overburdened GHC team and slow the
GHC release cycle.

How about adding a module named something like Data.List.Nub
to containers and putting ordNub in there? Or just go back to the
idea of putting it in Data.Set.

-Yitz
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Yitzchak Gale
David Thomas wrote:
> With such a big speedup and not a lot of downside

That is far from proven, and frankly, almost certainly untrue.

But again, it isn't the point here. There *are* case where you
do need nubOrd, and those cases are common enough for
it to make sense to get it into the libraries.

> I'd really rather it wind up central enough to be used in
> preference to nub wherever possible

You are welcome to your own preference. I, and many
other experienced Haskellers I know, prefer nub in many cases.
Let's just make both easily available please.

> (including in base!).

I wouldn't mind having ordNub in base. But let's at least
get it in somewhere convenient and easily usable. If you
focus the energy on trying to get it into base, this proposal
will likely die the same death as all previous attempts.

> Perhaps they can duplicate the minimum functionality
> necessary from Data.Set, internally behind the scenes?

Why should the GHC team agree to the maintenance burden
of that? They have enough of a challenge keeping up with the
work they already have.

But you know what, give it a try. Just don't get stuck
on that point if you meet with resistance.

> Alternatively, maybe we can move nub out of base?

No. nub is part of the Haskell standard, so it's required to
be there. Even if you disagree with my view that it should
be there on its own merits.

-Yitz
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Dan Doel
In reply to this post by David Thomas
On Fri, Oct 18, 2013 at 3:13 PM, David Thomas <[hidden email]> wrote:
> With such a big speedup and not a lot of downside, I'd really rather it wind
> up central enough to be used in preference to nub wherever possible
> (including in base!).  Perhaps they can duplicate the minimum functionality
> necessary from Data.Set, internally behind the scenes?  Alternatively, maybe
> we can move nub out of base?

The string 'nub' does not appear anywhere (that I can find) in base
outside of Data.List. All occurrences of 'nub' in Data.List are in the
definition and export of nub and nubBy, except one use of nubBy in
unionBy, which cannot switch to ordNub, and would have to have its own
alternate function.

Of all the libraries packaged with GHC, the only one I see that uses
nub outside of tests is Cabal, which already depends on containers.
And in fact, one of the libraries I grepped through _was_ containers,
because it's already about as close as you can get to being in base
without actually being there, and is certainly as close as many other
things will be once we split up base into more packages.

I don't think it's really accurate to suggest that containers is less
core than base. It's not just, 'some library.'

-- Dan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Tom Ellis
In reply to this post by Clark Gaebel-2
On Mon, Jul 15, 2013 at 11:21:39PM -0400, Clark Gaebel wrote:
> As a tangent, can anyone think of a data structure for which you can
> write an Ord instance but Hashable/Eq is impossible (or prove
> otherwise)? How about the converse?

A conversation on #haskell brought back to mind this question, which I'm not
sure was ever answered.

Is there a type with an Eq instance for which on Ord instance could not also
be provided (i.e. I'm interested in Clark's "converse")?

One answer is that I could write

    data A = A deriving Eq

and then not export the constructor.  That would make it impossible to write
an Ord instance.  However, I'm more interested in the question "morally" or
"in principle".

If we think about algebraic datatypes built from sums and products of base
types, which have both Eq and Ord, and the function type construct, which
prevents both Eq and Ord, it seems that the two always go together, in
principle.

Am I missing anything more exotic?  IORef's have Eq but not Ord.  Is there a
good reason for that?  Would Ord break "referential transparency" somehow?
I doubt it.  How about STRef?  It seems more likely they shouldn't have Ord.

Any thoughts?

Tom
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

David Feuer
In reply to this post by Niklas Hambüchen

I think ordNub in Data.Set, hashNub in Data.HashSet or somewhere, and bitsNub in Data.Bits (for FiniteBits things).

On Jul 14, 2013 7:21 AM, "Niklas Hambüchen" <[hidden email]> wrote:
tldr: nub is abnormally slow, we shouldn't use it, but we do.


As you might know, Data.List.nub is O(n²). (*)

As you might not know, almost *all* practical Haskell projects use it,
and that in places where an Ord instance is given, e.g. happy, Xmonad,
ghc-mod, Agda, darcs, QuickCheck, yesod, shake, Cabal, haddock, and 600
more (see https://github.com/nh2/haskell-ordnub).

I've taken the Ord-based O(n * log n) implementation from yi using a Set:

  ordNub :: (Ord a) => [a] -> [a]
  ordNub l = go empty l
    where
      go _ []     = []
      go s (x:xs) = if x `member` s then go s xs
                                    else x : go (insert x s) xs


and put benchmarks on
http://htmlpreview.github.io/?https://github.com/nh2/haskell-ordnub/blob/1f0a2c94a/report.html
(compare `nub` vs `ordNub`).

`ordNub` is not only in a different complexity class, but even seems to
perform better than nub for very small numbers of actually different
list elements (that's the numbers before the benchmark names).

(The benchmark also shows some other potential problem: Using a state
monad to keep the set instead of a function argument can be up to 20
times slower. Should that happen?)

What do you think about ordNub?

I've seen a proposal from 5 years ago about adding a *sort*Nub function
started by Neil, but it just died.


(*) The mentioned complexity is for the (very common) worst case, in
which the number of different elements in the list grows with the list
(alias you don't have an N element list with always only 5 different
things inside).

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

David Feuer

Er.. that last might be to hard. But Data.IntSet can support its own nub version.

On Jan 1, 2015 8:42 AM, "David Feuer" <[hidden email]> wrote:

I think ordNub in Data.Set, hashNub in Data.HashSet or somewhere, and bitsNub in Data.Bits (for FiniteBits things).

On Jul 14, 2013 7:21 AM, "Niklas Hambüchen" <[hidden email]> wrote:
tldr: nub is abnormally slow, we shouldn't use it, but we do.


As you might know, Data.List.nub is O(n²). (*)

As you might not know, almost *all* practical Haskell projects use it,
and that in places where an Ord instance is given, e.g. happy, Xmonad,
ghc-mod, Agda, darcs, QuickCheck, yesod, shake, Cabal, haddock, and 600
more (see https://github.com/nh2/haskell-ordnub).

I've taken the Ord-based O(n * log n) implementation from yi using a Set:

  ordNub :: (Ord a) => [a] -> [a]
  ordNub l = go empty l
    where
      go _ []     = []
      go s (x:xs) = if x `member` s then go s xs
                                    else x : go (insert x s) xs


and put benchmarks on
http://htmlpreview.github.io/?https://github.com/nh2/haskell-ordnub/blob/1f0a2c94a/report.html
(compare `nub` vs `ordNub`).

`ordNub` is not only in a different complexity class, but even seems to
perform better than nub for very small numbers of actually different
list elements (that's the numbers before the benchmark names).

(The benchmark also shows some other potential problem: Using a state
monad to keep the set instead of a function argument can be up to 20
times slower. Should that happen?)

What do you think about ordNub?

I've seen a proposal from 5 years ago about adding a *sort*Nub function
started by Neil, but it just died.


(*) The mentioned complexity is for the (very common) worst case, in
which the number of different elements in the list grows with the list
(alias you don't have an N element list with always only 5 different
things inside).

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

oleg-30
In reply to this post by Niklas Hambüchen

Tom Ellis wrote:
> Is there a type with an Eq instance for which on Ord instance could not also
> be provided (i.e. I'm interested in Clark's "converse")?

Of course. One of the very many examples is Complex. One can say we
can compare complex numbers, by their absolute value.  That is true;
however we end up in a position where compare x y returns EQ but x==y
returns False.

In general, Ord represents total order. There are many structures on
which total order cannot be established. Take nodes in the tree, the
Tree data type. One can compare nodes by taking a parent to be less
than any of its children. But then two brothers are not
comparable. Searching for "partial orders" and pre-orders gives many
more examples.



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Tom Ellis
On Thu, Jan 01, 2015 at 08:58:35AM -0500, [hidden email] wrote:
> Tom Ellis wrote:
> > Is there a type with an Eq instance for which on Ord instance could not also
> > be provided (i.e. I'm interested in Clark's "converse")?
>
> Of course. One of the very many examples is Complex. One can say we
> can compare complex numbers, by their absolute value.  That is true;
> however we end up in a position where compare x y returns EQ but x==y
> returns False.

I don't understand your objection.  `Complex a` isomorphic to `(a, a)` which
can be totally ordered.  (The complex field cannot be given a total order
*compatible with the field structure*, but that's not relevant to my
question.)

> In general, Ord represents total order. There are many structures on
> which total order cannot be established. Take nodes in the tree, the
> Tree data type. One can compare nodes by taking a parent to be less
> than any of its children. But then two brothers are not
> comparable. Searching for "partial orders" and pre-orders gives many
> more examples.

I think you may be missing the intent of my question.  I am merely asking
whether there is a type which supports a (law abiding) Eq instance that
cannot support a (law abiding) Ord instance.  Whether that Ord instance is
compatible with additional structures on that type is beside the point.

Tom
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Atze van der Ploeg

Instance Ord a where
  _ <= _ = True

Is law abiding for any type. So there is no type that cannot support a law abiding Ord instance.

On Jan 1, 2015 3:04 PM, "Tom Ellis" <[hidden email]> wrote:
On Thu, Jan 01, 2015 at 08:58:35AM -0500, [hidden email] wrote:
> Tom Ellis wrote:
> > Is there a type with an Eq instance for which on Ord instance could not also
> > be provided (i.e. I'm interested in Clark's "converse")?
>
> Of course. One of the very many examples is Complex. One can say we
> can compare complex numbers, by their absolute value.  That is true;
> however we end up in a position where compare x y returns EQ but x==y
> returns False.

I don't understand your objection.  `Complex a` isomorphic to `(a, a)` which
can be totally ordered.  (The complex field cannot be given a total order
*compatible with the field structure*, but that's not relevant to my
question.)

> In general, Ord represents total order. There are many structures on
> which total order cannot be established. Take nodes in the tree, the
> Tree data type. One can compare nodes by taking a parent to be less
> than any of its children. But then two brothers are not
> comparable. Searching for "partial orders" and pre-orders gives many
> more examples.

I think you may be missing the intent of my question.  I am merely asking
whether there is a type which supports a (law abiding) Eq instance that
cannot support a (law abiding) Ord instance.  Whether that Ord instance is
compatible with additional structures on that type is beside the point.

Tom
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Tom Ellis
On Thu, Jan 01, 2015 at 03:12:15PM +0100, Atze van der Ploeg wrote:
> Instance Ord a where
>   _ <= _ = True
>
> Is law abiding for any type. So there is no type that cannot support a law
> abiding Ord instance.

So let me clarify that I want (<=) to be a total order in the sense that it
is

* reflexive
* symmetric
* transitive

and `(x <= y) && (y <= x)` implies that `x == y`.

Tom
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Atze van der Ploeg

Taking

Instance Eq a where
  _ == _ = True

Then it has all the properties you mentoined

On Jan 1, 2015 3:14 PM, "Tom Ellis" <[hidden email]> wrote:
On Thu, Jan 01, 2015 at 03:12:15PM +0100, Atze van der Ploeg wrote:
> Instance Ord a where
>   _ <= _ = True
>
> Is law abiding for any type. So there is no type that cannot support a law
> abiding Ord instance.

So let me clarify that I want (<=) to be a total order in the sense that it
is

* reflexive
* symmetric
* transitive

and `(x <= y) && (y <= x)` implies that `x == y`.

Tom
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Tom Ellis
In reply to this post by Tom Ellis
On Thu, Jan 01, 2015 at 02:14:16PM +0000, Tom Ellis wrote:
> So let me clarify that I want (<=) to be a total order in the sense that it
> is
>
> * reflexive
> * symmetric
> * transitive
>
> and `(x <= y) && (y <= x)` implies that `x == y`. (*)

Correction: I mean "antisymmetric" not "symmetric".  Anti-symmetry is
exactly this condition (*).

Futhermore I want (==) to be at least as fine-grained as extensional
equivalence.

Tom
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Tom Ellis
In reply to this post by Atze van der Ploeg
On Thu, Jan 01, 2015 at 03:17:13PM +0100, Atze van der Ploeg wrote:
> Taking
>
> Instance Eq a where
>   _ == _ = True
>
> Then it has all the properties you mentoined

Right, hence my latest clarification that "Futhermore I want (==) to be at
least as fine-grained as extensional equivalence.".
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Atze van der Ploeg

> i want it to be at least as fine grained as extensional equivalence

Then see Oleg's comment or am i missing something here?

On Jan 1, 2015 3:19 PM, "Tom Ellis" <[hidden email]> wrote:
On Thu, Jan 01, 2015 at 03:17:13PM +0100, Atze van der Ploeg wrote:
> Taking
>
> Instance Eq a where
>   _ == _ = True
>
> Then it has all the properties you mentoined

Right, hence my latest clarification that "Futhermore I want (==) to be at
least as fine-grained as extensional equivalence.".
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Tom Ellis
On Thu, Jan 01, 2015 at 03:22:55PM +0100, Atze van der Ploeg wrote:
> > i want it to be at least as fine grained as extensional equivalence
>
> Then see Oleg's comment or am i missing something here?

Perhaps you could explain Oleg's comment.  I don't understand it.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: ordNub

Atze van der Ploeg

Your question is if I understand correctly, whether we can think of a type that has a law abiding Eq instance that gives equality as fine grained as extensional equality (meaning structural equality?) but for which no law abing instance of Ord can be given such that a <= b && a >= b ==> a == b

This boils down to the question whether on each set with an equality relation defined on it a total ordering (consistent with the equality relation) can also be defined. One counterexample is the complex numbers.

Does that answer your question?

Cheers!

On Jan 1, 2015 3:27 PM, "Tom Ellis" <[hidden email]> wrote:
On Thu, Jan 01, 2015 at 03:22:55PM +0100, Atze van der Ploeg wrote:
> > i want it to be at least as fine grained as extensional equivalence
>
> Then see Oleg's comment or am i missing something here?

Perhaps you could explain Oleg's comment.  I don't understand it.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
1234