At Sun, 28 Sep 2008 11:05:42 -0700, Alexander Dunlap wrote:

This seems like a good idea but it's kind of strange to have three different exposed versions of nub. Would it be possible to hide them, hide the StopList typeclass and use {-# RULES #-} pragmas to use the faster versions when possible?

The RULES pragma is GHC-specific. Would it make sense to export the faster versions so that people targeting alternative compilers could use them? Additionally, I think RULES only take effect if you are compiling with optimizations, but not if you just load the files into GHCi. I have written programs which run fine with nubOrd but are unacceptable with nubEq. So, I would certainly want the option to force the use of nubOrd at all times, rather than rely on the compiler to sometimes make the required optimization for me. j.

Alexander Dunlap wrote:

This seems like a good idea but it's kind of strange to have three different exposed versions of nub. Would it be possible to hide them, hide the StopList typeclass and use {-# RULES #-} pragmas to use the faster versions when possible?

I don't think that using RULES pragmas is a good solution to the problem. Instead, there's an old-fashioned way to use the name nub for all cases: make it a member of the Eq typeclass! class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool nub :: [a] -> [a] nub = -- default definition Now, nub can be specialized at will. Changing the default definition of nub to use Set if we have an Ord class is tricky, though. Basically, we would need this proposal: http://www.haskell.org/haskellwiki/Class_system_extension_proposal#Allowing_... Does it have a formal definition yet and guarantees that it works? In any case, consider nub to be another example for the usefulness of this proposal. Regards, apfelmus

On 2008 Sep 29, at 18:55, Alexander Dunlap wrote:

On Mon, Sep 29, 2008 at 9:40 AM, apfelmus wrote:

...

Alexander Dunlap wrote:

...

This seems like a good idea but it's kind of strange to have three different exposed versions of nub. Would it be possible to hide them, hide the StopList typeclass and use {-# RULES #-} pragmas to use the faster versions when possible?

I don't think that using RULES pragmas is a good solution to the problem.

Why not? I thought that was the major purpose of RULES - to implement transformations that don't affect semantics. It seems silly to clutter

So what of yhc, nhc98, jhc? ghc is not the be-all and end-all of Haskell. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

On 2008 Sep 29, at 19:40, Alexander Dunlap wrote:

On Mon, Sep 29, 2008 at 4:06 PM, Brandon S. Allbery KF8NH wrote:

...

On 2008 Sep 29, at 18:55, Alexander Dunlap wrote:

...

On Mon, Sep 29, 2008 at 9:40 AM, apfelmus wrote:

...

Alexander Dunlap wrote:

...

This seems like a good idea but it's kind of strange to have three different exposed versions of nub. Would it be possible to hide them, hide the StopList typeclass and use {-# RULES #-} pragmas to use the faster versions when possible?

I don't think that using RULES pragmas is a good solution to the problem.

Why not? I thought that was the major purpose of RULES - to implement transformations that don't affect semantics. It seems silly to clutter

So what of yhc, nhc98, jhc? ghc is not the be-all and end-all of Haskell.

Well, yes, but presumably different compilers could optimize in different ways. (Perhaps they could use some class behind the scenes, or their own optimizing mechanism?) My point is that we shouldn't have multiple exposed functions for _exactly_ the same semantic operation.

Tell it to the Prelude. (^), (^^), (**) anyone? -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

Alexander Dunlap wrote:

apfelmus wrote:

...

Alexander Dunlap wrote:

...

This seems like a good idea but it's kind of strange to have three different exposed versions of nub. Would it be possible to hide them, hide the StopList typeclass and use {-# RULES #-} pragmas to use the faster versions when possible?

I don't think that using RULES pragmas is a good solution to the problem.

Why not? I thought that was the major purpose of RULES - to implement transformations that don't affect semantics. It seems silly to clutter up classes with extra functions just for efficiency or to have to change programs every time the types change. The fact that RULES don't work in GHCi is admittedly a downside; is there any plan to change that?

