From b3226616beaa8cd4d3289b8a9d4bb0a9b8936f8e Mon Sep 17 00:00:00 2001 From: Andrei Borzenkov Date: Sun, 30 Apr 2023 18:45:39 +0400 Subject: 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 --- libraries/base/Data/OldList.hs | 12 +++++++++--- 1 file 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 (==) -- cgit v1.2.1