<p dir="ltr">Er.. that last might be to hard. But Data.IntSet can support its own nub version.</p>
<div class="gmail_quote">On Jan 1, 2015 8:42 AM, "David Feuer" <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir="ltr">I think ordNub in Data.Set, hashNub in Data.HashSet or somewhere, and bitsNub in Data.Bits (for FiniteBits things).</p>
<div class="gmail_quote">On Jul 14, 2013 7:21 AM, "Niklas Hambüchen" <<a href="mailto:mail@nh2.me" target="_blank">mail@nh2.me</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">tldr: nub is abnormally slow, we shouldn't use it, but we do.<br>
<br>
<br>
As you might know, Data.List.nub is O(n²). (*)<br>
<br>
As you might not know, almost *all* practical Haskell projects use it,<br>
and that in places where an Ord instance is given, e.g. happy, Xmonad,<br>
ghc-mod, Agda, darcs, QuickCheck, yesod, shake, Cabal, haddock, and 600<br>
more (see <a href="https://github.com/nh2/haskell-ordnub" target="_blank">https://github.com/nh2/haskell-ordnub</a>).<br>
<br>
I've taken the Ord-based O(n * log n) implementation from yi using a Set:<br>
<br>
  ordNub :: (Ord a) => [a] -> [a]<br>
  ordNub l = go empty l<br>
    where<br>
      go _ []     = []<br>
      go s (x:xs) = if x `member` s then go s xs<br>
                                    else x : go (insert x s) xs<br>
<br>
<br>
and put benchmarks on<br>
<a href="http://htmlpreview.github.io/?https://github.com/nh2/haskell-ordnub/blob/1f0a2c94a/report.html" target="_blank">http://htmlpreview.github.io/?https://github.com/nh2/haskell-ordnub/blob/1f0a2c94a/report.html</a><br>
(compare `nub` vs `ordNub`).<br>
<br>
`ordNub` is not only in a different complexity class, but even seems to<br>
perform better than nub for very small numbers of actually different<br>
list elements (that's the numbers before the benchmark names).<br>
<br>
(The benchmark also shows some other potential problem: Using a state<br>
monad to keep the set instead of a function argument can be up to 20<br>
times slower. Should that happen?)<br>
<br>
What do you think about ordNub?<br>
<br>
I've seen a proposal from 5 years ago about adding a *sort*Nub function<br>
started by Neil, but it just died.<br>
<br>
<br>
(*) The mentioned complexity is for the (very common) worst case, in<br>
which the number of different elements in the list grows with the list<br>
(alias you don't have an N element list with always only 5 different<br>
things inside).<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div>
</blockquote></div>