Add some complexities to Data.List documentation (#15003)

Describe complexity and add an example for `GHC.List.filter`.

2 files changed, 26 insertions, 16 deletions

diff --git a/libraries/base/Data/OldList.hs b/libraries/base/Data/OldList.hs
index 80c6267faa..99ad914ba7 100644
--- a/libraries/base/Data/OldList.hs
+++ b/libraries/base/Data/OldList.hs
@@ -431,8 +431,8 @@ elem_by eq y (x:xs)     =  x `eq` y || elem_by eq y xs
 #endif
 
 
--- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
--- For example,
+-- | /O(n)/. 'delete' @x@ removes the first occurrence of @x@ from its list
+-- argument. For example,
 --
 -- >>> delete 'a' "banana"
 -- "bnana"
@@ -442,7 +442,7 @@ elem_by eq y (x:xs)     =  x `eq` y || elem_by eq y xs
 delete                  :: (Eq a) => a -> [a] -> [a]
 delete                  =  deleteBy (==)
 
--- | The 'deleteBy' function behaves like 'delete', but takes a
+-- | /O(n)/. The 'deleteBy' function behaves like 'delete', but takes a
 -- user-supplied equality predicate.
 --
 -- >>> deleteBy (<=) 4 [1..10]
@@ -618,19 +618,18 @@ mapAccumR f s (x:xs)    =  (s'', y:ys)
                            where (s'',y ) = f s' x
                                  (s', ys) = mapAccumR f s xs
 
--- | The 'insert' function takes an element and a list and inserts the
--- element into the list at the first position where it is less
--- than or equal to the next element.  In particular, if the list
--- is sorted before the call, the result will also be sorted.
--- It is a special case of 'insertBy', which allows the programmer to
--- supply their own comparison function.
+-- | /O(n)/. The 'insert' function takes an element and a list and inserts the
+-- element into the list at the first position where it is less than or equal to
+-- the next element. In particular, if the list is sorted before the call, the
+-- result will also be sorted. It is a special case of 'insertBy', which allows
+-- the programmer to supply their own comparison function.
 --
 -- >>> insert 4 [1,2,3,5,6,7]
 -- [1,2,3,4,5,6,7]
 insert :: Ord a => a -> [a] -> [a]
 insert e ls = insertBy (compare) e ls
 
--- | The non-overloaded version of 'insert'.
+-- | /O(n)/. The non-overloaded version of 'insert'.
 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
 insertBy _   x [] = [x]
 insertBy cmp x ys@(y:ys')
@@ -670,9 +669,14 @@ minimumBy cmp xs        =  foldl1 minBy xs
                                        GT -> y
                                        _  -> x
 
--- | The 'genericLength' function is an overloaded version of 'length'.  In
--- particular, instead of returning an 'Int', it returns any type which is
--- an instance of 'Num'.  It is, however, less efficient than 'length'.
+-- | /O(n)/. The 'genericLength' function is an overloaded version of 'length'.
+-- In particular, instead of returning an 'Int', it returns any type which is an
+-- instance of 'Num'. It is, however, less efficient than 'length'.
+--
+-- >>> genericLength [1, 2, 3] :: Int
+-- 3
+-- >>> genericLength [1, 2, 3] :: Float
+-- 3.0
 genericLength           :: (Num i) => [a] -> i
 {-# NOINLINE [1] genericLength #-}
 genericLength []        =  0
diff --git a/libraries/base/GHC/List.hs b/libraries/base/GHC/List.hs
index 6b86b1fc60..fced32916c 100644
--- a/libraries/base/GHC/List.hs
+++ b/libraries/base/GHC/List.hs
@@ -142,10 +142,13 @@ lengthFB _ r = \ !a -> r (a + 1)
 idLength :: Int -> Int
 idLength = id
 
--- | 'filter', applied to a predicate and a list, returns the list of
+-- | /O(n)/. 'filter', applied to a predicate and a list, returns the list of
 -- those elements that satisfy the predicate; i.e.,
 --
 -- > filter p xs = [ x | x <- xs, p x]
+--
+-- >>> filter odd [1, 2, 3]
+-- [1,3]
 
 {-# NOINLINE [1] filter #-}
 filter :: (a -> Bool) -> [a] -> [a]
@@ -847,11 +850,14 @@ notElem x (y:ys)=  x /= y && notElem x ys
  #-}
 #endif
 
--- | 'lookup' @key assocs@ looks up a key in an association list.
+-- | /O(n)/. 'lookup' @key assocs@ looks up a key in an association list.
+--
+-- >>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]
+-- Just "second"
 lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
 lookup _key []          =  Nothing
 lookup  key ((x,y):xys)
-    | key == x          =  Just y
+    | key == x           =  Just y
     | otherwise         =  lookup key xys
 
 -- | Map a function over a list and concatenate the results.