<p>Similarly, I&#39;ve always used:</p>
<p>import qualified Data.HashSet as S</p>
<p>nub :: Hashable a =&gt; [a] -&gt; [a]<br>
nub = S.toList . S.fromList</p>
<p>And i can&#39;t think of any type which i can&#39;t write a Hashable instance, so this is extremely practical.</p>
<div class="gmail_quote">On Jul 14, 2013 7:24 AM, &quot;Niklas Hambüchen&quot; &lt;<a href="mailto:mail@nh2.me">mail@nh2.me</a>&gt; 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&#39;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&#39;ve taken the Ord-based O(n * log n) implementation from yi using a Set:<br>
<br>
  ordNub :: (Ord a) =&gt; [a] -&gt; [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&#39;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&#39;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&#39;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">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>