Oops sorry I guess my point wasn't clear. Why ord based when hashable is faster? Then there's no reason this has to be in base, it can just be a free function in Data.HashSet. If stability is a concern then there's a way to easily account for that using HashMap. - Clark On Jul 14, 2013 7:48 AM, "Niklas Hambüchen" wrote:

One of my main points is:

Should we not add such a function (ord-based, same output as nub, stable, no sorting) to base?

As the package counting shows, if we don't offer an alternative, people obviously use it, and not to our benefit.

(Not to say it this way: We could make the Haskell world fast with smarter fusion, strictness analysis and LLVM backends. Or we could stop using quadratic algorithms.)

Apologies. I was being lazy. Here's a stable version: import qualified Data.HashSet as S hashNub :: (Ord a) => [a] -> [a] hashNub l = go S.empty l where go _ [] = [] go s (x:xs) = if x `S.member` s then go s xs else x : go (S.insert x s) xs Which, again, will probably be faster than the one using Ord, and I can't think of any cases where I'd want the one using Ord instead. I may just not be creative enough, though. - Clark On Mon, Jul 15, 2013 at 12:46 AM, Brandon Allbery wrote:

On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel wrote:

...

Oops sorry I guess my point wasn't clear.

Why ord based when hashable is faster? Then there's no reason this has to be in base, it can just be a

Did the point about "stable" fly overhead?

-- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

On 16 July 2013 11:46, John Lato wrote:

In my tests, using unordered-containers was slightly slower than using Ord, although as the number of repeated elements grows unordered-containers appears to have an advantage. I'm sure the relative costs of comparison vs hashing would affect this also. But both are dramatically better than the current nub.

Has anyone looked at Bart's patches to see how difficult it would be to apply them (or re-write them)?

If I understand correctly, this function is proposed to be added to Data.List which lives in base... but the proposals here are about using either Sets from containers or HashSet from unordered-containers; I thought base wasn't supposed to depend on any other package :/

On Mon, Jul 15, 2013 at 8:43 PM, Clark Gaebel wrote:

...

Apologies. I was being lazy. Here's a stable version:

import qualified Data.HashSet as S

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

Which, again, will probably be faster than the one using Ord, and I can't think of any cases where I'd want the one using Ord instead. I may just not be creative enough, though.

- Clark

On Mon, Jul 15, 2013 at 12:46 AM, Brandon Allbery wrote:

...

On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel wrote:

...

Oops sorry I guess my point wasn't clear.

Why ord based when hashable is faster? Then there's no reason this has to be in base, it can just be a

Did the point about "stable" fly overhead?

-- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

I'm procrastinating something else, so I wrote the patch to unordered-containers. Feel free to comment on the github link: https://github.com/tibbe/unordered-containers/pull/67 I'm still against having an Ord version, since my intuition tells me that hash-based data structures are faster than ordered ones. Someone else can write the patch, though! 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? Regards, - Clark On Mon, Jul 15, 2013 at 10:40 PM, John Lato wrote:

On Tue, Jul 16, 2013 at 10:31 AM, Ivan Lazar Miljenovic wrote:

...

On 16 July 2013 11:46, John Lato wrote:

...

In my tests, using unordered-containers was slightly slower than using Ord, although as the number of repeated elements grows unordered-containers appears to have an advantage. I'm sure the relative costs of comparison vs hashing would affect this also. But both are dramatically better than the current nub.

Has anyone looked at Bart's patches to see how difficult it would be to apply them (or re-write them)?

If I understand correctly, this function is proposed to be added to Data.List which lives in base... but the proposals here are about using either Sets from containers or HashSet from unordered-containers; I thought base wasn't supposed to depend on any other package :/

That was one of the points up for discussion: is it worth including a subset of Set functionality to enable a much better nub in base? Is it even worth having Data.List.nub if it has quadratic complexity?

As an alternative, Bart's proposal was for both including ordNub in containers and an improved nub (with no dependencies outside base) in Data.List. Unfortunately the patches are quite old (darcs format), and I don't know how they'd apply to the current situation.

nubBy is a very good suggestion. Added! Regarding good hash functions: if your data structure is algebraic, you can derive generic and Hashable will give you a pretty good hash function:

data ADT a = C0 Int String | C1 [a] deriving Generic

