Improved documentation for the Data.OldList.nub function

There was recomentation to use map head . group . sort instead of nub
function, but containers library has more suitable and efficient
analogue

1 files changed, 9 insertions, 3 deletions

diff --git a/libraries/base/Data/OldList.hs b/libraries/base/Data/OldList.hs
index cda19cb650..34935782cf 100644
--- a/libraries/base/Data/OldList.hs
+++ b/libraries/base/Data/OldList.hs
@@ -448,10 +448,16 @@ isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
 -- >>> nub [1,2,3,4,3,2,1,2,4,3,5]
 -- [1,2,3,4,5]
 --
--- If the order of outputs does not matter and there exists @instance Ord a@,
--- it's faster to use
+-- If there exists @instance Ord a@, it's faster to use `nubOrd` from the `containers` package
+-- ([link to the latest online documentation](https://hackage.haskell.org/package/containers/docs/Data-Containers-ListUtils.html#v:nubOrd)),
+-- which takes only \(\mathcal{O}(n \log d)\) time where `d` is the number of
+-- distinct elements in the list.
+--
+-- Another approach to speed up 'nub' is to use
 -- 'map' @Data.List.NonEmpty.@'Data.List.NonEmpty.head' . @Data.List.NonEmpty.@'Data.List.NonEmpty.group' . 'sort',
--- which takes only \(\mathcal{O}(n \log n)\) time.
+-- which takes \(\mathcal{O}(n \log n)\) time, requires @instance Ord a@ and doesn't
+-- preserve the order.
+
 --
 nub                     :: (Eq a) => [a] -> [a]
 nub                     =  nubBy (==)