[Haskell-cafe] ordNub

John Lato jwlato at gmail.com
Tue Jul 16 04:40:54 CEST 2013


On Tue, Jul 16, 2013 at 10:31 AM, Ivan Lazar Miljenovic <
ivan.miljenovic at gmail.com> wrote:

> On 16 July 2013 11:46, John Lato <jwlato at gmail.com> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130716/add4125d/attachment.htm>


More information about the Haskell-Cafe mailing list