Why not type classes? :) Their major purpose is to overload a value at different types, like nub :: Eq a => [a] -> [a] nub :: Ord a => [a] -> [a] nub :: [Int] -> [Int] and that's exactly what we're trying to do. Adding nub with a default definition is a two-line change to the definition of the Eq class and it's completely backwards compatible, no existing program needs to be changed. But as said, Haskell98 is currently unable to specialize nub for a general Ord context, we would need some extension about superclasses for that. But this extension is desirable for Functor, Monad and Applicative anyway. The argument that the semantics of the different nubs are all the same does have merits, but we're already putting functions into the class for efficiency reasons, like (/=) and (==) (>),(>=) and compare (/) and recip tan and sin,cos (>>) and (>>=) etc. Regards, apfelmus

On Tuesday 30 September 2008 1:46:23 am Bart Massey wrote:

Just thought I'd post a note to thank you all for the informative and interesting discussion of my proposal so far. Thanks much to all who are helping to figure out what we should do!

One additional issue: Data.List is in the base package. Data.Set is in containers. Data.Set also imports Data.List, so using sets in the latter creates a circular dependency. The latter isn't as big a deal, but circular package dependences sounds like a problem to me (as I imagine containers depends on base). Something else to discuss. :) -- Dan P.S.: On point 4, I'd probably lean away from StopList as well. Requiring fundeps seems undesirable for a rather core, H98-esque module.

On Tuesday 30 September 2008 12:24:29 pm Bart Massey wrote:

You said that the circular module dependency is "not as big a deal"? I'm not getting why...it seems pretty serious to me. Is there some refactoring that makes it go away without doing huge violence to the existing structure? I mean, we could split the Data.List module up into pieces to break the dependency, but that doesn't seem like it's going to happen...

Well, in GHC, at least, there are ways to handle mutually recursive modules. I've never encountered the need myself, so I don't know the specifics, but it involves making an hs-boot file or something of the sort. Of course, that only works if they're in the same package, I suspect, so maybe it is a big problem. :) I don't know how any other compilers handle such things.

I'd completely forgotten about the recent package split of containers and base. No idea what to do there. I suppose at worst we could have a Data.Nubs module, but that just seems silly, as all it's going to export at this point is nubOrd and (StopList-less) nubWith. Besides, what package do we put it in? Do we now have container, base, and nubs?? :-) :-)

(In general, it seems like this sort of thing is going to become a problem as the libraries grow. I note, for example, that Data.Function is in base, which makes putting any reasonable implementation of transitiveClosure in there pretty hard for this same reason.)

Any suggestions from anyone about how to proceed? Or are we just done at this point? So close...

Lists are a container, so I guess it'd be nice if Data.List could be moved to containers, but I think the prelude imports and uses stuff from it, and you're not going to move that. nubOrd could be stuck in Data.Set, but that's kind of an odd place for it. Other than that, I'm stumped. -- Dan

Bart Massey writes:

Any suggestions from anyone about how to proceed? Or are we just done at this point? So close...

