ghc/lib/required/List.lhs

   1 %
   2 % (c) The AQUA Project, Glasgow University, 1994-1996
   3 %
   4
   5 \section[List]{Module @Lhar@}
   6
   7 \begin{code}
   8 module List (
   9     delete, deleteBy, (\\), deleteFirsts, deleteFirstsBy,
  10     elemBy, notElemBy, lookupBy, maximumBy, minimumBy,
  11     nub, nubBy, partition, sums, products, transpose,
  12     zip4, zip5, zip6, zip7,
  13     zipWith4, zipWith5, zipWith6, zipWith7,
  14     unzip4, unzip5, unzip6, unzip7,
  15     genericLength, genericDrop, genericTake, genericSplitAt,
  16     genericReplicate,
  17     elemIndex, elemIndexBy, intersperse, group, groupBy,
  18     mapAccumL, mapAccumR,
  19     inits, tails, subsequences, permutations,
  20     union, intersect
  21   ) where
  22
  23 import Prelude
  24 \end{code}
  25
  26 %*********************************************************
  27 %*                                                      *
  28 \subsection{List functions}
  29 %*                                                      *
  30 %*********************************************************
  31
  32 \begin{code}
  33 -- delete x removes the first occurrence of x from its list argument.
  34 delete                  :: (Eq a) => a -> [a] -> [a]
  35 delete                  =  deleteBy (==)
  36
  37 deleteBy                :: (a -> a -> Bool) -> a -> [a] -> [a]
  38 deleteBy eq x []        = []
  39 deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys
  40
  41 -- list difference (non-associative).  In the result of xs \\ ys,
  42 -- the first occurrence of each element of ys in turn (if any)
  43 -- has been removed from xs.  Thus, (xs ++ ys) \\ xs == ys.
  44 (\\)                    :: (Eq a) => [a] -> [a] -> [a]
  45 (\\)                    =  foldl (flip delete)
  46
  47 -- Alternate name for \\
  48 deleteFirsts            :: (Eq a) => [a] -> [a] -> [a]
  49 deleteFirsts            = (\\)
  50
  51 deleteFirstsBy          :: (a -> a -> Bool) -> [a] -> [a] -> [a]
  52 deleteFirstsBy eq       =  foldl (flip (deleteBy eq))
  53
  54 -- elem, notElem, lookup, maximumBy and minimumBy are in PreludeList
  55 elemBy, notElemBy       :: (a -> a -> Bool) -> a -> [a] -> Bool
  56 elemBy eq _ []          =  False
  57 elemBy eq x (y:ys)      =  x `eq` y || elemBy eq x ys
  58
  59 notElemBy eq x xs       =  not (elemBy eq x xs)
  60
  61 lookupBy                :: (a -> a -> Bool) -> a -> [(a, b)] -> Maybe b
  62 lookupBy eq key []      =  Nothing
  63 lookupBy eq key ((x,y):xys)
  64     | key `eq` x        =  Just y
  65     | otherwise         =  lookupBy eq key xys
  66
  67 maximumBy               :: (a -> a -> a) -> [a] -> a
  68 maximumBy max []        =  error "List.maximumBy: empty list"
  69 maximumBy max xs        =  foldl1 max xs
  70
  71 minimumBy               :: (a -> a -> a) -> [a] -> a
  72 minimumBy min []        =  error "List.minimumBy: empty list"
  73 minimumBy min xs        =  foldl1 min xs
  74
  75 -- nub (meaning "essence") remove duplicate elements from its list argument.
  76 nub                     :: (Eq a) => [a] -> [a]
  77 nub                     =  nubBy (==)
  78
  79 nubBy                   :: (a -> a -> Bool) -> [a] -> [a]
  80 nubBy eq []             =  []
  81 nubBy eq (x:xs)         =  x : nubBy eq (filter (\ y -> not (eq x y)) xs)
  82
  83 -- partition takes a predicate and a list and returns a pair of lists:
  84 -- those elements of the argument list that do and do not satisfy the
  85 -- predicate, respectively; i,e,,
  86 -- partition p xs == (filter p xs, filter (not . p) xs).
  87 partition               :: (a -> Bool) -> [a] -> ([a],[a])
  88 partition p xs          =  foldr select ([],[]) xs
  89                            where select x (ts,fs) | p x       = (x:ts,fs)
  90                                                   | otherwise = (ts, x:fs)
  91
  92 -- sums and products give a list of running sums or products from
  93 -- a list of numbers.  e.g., sums [1,2,3] == [0,1,3,6]
  94 sums, products          :: (Num a) => [a] -> [a]
  95 sums                    =  scanl (+) 0
  96 products                =  scanl (*) 1
  97
  98 transpose               :: [[a]] -> [[a]]
  99 transpose               =  foldr
 100                              (\xs xss -> zipWith (:) xs (xss ++ repeat []))
 101                              []
 102
 103 zip4                    :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
 104 zip4                    =  zipWith4 (,,,)
 105
 106 zip5                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
 107 zip5                    =  zipWith5 (,,,,)
 108
 109 zip6                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 110                               [(a,b,c,d,e,f)]
 111 zip6                    =  zipWith6 (,,,,,)
 112
 113 zip7                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 114                               [g] -> [(a,b,c,d,e,f,g)]
 115 zip7                    =  zipWith7 (,,,,,,)
 116
 117 zipWith4                :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
 118 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
 119                         =  z a b c d : zipWith4 z as bs cs ds
 120 zipWith4 _ _ _ _ _      =  []
 121
 122 zipWith5                :: (a->b->c->d->e->f) ->
 123                            [a]->[b]->[c]->[d]->[e]->[f]
 124 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
 125                         =  z a b c d e : zipWith5 z as bs cs ds es
 126 zipWith5 _ _ _ _ _ _    = []
 127
 128 zipWith6                :: (a->b->c->d->e->f->g) ->
 129                            [a]->[b]->[c]->[d]->[e]->[f]->[g]
 130 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
 131                         =  z a b c d e f : zipWith6 z as bs cs ds es fs
 132 zipWith6 _ _ _ _ _ _ _  = []
 133
 134 zipWith7                :: (a->b->c->d->e->f->g->h) ->
 135                            [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
 136 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
 137                    =  z a b c d e f g : zipWith7 z as bs cs ds es fs gs
 138 zipWith7 _ _ _ _ _ _ _ _ = []
 139
 140 unzip4                  :: [(a,b,c,d)] -> ([a],[b],[c],[d])
 141 unzip4                  =  foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
 142                                         (a:as,b:bs,c:cs,d:ds))
 143                                  ([],[],[],[])
 144
 145 unzip5                  :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
 146 unzip5                  =  foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
 147                                         (a:as,b:bs,c:cs,d:ds,e:es))
 148                                  ([],[],[],[],[])
 149
 150 unzip6                  :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
 151 unzip6                  =  foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
 152                                         (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
 153                                  ([],[],[],[],[],[])
 154
 155 unzip7          :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
 156 unzip7          =  foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
 157                                 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
 158                          ([],[],[],[],[],[],[])
 159
 160 genericLength           :: (Num i) => [b] -> i
 161 genericLength []        =  0
 162 genericLength (_:l)     =  1 + genericLength l
 163
 164 genericDrop             :: (Integral i) => i -> [a] -> [a]
 165 genericDrop 0 xs        =  xs
 166 genericDrop _ []        =  []
 167 genericDrop n (_:xs) | n > 0  =  genericDrop (n-1) xs
 168 genericDrop _ _         =  error "List.genericDrop: negative argument"
 169
 170 genericTake             :: (Integral i) => i -> [a] -> [a]
 171 genericTake 0 _         =  []
 172 genericTake _ []        =  []
 173 genericTake n (x:xs) | n > 0  =  x : genericTake (n-1) xs
 174 genericTake _  _        =  error "List.genericTake: negative argument"
 175
 176 genericSplitAt          :: (Integral i) => i -> [b] -> ([b],[b])
 177 genericSplitAt 0 xs     =  ([],xs)
 178 genericSplitAt _ []     =  ([],[])
 179 genericSplitAt n (x:xs) | n > 0  =  (x:xs',xs'') where
 180                                (xs',xs'') = genericSplitAt (n-1) xs
 181 genericSplitAt _ _      =  error "List.genericSplitAt: negative argument"
 182
 183 genericReplicate        :: (Integral i) => i -> a -> [a]
 184 genericReplicate n x    =  genericTake n (repeat x)
 185
 186 -- l !! (elemIndex l x) == x  if x `elem` l
 187 elemIndex               :: Eq a => [a] -> a -> Int
 188 elemIndex               =  elemIndexBy (==)
 189
 190 elemIndexBy             :: (a -> a -> Bool) -> [a] -> a -> Int
 191 elemIndexBy eq [] x      = error "List.elemIndexBy: empty list"
 192 elemIndexBy eq (x:xs) x' = if x `eq` x' then 0 else 1 + elemIndexBy eq xs x'
 193
 194 -- group splits its list argument into a list of lists of equal, adjacent
 195 -- elements.  e.g.,
 196 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
 197 group                   :: (Eq a) => [a] -> [[a]]
 198 group                   =  groupBy (==)
 199
 200 groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
 201 groupBy eq []           =  []
 202 groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
 203                            where (ys,zs) = span (eq x) xs
 204
 205
 206 mapAccumL               :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
 207 mapAccumL f s []        =  (s, [])
 208 mapAccumL f s (x:xs)    =  (s'',y:ys)
 209                            where (s', y ) = f s x
 210                                  (s'',ys) = mapAccumL f s' xs
 211
 212 mapAccumR               :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
 213 mapAccumR f s []        =  (s, [])
 214 mapAccumR f s (x:xs)    =  (s'', y:ys)
 215                            where (s'',y ) = f s' x
 216                                  (s', ys) = mapAccumR f s xs
 217
 218 -- intersperse sep inserts sep between the elements of its list argument.
 219 -- e.g. intersperse ',' "abcde" == "a,b,c,d,e"
 220 intersperse             :: a -> [a] -> [a]
 221 intersperse sep []      =  []
 222 intersperse sep [x]     =  [x]
 223 intersperse sep (x:xs)  =  x : sep : intersperse sep xs
 224
 225 -- inits xs returns the list of initial segments of xs, shortest first.
 226 -- e.g., inits "abc" == ["","a","ab","abc"]
 227 inits                   :: [a] -> [[a]]
 228 inits []                =  [[]]
 229 inits (x:xs)            =  [[]] ++ map (x:) (inits xs)
 230
 231 -- tails xs returns the list of all final segments of xs, longest first.
 232 -- e.g., tails "abc" == ["abc", "bc", "c",""]
 233 tails                   :: [a] -> [[a]]
 234 tails []                =  [[]]
 235 tails xxs@(_:xs)        =  xxs : tails xs
 236
 237 -- subsequences xs returns the list of all subsequences of xs.
 238 -- e.g., subsequences "abc" == ["","c","b","bc","a","ac","ab","abc"]
 239 subsequences            :: [a] -> [[a]]
 240 subsequences []         =  [[]]
 241 subsequences (x:xs)     =  subsequences xs ++ map (x:) (subsequences xs)
 242
 243 -- permutations xs returns the list of all permutations of xs.
 244 -- e.g., permutations "abc" == ["abc","bac","bca","acb","cab","cba"]
 245 permutations            :: [a] -> [[a]]
 246 permutations []         =  [[]]
 247 permutations (x:xs)     =  [zs | ys <- permutations xs, zs <- interleave x ys ]
 248   where interleave          :: a -> [a] -> [[a]]
 249         interleave x []     =  [[x]]
 250         interleave x (y:ys) =  [x:y:ys] ++ map (y:) (interleave x ys)
 251
 252 union                   :: (Eq a) => [a] -> [a] -> [a]
 253 union xs ys             =  xs ++ (ys \\ xs)
 254
 255 intersect               :: (Eq a) => [a] -> [a] -> [a]
 256 intersect xs ys         =  [x | x <- xs, x `elem` ys]
 257 \end{code}