instance Hashable a => Hashable (ADT a)

It's magic! - Clark On Mon, Jul 15, 2013 at 11:35 PM, Richard A. O'Keefe wrote:

On 16/07/2013, at 3:21 PM, Clark Gaebel wrote:

...

I'm still against having an Ord version, since my intuition tells me that hash-based data structures are faster than ordered ones.

There are at least four different things that "an Ord version" might mean:

- first sort a list, then eliminate duplicates - sort a list eliminating duplicates stably as you go (think 'merge sort', using 'union' instead of 'merge') - build a balanced tree set as you go - having a list that is already sorted, use that to eliminated duplicates cheaply.

These things have different costs. For example, if there are N elements of which U are unique, the first as O(N.log N) cost, the third has O(N.log U) cost, and the fourth has O(N) cost.

What I want is more often ordNubBy than ordNub, though.

...

Someone else can write the patch, though!

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?

Since Ord has Eq as a superclass, and since 0 is a functionally correct hash value for anything, if you can implement Ord you can obviously implement Hashable/Eq. Whether it is *useful* to do so is another question.

It turns out that it _is_ possible to define good quality hash functions on sets, but most code in the field to do so is pretty bad. (Just a modular sum or exclusive or.)

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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

On 16 July 2013 10:31, Ivan Lazar Miljenovic wrote:

On 16 July 2013 11:46, John Lato wrote:

...

In my tests, using unordered-containers was slightly slower than using Ord, although as the number of repeated elements grows unordered-containers appears to have an advantage. I'm sure the relative costs of comparison vs hashing would affect this also. But both are dramatically better than the current nub.

Has anyone looked at Bart's patches to see how difficult it would be to apply them (or re-write them)?

If I understand correctly, this function is proposed to be added to Data.List which lives in base... but the proposals here are about using either Sets from containers or HashSet from unordered-containers; I thought base wasn't supposed to depend on any other package :/

This discussion (on -cafe@) is just about what course of action to take; adding such functions to containers or unordered-containers would not require a libraries@ proposal. Conrad.

...

On Mon, Jul 15, 2013 at 8:43 PM, Clark Gaebel wrote:

...

Apologies. I was being lazy. Here's a stable version:

import qualified Data.HashSet as S

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

Which, again, will probably be faster than the one using Ord, and I can't think of any cases where I'd want the one using Ord instead. I may just not be creative enough, though.

- Clark

On Mon, Jul 15, 2013 at 12:46 AM, Brandon Allbery wrote:

...

On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel wrote:

...

Oops sorry I guess my point wasn't clear.

Why ord based when hashable is faster? Then there's no reason this has to be in base, it can just be a

Did the point about "stable" fly overhead?

-- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Francesco Mazzoli writes:

...

import qualified Data.HashSet as S

nub :: Hashable a => [a] -> [a] nub = S.toList . S.fromList

Well, the above is not stable while Niklas’ is. But I guess that’s not the point of your message :).

We could also implement Data.BloomFilter.nub, which removes equal elements probabilistically (with a small but non-zero chance of removing some unique elements) :-) -k -- If I haven't seen further, it is by standing in the footprints of giants

On 15 July 2013 09:54, Joey Adams wrote:

On Sun, Jul 14, 2013 at 7:31 AM, Clark Gaebel wrote:

...

Similarly, I've always used:

import qualified Data.HashSet as S

nub :: Hashable a => [a] -> [a] nub = S.toList . S.fromList

And i can't think of any type which i can't write a Hashable instance, so this is extremely practical.

This won't yield results lazily (e.g. nub (repeat 'x') = _|_ instead of 'x' : _|_), but Niklas' ordNub will. His ordNub can be translated directly to HashSet and still have the stability and laziness properties.

A difficulty with putting ordNub in Data.List is that it depends on containers, which is outside of the base package. Some options:

* Move the implementation of Set to base.

* Implement a lean version of Set in base that only provides 'insert' and 'member'.

* Define ordNub in Data.Set instead.

Adding a Hashable-based nub to base would be even more problematic, since you'd need Hashable in base.