OK, I've got a new version of nubOrd together. This one is just nubOrd, no nubWith, no nubInt, nothing fancy. There's two variants, nubOrd' and nubOrd''. The latter gets a slight performance win by omitting some work that would preserve the order of output with respect to nub. The basic strategy of nubOrd' is to pull off a prefix l of the input list as long as the current stoplist s, nubSort l, merge l with s to get a new stoplist s', use s in a merge step to filter l, then sort the remainder of l back to the original order. Finally, the resulting l' and s' are prepended to a recursive call on the rest of the list. nubOrd' has roughly the same time complexity as the set-based nubOrd did. This is because each step of nubOrd requires log m time to search the stoplist, and each collection of steps in nubOrd' requires amortized log m time for the sorts. Let's do some side by side comparison: nub nubSort nubOrd nubOrd' nubOrd'' laziness full no full spine spine worst-case O(mn) O(n log n) O(n log m) O(n log m) O(n log m) complexity (m symbols, length n) relative 1x 50x 1.1x 5x 5x runtime with m = 1 absolute 84s 0.14s 0.16s 0.35s 0.21s runtime with m = n = 10^5 dependencies no no Data.Set no no outside (containers) Data.List outputs in yes no yes yes no order of first mention code small tiny smallish wtf wtf-lite complexity This table suggests to me that nubOrd' is viable, assuming spine-laziness is sufficient. It solves the time problems of nub and nubSort, solves the dependency problem of nubOrd, and preserves the order of its outputs. I don't like the 5x slowdown for small m, or the non-laziness on elements, but I guess I am willing to take them to get the other stuff. Maybe someone or the compiler can do some optimization later. The code for nubOrd', in all its hideous glory, is at the end of this post. Comments, corrections and improvements welcome. Bart Massey bart <at> cs.pdx.edu merge :: Ord e => [e] -> [e] -> [e] merge l1 [] = l1 merge [] l2 = l2 merge l1@(e1 : e1s) l2@(e2 : e2s) | e1 < e2 = e1 : merge e1s l2 | e1 > e2 = e2 : merge l1 e2s | otherwise = merge l1 e2s nubOrd' :: Ord e => [e] -> [e] nubOrd' [] = [] nubOrd' (e : es) = e : go [e] es where go _ [] = [] go s l = l1' ++ go s' l2 where (l1, l2) = splitAt (length s) l curl = filterDups $ sort $ zip l1 ([1..] :: [Integer]) s' = merge s (map fst curl) l1' = map fst $ sortBy flipcmp $ stopMerge s curl (a, b) `flipcmp` (c, d) = (b, a) `compare` (d, c) filterDups [] = [] filterDups (s1@(e1, _) : (e2, _) : ss) | e1 == e2 = filterDups (s1 : ss) filterDups (s1 : ss) = s1 : filterDups ss stopMerge _ [] = [] stopMerge [] m2 = m2 stopMerge m1@(e1 : e1s) m2@(s2@(e2, _) : s2s) | e1 < e2 = stopMerge e1s m2 | e1 > e2 = s2 : stopMerge m1 s2s | otherwise = stopMerge m1 s2s

Bart Massey wrote:

2) Stick (non-StopList) nubWith in Data.List. Stick nubOrd in Data.Set, implemented using nubWith.

Advantages: Provides a highly efficient, fully lazy nubOrd. Provides nubWith. Reasonable implementation.

Disadvantages: Sticking nubOrd in Data.Set is weird.

My score: 4/5

indeed a weird location, but only an import-line needs to change if someone invents a super-duper nubOrd that's even faster but depends on more libraries. Would it be better to stick it in a new module e.g. Data.Set.Nub? -Isaac

On Sat, Oct 4, 2008 at 3:26 AM, Bart Massey wrote:

I need to know what the community wants me to do to close out my proposal to add nubOrd to the standard libraries. After ruling out a lot of marginal choices, I guess I see three leading alternatives, all of which have negatives. I'd love to have some feedback on these so I can start thinking about other things.

I realize I'm coming into this discussion late, but has anyone surveyed existing Haskell code to see how often nub is used? How many of those cases require the specific functionality of nub, as opposed to something like "Set.toList . Set.fromList"? I may be misjudging things, but I can't imagine it's often enough to justify three or more implementations in the standard library. If there are really a lot of cases where people need a collection that (1) has no duplicates, and (2) preserves an arbitrary order of elements, maybe we'd be better off designing a data structure specifically for that. -- Dave Menendez http://www.eyrie.org/~zednenem/

On Mon, Oct 6, 2008 at 12:13 AM, Brandon S. Allbery KF8NH wrote:

On 2008 Oct 6, at 0:07, David Menendez wrote:

...

On Sat, Oct 4, 2008 at 3:26 AM, Bart Massey wrote:

...

I need to know what the community wants me to do to close out my proposal to add nubOrd to the standard libraries. After ruling out a lot of marginal choices, I guess I see three leading alternatives, all of which have negatives. I'd love to have some feedback on these so I can start thinking about other things.

