title: Why does "nub" have O(n^2) complexity when it could be O(n)?
body: <p>The <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#v:nub" rel="noreferrer"><code>nub</code></a> function from <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html" rel="noreferrer"><code>Data.list</code></a> has a O(n<sup>2</sup>) complexity. It's clear that implementing an O(n) algorithm is doable and not hard. Why doesn't Haskell do it?</p>
  
  <pre>
  nub :: Eq a => [a] -> [a]
  base Data.List
  O(n^2). The nub function removes duplicate elements from a list. In particular,
  it keeps only the first occurrence of each element. (The name nub means
  `essence'.) It is a special case of nubBy, which allows the programmer to supply
  their own equality test. 
  </pre>