Right, I suggest the following community course of action: 1a) add ordNub to Data.Set 1b) add ordNub to Data.Hashable (1 day) 2) make a libraries@ proposal to include a stripped-down Data.Set-like balanced binary tree implementation to base. (2 weeks) 3) bikeshed about the name, eg.: * is "nub" really intuitive? how about "uniq", like in perl/ruby/underscore.js? * but "uniq" in unix only removes _adjacent_ duplicates, confusing! * how about "distinct"? "sole"? "unique"? "azygous"? (7 weeks) 4) Failing consensus on technical grounds (that the stripped-down Data.Set implementation is overkill for one library function), agree that anyone who really cares should just use the version from containers or hashable. Only newbs and textbook authors actually use base anyway, and it's impossible to change the language definition. Prelude will continue to fulfil its role of avoiding success at all costs, quadratic or otherwise. (Please, let's have both 1a and 1b :) Conrad.

I would like to come back to the original question: How can ordNub be added to base? I guess we agree that Data.List is the right module for a function of type Ord a => [a] -> [a], but this introduces * a cyclic dependency between Data.List and Data.Set * a base dependency on containers. What is the right way to go with that? Should ordNub be introduced as part of Data.Set, as Conrad suggested? It does not really have anything to do with Set, apart from being implemented with it. On 14/07/13 14:12, Roman Cheplyaka wrote:

Something like that should definitely be included in Data.List. Thanks for working on it.

Roman

On 12/10/13 20:43, Anthony Cowley wrote:

I think nub's behavior is rather set-related, so I don't really understand the objection to putting it in Data.Set.

In sets, the order does not matter, while for nub it does. nub :: Eq a => [a] -> [a] ordNub :: Ord a => [a] -> [a] both do not mention Set, and the fact that Set is used inside my proposed ordNub implementation is a detail not visible to the caller. That's why it looks like a Data.List function to me.

On 13/10/13 21:42, AntC wrote:

...

Niklas Hambüchen writes:

In sets, the order does not matter, while for nub it does.

Let's be careful here!. Niklas, when you say "order", do you mean: * the _ordering_ from the Ord instance? Or * the relative sequence of elements in the list?

...

... the fact that Set is used inside my proposed ordNub implementation is a detail not visible to the caller.

If you use the Set library, that fact may be very visible! Because Set re-sequences the whole list, as per its Ord instance.

But List.nub preserves the list sequence (except for omitting duplicates).

I mean *exactly* what you say here. ordNub behaves has the same behaviour as nub, while (Set.toList . Set.fromList) doesn't.

[BTW I am still less than convinced that overall a Set-based ordNub is significantly more efficient. I suspect it depends on how big is your list.]

What do you mean? ordNub is clearly in a different complexity class, and the benchmarks that I provided show not only this, but also that ordNub is *always* faster than nub, even for singleton lists.

On 14/10/13 03:20, AntC wrote:

Thanks Niklas, I hadn't spotted those benchmarks back in July.

No worries :)

I'm surprised at that result for singletons (and for very small numbers of elements which are in fact each different).

I think one of the main reasons for the performance difference is that a list node and a Set binary tree node have pretty much the same performance, with the difference that in http://hackage.haskell.org/package/containers-0.5.2.1/docs/src/Data-Set-Base... data Set a = Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a) | Tip there are strictness and unpack annotations, while for data [a] = [] | a : [a] -- pseudo syntax there are not. Good for us in this case, I guess.

It seems to me that for small numbers, the Set-based approach still requires comparing each element to each other.

This I don't understand.

Then here's a further possible optimisation, instead of making separate calls to `member` and `insert`:

This I understand again. Where do you get insert' from? containers doesn't seem to have it. Do you suggest adding it? Niklas

On Sun, Oct 13, 2013 at 6:25 PM, Niklas Hambüchen wrote:

ordNub behaves has the same behaviour as nub, while (Set.toList . Set.fromList) doesn't.

Perhaps you mean that they produce exactly the same output when fully evaluated. But I doubt that their behavior is *exactly* the same in every aspect. Given the differences in strictness between sets and lists, can you prove that nub and nubOrd have *exactly* the same strictness properties in every possible case?

...ordNub is *always* faster than nub, even for singleton lists.