I realize I'm coming into this discussion late, but has anyone surveyed existing Haskell code to see how often nub is used? How many

It's not so much that nub is used often. it's that it's often *reimplemented*.

By people who *need* a faster nub, or by people who figured they could make nub faster by changing the type? How often does someone need the exact behavior of nub, instead of something faster like "Set.toList . Set.fromList"? All this effort to optimize a seemingly obscure function feels like overkill. We might be better off just adding a note to the documentation of nub suggesting that people use Data.Set instead. (We can't get rid of it, because it's in the H98 Report.) In any case, my only objection is to complicating the standard libraries. If someone wants to post a faster nub to Hackage, that's fine.

...

If there are really a lot of cases where people need a collection that (1) has no duplicates, and (2) preserves an arbitrary order of elements, maybe we'd be better off designing a data structure specifically for that.

Feel free to contribute. Make sure it supports the whole spectrum of list operations, including list comprehensions.

Demonstrate the need, and I'd be happy to contribute. -- Dave Menendez http://www.eyrie.org/~zednenem/

Bart Massey wrote:

2) Stick (non-StopList) nubWith in Data.List. Stick nubOrd in Data.Set, implemented using nubWith.

Advantages: Provides a highly efficient, fully lazy nubOrd. Provides nubWith. Reasonable implementation.

Disadvantages: Sticking nubOrd in Data.Set is weird.

My score: 4/5

(2) seems reasonable to me, as long as we improve the documentation for nub to point out the quadratic complexity and direct users who want a faster version to Data.Set.nubOrd. Cheers, Simon

Johannes Waldmann writes:

...

The StopList class [...]

BTW, that is a horrible name for what is simply a *set* (look at the methods you wrote: empty, insert, member).

I originally called the typeclass Set, but it isn't, so I changed it. It omits some Set functionality. One couldn't write an implementation of union or intersect with it, because there's no way to enumerate its elements. In any case, it's moot, because we're ditching StopLists. :-)

The design problem here is that you don't want to use Data.Set because currently it is an implementation, not an interface.

If by that you mean that it would be nice if Set was a typeclass, and there was a [] implementation as well as the current OrdSet implementation, I tend to agree. C'est la vie.

On Tue, Sep 30, 2008 at 11:58:07AM -0400, David Roundy wrote:

On Tue, Sep 30, 2008 at 1:46 AM, Bart Massey wrote:

...

Note, though, that one can easily imagine a nubAscii that is linear-time rather than the n log n time of nubOrd / nubInt, using a small bit vector to track the Chars. Certainly nubBool has this property. Hmm. What's our criterion for when the performance difference between two functions constitutes a practical semantic difference? I'm claiming it's asymptotic complexity class, in which case (a) we should probably figure out how to expose some kind of nubFinite. Or we could just take the position that in the vast universe of possible functions, our library cannot provide them all. In which case (1b) nubWith is back in. I guess I tend toward (1b).

Actually, the asymptotic complexity (measured in terms of list length) of nubOrd is identical to the asymptotic complexity of nubAscii, nubBool or nubFinite. They differ by a constant factor of the log(# possible data values).

Incidentally, for data types with finite value ranges, nub itself isn't bad, as it'd just O(n * # of values present). So, for instance, nub on a list of Bool is likely to be faster than nubOrd on a list of bools, and it's certainly O(n)... I just ran a timing, and nub takes about as long as length does. David

I think that the easiest way to think about the asymptotic complexity of the nub* functions is in terms of the length n of the input list and the number of unique elements m in that list, as I did in a previous posting. My original point in this thread, which I stated badly, is this: Since array access is constant time, one can imagine an implementation nubIx that has O(n) worst-case time on any Ix datatype, regardless of m. This contrasts with the O(mn) complexity of nub and the O(n log m) complexity of nubOrd on values of type Ix. It is true that for any fixed m any nub* is O(n), but IMHO this fact is a bit misleading; we probably want to think about the asymptotic complexity in m as well as n to get a clear picture of what's going on. Bart Massey bart <at> cs.pdx.edu