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     elemIndex, elemIndices,
  10     find, findIndex, findIndices,
  11     nub, nubBy, delete, deleteBy, (\\), deleteFirstsBy,
  12     union, intersect,
  13     intersperse, transpose, partition, group, groupBy,
  14     inits, tails, isPrefixOf, isSuffixOf,
  15     mapAccumL, mapAccumR,
  16     sort, sortBy, insertBy, maximumBy, minimumBy,
  17     genericLength, genericTake, genericDrop,
  18     genericSplitAt, genericIndex, genericReplicate,
  19     zip4, zip5, zip6, zip7,
  20     zipWith4, zipWith5, zipWith6, zipWith7,
  21     unzip4, unzip5, unzip6, unzip7
  22
  23   ) where
  24
  25 import Prelude
  26 import Maybe (listToMaybe)
  27
  28 infix 5 \\
  29 \end{code}
  30
  31 %*********************************************************
  32 %*                                                      *
  33 \subsection{List functions}
  34 %*                                                      *
  35 %*********************************************************
  36
  37 \begin{code}
  38 elemIndex       :: Eq a => a -> [a] -> Maybe Int
  39 elemIndex x     = findIndex (x==)
  40
  41 elemIndices     :: Eq a => a -> [a] -> [Int]
  42 elemIndices x   = findIndices (x==)
  43
  44 find            :: (a -> Bool) -> [a] -> Maybe a
  45 find p          = listToMaybe . filter p
  46
  47 findIndex       :: (a -> Bool) -> [a] -> Maybe Int
  48 findIndex p     = listToMaybe . findIndices p
  49
  50 findIndices      :: (a -> Bool) -> [a] -> [Int]
  51 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
  52
  53 isPrefixOf              :: (Eq a) => [a] -> [a] -> Bool
  54 isPrefixOf [] _         =  True
  55 isPrefixOf _  []        =  False
  56 isPrefixOf (x:xs) (y:ys)=  x == y && isPrefixOf xs ys
  57
  58 isSuffixOf              :: (Eq a) => [a] -> [a] -> Bool
  59 isSuffixOf x y          =  reverse x `isPrefixOf` reverse y
  60
  61 -- nub (meaning "essence") remove duplicate elements from its list argument.
  62 nub                     :: (Eq a) => [a] -> [a]
  63 #ifdef USE_REPORT_PRELUDE
  64 nub                     =  nubBy (==)
  65 #else
  66 -- stolen from HBC
  67 nub l                   = nub' l []
  68   where
  69     nub' [] _           = []
  70     nub' (x:xs) l       = if x `elem` l then nub' xs l else x : nub' xs (x:l)
  71 #endif
  72
  73 nubBy                   :: (a -> a -> Bool) -> [a] -> [a]
  74 #ifdef USE_REPORT_PRELUDE
  75 nubBy eq []             =  []
  76 nubBy eq (x:xs)         =  x : nubBy eq (filter (\ y -> not (eq x y)) xs)
  77 #else
  78 nubBy eq l              = nubBy' l []
  79   where
  80     nubBy' [] _         = []
  81     nubBy' (x:xs) l     = if elemBy eq x l then nubBy' xs l else x : nubBy' xs (x:l)
  82 #endif
  83
  84 -- delete x removes the first occurrence of x from its list argument.
  85 delete                  :: (Eq a) => a -> [a] -> [a]
  86 delete                  =  deleteBy (==)
  87
  88 deleteBy                :: (a -> a -> Bool) -> a -> [a] -> [a]
  89 deleteBy eq x []        = []
  90 deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys
  91
  92 -- list difference (non-associative).  In the result of xs \\ ys,
  93 -- the first occurrence of each element of ys in turn (if any)
  94 -- has been removed from xs.  Thus, (xs ++ ys) \\ xs == ys.
  95 (\\)                    :: (Eq a) => [a] -> [a] -> [a]
  96 (\\)                    =  foldl (flip delete)
  97
  98 -- List union, remove the elements of first list from second.
  99 union                   :: (Eq a) => [a] -> [a] -> [a]
 100 union                   = unionBy (==)
 101
 102 unionBy                 :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 103 unionBy eq xs ys        =  xs ++ foldl (flip (deleteBy eq)) ys xs
 104
 105 intersect               :: (Eq a) => [a] -> [a] -> [a]
 106 intersect               =  intersectBy (==)
 107
 108 intersectBy             :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 109 intersectBy eq xs ys    =  [x | x <- xs, any (eq x) ys]
 110
 111 -- intersperse sep inserts sep between the elements of its list argument.
 112 -- e.g. intersperse ',' "abcde" == "a,b,c,d,e"
 113 intersperse             :: a -> [a] -> [a]
 114 intersperse sep []      = []
 115 intersperse sep [x]     = [x]
 116 intersperse sep (x:xs)  = x : sep : intersperse sep xs
 117
 118 transpose               :: [[a]] -> [[a]]
 119 transpose               =  foldr
 120                              (\xs xss -> zipWith (:) xs (xss ++ repeat []))
 121                              []
 122
 123
 124 -- partition takes a predicate and a list and returns a pair of lists:
 125 -- those elements of the argument list that do and do not satisfy the
 126 -- predicate, respectively; i,e,,
 127 -- partition p xs == (filter p xs, filter (not . p) xs).
 128 partition               :: (a -> Bool) -> [a] -> ([a],[a])
 129 partition p xs          =  foldr select ([],[]) xs
 130                            where select x (ts,fs) | p x       = (x:ts,fs)
 131                                                   | otherwise = (ts, x:fs)
 132
 133
 134
 135
 136 mapAccumL               :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
 137 mapAccumL f s []        =  (s, [])
 138 mapAccumL f s (x:xs)    =  (s'',y:ys)
 139                            where (s', y ) = f s x
 140                                  (s'',ys) = mapAccumL f s' xs
 141
 142 mapAccumR               :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
 143 mapAccumR f s []        =  (s, [])
 144 mapAccumR f s (x:xs)    =  (s'', y:ys)
 145                            where (s'',y ) = f s' x
 146                                  (s', ys) = mapAccumR f s xs
 147 sort :: (Ord a) => [a] -> [a]
 148 sort = sortBy compare
 149
 150 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
 151 sortBy cmp = foldr (insertBy cmp) []
 152
 153 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
 154 insertBy cmp x [] = [x]
 155 insertBy cmp x ys@(y:ys')
 156  = case cmp x y of
 157      GT -> y : insertBy cmp x ys'
 158      _  -> x : ys
 159
 160 maximumBy               :: (a -> a -> a) -> [a] -> a
 161 maximumBy max []        =  error "List.maximumBy: empty list"
 162 maximumBy max xs        =  foldl1 max xs
 163
 164 minimumBy               :: (a -> a -> a) -> [a] -> a
 165 minimumBy min []        =  error "List.minimumBy: empty list"
 166 minimumBy min xs        =  foldl1 min xs
 167
 168 genericLength           :: (Num i) => [b] -> i
 169 genericLength []        =  0
 170 genericLength (_:l)     =  1 + genericLength l
 171
 172 genericTake             :: (Integral i) => i -> [a] -> [a]
 173 genericTake 0 _         =  []
 174 genericTake _ []        =  []
 175 genericTake n (x:xs) | n > 0  =  x : genericTake (n-1) xs
 176 genericTake _  _        =  error "List.genericTake: negative argument"
 177
 178 genericDrop             :: (Integral i) => i -> [a] -> [a]
 179 genericDrop 0 xs        =  xs
 180 genericDrop _ []        =  []
 181 genericDrop n (_:xs) | n > 0  =  genericDrop (n-1) xs
 182 genericDrop _ _         =  error "List.genericDrop: negative argument"
 183
 184 genericSplitAt          :: (Integral i) => i -> [b] -> ([b],[b])
 185 genericSplitAt 0 xs     =  ([],xs)
 186 genericSplitAt _ []     =  ([],[])
 187 genericSplitAt n (x:xs) | n > 0  =  (x:xs',xs'') where
 188                                (xs',xs'') = genericSplitAt (n-1) xs
 189 genericSplitAt _ _      =  error "List.genericSplitAt: negative argument"
 190
 191
 192 genericIndex :: (Integral a) => [b] -> a -> b
 193 genericIndex (x:_)  0 = x
 194 genericIndex (_:xs) n
 195  | n > 0     = genericIndex xs (n-1)
 196  | otherwise = error "List.genericIndex: negative argument."
 197 genericIndex _ _      = error "List.genericIndex: index too large."
 198
 199 zip4                    :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
 200 zip4                    =  zipWith4 (,,,)
 201
 202 zip5                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
 203 zip5                    =  zipWith5 (,,,,)
 204
 205 zip6                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 206                               [(a,b,c,d,e,f)]
 207 zip6                    =  zipWith6 (,,,,,)
 208
 209 zip7                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 210                               [g] -> [(a,b,c,d,e,f,g)]
 211 zip7                    =  zipWith7 (,,,,,,)
 212
 213 zipWith4                :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
 214 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
 215                         =  z a b c d : zipWith4 z as bs cs ds
 216 zipWith4 _ _ _ _ _      =  []
 217
 218 zipWith5                :: (a->b->c->d->e->f) ->
 219                            [a]->[b]->[c]->[d]->[e]->[f]
 220 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
 221                         =  z a b c d e : zipWith5 z as bs cs ds es
 222 zipWith5 _ _ _ _ _ _    = []
 223
 224 zipWith6                :: (a->b->c->d->e->f->g) ->
 225                            [a]->[b]->[c]->[d]->[e]->[f]->[g]
 226 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
 227                         =  z a b c d e f : zipWith6 z as bs cs ds es fs
 228 zipWith6 _ _ _ _ _ _ _  = []
 229
 230 zipWith7                :: (a->b->c->d->e->f->g->h) ->
 231                            [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
 232 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
 233                    =  z a b c d e f g : zipWith7 z as bs cs ds es fs gs
 234 zipWith7 _ _ _ _ _ _ _ _ = []
 235
 236 unzip4                  :: [(a,b,c,d)] -> ([a],[b],[c],[d])
 237 unzip4                  =  foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
 238                                         (a:as,b:bs,c:cs,d:ds))
 239                                  ([],[],[],[])
 240
 241 unzip5                  :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
 242 unzip5                  =  foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
 243                                         (a:as,b:bs,c:cs,d:ds,e:es))
 244                                  ([],[],[],[],[])
 245
 246 unzip6                  :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
 247 unzip6                  =  foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
 248                                         (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
 249                                  ([],[],[],[],[],[])
 250
 251 unzip7          :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
 252 unzip7          =  foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
 253                                 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
 254                          ([],[],[],[],[],[],[])
 255
 256
 257
 258 deleteFirstsBy          :: (a -> a -> Bool) -> [a] -> [a] -> [a]
 259 deleteFirstsBy eq       =  foldl (flip (deleteBy eq))
 260
 261 -- elem, notElem, lookup, maximumBy and minimumBy are in PreludeList
 262 elemBy, notElemBy       :: (a -> a -> Bool) -> a -> [a] -> Bool
 263 elemBy eq _ []          =  False
 264 elemBy eq x (y:ys)      =  x `eq` y || elemBy eq x ys
 265
 266 notElemBy eq x xs       =  not (elemBy eq x xs)
 267
 268 lookupBy                :: (a -> a -> Bool) -> a -> [(a, b)] -> Maybe b
 269 lookupBy eq key []      =  Nothing
 270 lookupBy eq key ((x,y):xys)
 271     | key `eq` x        =  Just y
 272     | otherwise         =  lookupBy eq key xys
 273
 274
 275 -- sums and products give a list of running sums or products from
 276 -- a list of numbers.  e.g., sums [1,2,3] == [0,1,3,6]
 277 sums, products          :: (Num a) => [a] -> [a]
 278 sums                    =  scanl (+) 0
 279 products                =  scanl (*) 1
 280
 281 genericReplicate        :: (Integral i) => i -> a -> [a]
 282 genericReplicate n x    =  genericTake n (repeat x)
 283
 284 -- group splits its list argument into a list of lists of equal, adjacent
 285 -- elements.  e.g.,
 286 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
 287 group                   :: (Eq a) => [a] -> [[a]]
 288 group                   =  groupBy (==)
 289
 290 groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
 291 groupBy eq []           =  []
 292 groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
 293                            where (ys,zs) = span (eq x) xs
 294
 295 -- inits xs returns the list of initial segments of xs, shortest first.
 296 -- e.g., inits "abc" == ["","a","ab","abc"]
 297 inits                   :: [a] -> [[a]]
 298 inits []                =  [[]]
 299 inits (x:xs)            =  [[]] ++ map (x:) (inits xs)
 300
 301 -- tails xs returns the list of all final segments of xs, longest first.
 302 -- e.g., tails "abc" == ["abc", "bc", "c",""]
 303 tails                   :: [a] -> [[a]]
 304 tails []                =  [[]]
 305 tails xxs@(_:xs)        =  xxs : tails xs
 306
 307 {-      Old stuff now not in List
 308
 309 elemIndexBy             :: (a -> a -> Bool) -> [a] -> a -> Int
 310 elemIndexBy eq [] x      = error "List.elemIndexBy: empty list"
 311 elemIndexBy eq (x:xs) x' = if x `eq` x' then 0 else 1 + elemIndexBy eq xs x'
 312
 313 -- subsequences xs returns the list of all subsequences of xs.
 314 -- e.g., subsequences "abc" == ["","c","b","bc","a","ac","ab","abc"]
 315 subsequences            :: [a] -> [[a]]
 316 subsequences []         =  [[]]
 317 subsequences (x:xs)     =  subsequences xs ++ map (x:) (subsequences xs)
 318
 319 -- permutations xs returns the list of all permutations of xs.
 320 -- e.g., permutations "abc" == ["abc","bac","bca","acb","cab","cba"]
 321 permutations            :: [a] -> [[a]]
 322 permutations []         =  [[]]
 323 permutations (x:xs)     =  [zs | ys <- permutations xs, zs <- interleave x ys ]
 324   where interleave          :: a -> [a] -> [[a]]
 325         interleave x []     =  [[x]]
 326         interleave x (y:ys) =  [x:y:ys] ++ map (y:) (interleave x ys)
 327 -}
 328 \end{code}