This is also a claim that I doubt. You say that you tested the case of singletons. How about this: 2 : replicate 100000 1 ++ [3] Well, you could optimize for that by having nubOrd squeeze runs of of equal elements in the input. But then how about something like this: [3,2,1] ++ take 100000 (cycle [3,2,1]) ++ [4] Or variations on that, cycling some other fairly small number of elements. Set containers must do extra comparisons, whereas the of cost running down the first few hundred elements of a linked list (as long as the compiler fuses the iteration down to a tight loop in the output code and you remain within the cache) is near zero. How could nubOrd be as fast as ord in these kinds of cases? I'm not saying that it wouldn't be worthwhile to add a standard well-optimized implementation of nubOrd somewhere. But nub is a very useful function. The only advantage of nubOrd is for very large lists where the complexity advantage overtakes the excellent constants of nub to provide better speed. In practice, the cases where that's worthwhile are unusual. I rarely bother with nubOrd over nub. -Yitz

On 16/10/13 17:46, Yitzchak Gale wrote:

On Sun, Oct 13, 2013 at 6:25 PM, Niklas Hambüchen wrote:

...

ordNub behaves has the same behaviour as nub, while (Set.toList . Set.fromList) doesn't.

Perhaps you mean that they produce exactly the same output when fully evaluated. But I doubt that their behavior is *exactly* the same in every aspect. Given the differences in strictness between sets and lists, can you prove that nub and nubOrd have *exactly* the same strictness properties in every possible case?

Yes. The elements are are evaluated in the same order as in `nub`. We can see that by comparing the implementations. If you have objects that need not be fully evaluated to use (==) on them, and need not fully evaluated *in a different way* when using `compare` on them, then of course the strictness properties are different. That is why one function has "Eq a =>" and the other one "Ord a =>" at the front.

...

...ordNub is *always* faster than nub, even for singleton lists.

This is also a claim that I doubt. You say that you tested the case of singletons. How about this:

2 : replicate 100000 1 ++ [3]

Well, you could optimize for that by having nubOrd squeeze runs of of equal elements in the input. But then how about something like this:

[3,2,1] ++ take 100000 (cycle [3,2,1]) ++ [4]

Or variations on that, cycling some other fairly small number of elements. Set containers must do extra comparisons, whereas the of cost running down the first few hundred elements of a linked list (as long as the compiler fuses the iteration down to a tight loop in the output code and you remain within the cache) is near zero. How could nubOrd be as fast as ord in these kinds of cases?

I make the following, really cool proposal: * You add your test cases that you just mentioned to the benchmark list in "ordnub.hs" * run `cabal build` * run `dist/build/ordnub/ordnub -o report.html`. Then you will see that ordNub is, indeed, faster.

(as long as the compiler fuses the iteration down to a tight loop in the output code and you remain within the cache)

Even though a list is conceptually simpler than a set, a list node and a set node are not that different (as I explained in the last email). Both have a content and a pointer to the next node. The only difference is that the Set node is optimised with strictness and unboxing, and the list one is not.

The only advantage of nubOrd is for very large lists where the complexity advantage overtakes the excellent constants of nub to provide better speed.

Sorry, I think this is absolutely invented. What "excellent constants" do you mean? How large are "very large lists"? I find lists of length 1000 a very common case. An `n log2 n` algorithm is already 100 times faster on those than an n² one. I do not dispute that there exist n² algorithms that are faster than others with better complexity for small inputs. nub is not one of them.

On 17/10/13 17:56, Yitzchak Gale wrote:

Let's get back to focusing on that.

Agreed. My main question is still: 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?

On Fri, Oct 18, 2013 at 3:03 PM, Andreas Abel 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? ;)

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.

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 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Fri, Oct 18, 2013 at 3:13 PM, David Thomas 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

Hey Jason, would you mind giving a short idea of what the point of Bird's implementation is / from what properties it is derived? Also, running the QuickCheck tests you added, it doesn't give the same output (order) as nub. On 15/07/13 13:26, Jason Dagit wrote:

Richard Bird has a book, "Pearls of Functional Algorithm Design" that is meant to teach a form of deriving algorithms from the properties we ask of them. In this book, he gives a possible derivation of ordNub, simply called nub in the book, following the methodology he is teaching. He notes in the text that this derivation feels more complicated than it ought.

Here is his version: http://lpaste.net/87625

I just sent you a pull request to add that one and S.toList . S.fromList that was suggested in this thread. I don't think those two implementations are faster than the others but it's nice to have them for completeness.

Jason

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" 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" 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/1f0... (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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe