<commit_before>ordnub
======

Data.List.nub is O(n²). This one is O(n log n) by requiring an Ord instance.

* Also contains a benchmark (`report.html`) that shows that `ordNub` apparently is faster than `nub` in *all* cases.

* `PACKAGES_USING_NUB.txt` contains all packages which use `nub` (made with a quick grep).
It's not the most accurate since some packages define their own `nub`, but that's a minority.

**This thing here is not a library.** It is a benchmark suite. [View results here](http://htmlpreview.github.io/?https://github.com/nh2/haskell-ordnub/blob/master/report.html).

Don't use nub
-------------

If you are looking for a fast `ordNub` function to use in your code, you can use:

```haskell
import qualified Data.Set as Set

ordNub :: (Ord a) => [a] -> [a]
ordNub l = go Set.empty l
  where
    go _ [] = []
    go s (x:xs) = if x `Set.member` s then go s xs
                                      else x : go (Set.insert x s) xs
```

### Other Data.List functions you NEVER want to use

`\\`, `union`, `intersect`<commit_msg>README: Add note<commit_after>ordnub
======

Data.List.nub is O(n²). This one is O(n log n) by requiring an Ord instance.

* Also contains a benchmark (`report.html`) that shows that `ordNub` apparently is faster than `nub` in *all* cases.

* `PACKAGES_USING_NUB.txt` contains all packages which use `nub` (made with a quick grep).
It's not the most accurate since some packages define their own `nub`, but that's a minority.

**This thing here is not a library.** It is a benchmark suite. [View results here](http://htmlpreview.github.io/?https://github.com/nh2/haskell-ordnub/blob/master/report.html).

Don't use nub
-------------

If you are looking for a fast `ordNub` function to use in your code, you can use:

```haskell
import qualified Data.Set as Set

ordNub :: (Ord a) => [a] -> [a]
ordNub l = go Set.empty l
  where
    go _ [] = []
    go s (x:xs) = if x `Set.member` s then go s xs
                                      else x : go (Set.insert x s) xs
```

### Other Data.List functions you NEVER want to use

`\\`, `union`, `intersect`

Also be aware that they don't work like sets. For example:

```
> [1,1,2] \\ [1]
[1,2]

> union [1,2,3,1] [1,4]
[1,2,3,1,4]
```
{'fraction_non_alphanumeric': 0.14510332434860737, 'fraction_numerical': 0.008535489667565139, 'mean_word_length': 2.9910394265232974, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 9, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3643808', 'n_tokens_mistral': 785, 'n_tokens_neox': 744, 'n_words': 301}