ghc/interpreter/library/List.hs

   1 #ifdef HEAD
   2 module List (
   3     elemIndex, elemIndices,
   4     find, findIndex, findIndices,
   5     nub, nubBy, delete, deleteBy, (\\),
   6     union, unionBy, intersect, intersectBy,
   7     intersperse, transpose, partition, group, groupBy,
   8     inits, tails, isPrefixOf, isSuffixOf,
   9     mapAccumL, mapAccumR,
  10     sort, sortBy, insertBy, maximumBy, minimumBy,
  11     genericLength, genericTake, genericDrop,
  12     genericSplitAt, genericIndex, genericReplicate,
  13     zip4, zip5, zip6, zip7,
  14     zipWith4, zipWith5, zipWith6, zipWith7,
  15     unzip4, unzip5, unzip6, unzip7
  16     ) where
  17
  18 #if STD_PRELUDE
  19 import Maybe( listToMaybe )
  20
  21 infix  5  \\
  22 #else
  23 import PreludeBuiltin
  24 #endif
  25 #endif /* HEAD */
  26 #ifdef BODY
  27
  28 elemIndex               :: Eq a => a -> [a] -> Maybe Int
  29 elemIndex x             =  findIndex (x ==)
  30
  31 elemIndices             :: Eq a => a -> [a] -> [Int]
  32 elemIndices x           =  findIndices (x ==)
  33
  34 find                    :: (a -> Bool) -> [a] -> Maybe a
  35 find p                  =  listToMaybe . filter p
  36
  37 findIndex               :: (a -> Bool) -> [a] -> Maybe Int
  38 findIndex p             =  listToMaybe . findIndices p
  39
  40 findIndices             :: (a -> Bool) -> [a] -> [Int]
  41 findIndices p xs        =  [ i | (x,i) <- zip xs [0..], p x ]
  42
  43 nub                     :: (Eq a) => [a] -> [a]
  44 nub                     =  nubBy (==)
  45
  46 nubBy                   :: (a -> a -> Bool) -> [a] -> [a]
  47 nubBy eq []             =  []
  48 nubBy eq (x:xs)         =  x : nubBy eq (filter (\y -> not (eq x y)) xs)
  49
  50 delete                  :: (Eq a) => a -> [a] -> [a]
  51 delete                  =  deleteBy (==)
  52
  53 deleteBy                :: (a -> a -> Bool) -> a -> [a] -> [a]
  54 deleteBy eq x []        = []
  55 deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys
  56
  57 (\\)                    :: (Eq a) => [a] -> [a] -> [a]
  58 (\\)                    =  foldl (flip delete)
  59
  60 deleteFirstsBy          :: (a -> a -> Bool) -> [a] -> [a] -> [a]
  61 deleteFirstsBy eq       =  foldl (flip (deleteBy eq))
  62
  63 union                   :: (Eq a) => [a] -> [a] -> [a]
  64 union                   =  unionBy (==)
  65
  66 unionBy                 :: (a -> a -> Bool) -> [a] -> [a] -> [a]
  67 unionBy eq xs ys        =  xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
  68
  69 intersect               :: (Eq a) => [a] -> [a] -> [a]
  70 intersect               =  intersectBy (==)
  71
  72 intersectBy             :: (a -> a -> Bool) -> [a] -> [a] -> [a]
  73 intersectBy eq xs ys    =  [x | x <- xs, any (eq x) ys]
  74
  75 intersperse             :: a -> [a] -> [a]
  76 intersperse sep []      =  []
  77 intersperse sep [x]     =  [x]
  78 intersperse sep (x:xs)  =  x : sep : intersperse sep xs
  79
  80 #if 1
  81 transpose               :: [[a]] -> [[a]]
  82 transpose               =  foldr
  83                              (\xs xss -> zipWith (:) xs (xss ++ repeat []))
  84                              []
  85 #else
  86 -- This variant was posted to the haskell mailing list
  87 -- by Jonas Holmerin <md93-jho@nada.kth.se> on 31 Mar 1998.
  88 -- He claims that it is more symmetric since it can handle
  89 --   transpose (repeat [1..5])
  90 -- as well as finite lists of infinite lists such as
  91 --   transpose (map repeat [1..5])
  92 transpose               :: [[a]] -> [[a]]
  93 transpose               =  foldr
  94                              (\xs xss -> zipLazier (:) xs (xss ++ repeat []))
  95                              []
  96   where
  97     zipLazier f (x:xs) xss = f x (head xss) : zipLazier f xs (tail xss)
  98     zipLazier _ _      _   = []
  99 #endif
 100
 101 partition               :: (a -> Bool) -> [a] -> ([a],[a])
 102 partition p xs          =  foldr select ([],[]) xs
 103                            where select x (ts,fs) | p x       = (x:ts,fs)
 104                                                   | otherwise = (ts, x:fs)
 105
 106 -- group splits its list argument into a list of lists of equal, adjacent
 107 -- elements.  e.g.,
 108 -- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
 109 group                   :: (Eq a) => [a] -> [[a]]
 110 group                   =  groupBy (==)
 111
 112 groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
 113 groupBy eq []           =  []
 114 groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
 115                            where (ys,zs) = span (eq x) xs
 116
 117 -- inits xs returns the list of initial segments of xs, shortest first.
 118 -- e.g., inits "abc" == ["","a","ab","abc"]
 119 inits                   :: [a] -> [[a]]
 120 inits []                =  [[]]
 121 inits (x:xs)            =  [[]] ++ map (x:) (inits xs)
 122
 123 -- tails xs returns the list of all final segments of xs, longest first.
 124 -- e.g., tails "abc" == ["abc","bc","c",""]
 125 tails                   :: [a] -> [[a]]
 126 tails []                =  [[]]
 127 tails xxs@(_:xs)        =  xxs : tails xs
 128
 129 isPrefixOf              :: (Eq a) => [a] -> [a] -> Bool
 130 isPrefixOf [] _         =  True
 131 isPrefixOf _  []        =  False
 132 isPrefixOf (x:xs) (y:ys)=  x == y && isPrefixOf xs ys
 133
 134 isSuffixOf              :: (Eq a) => [a] -> [a] -> Bool
 135 isSuffixOf x y          =  reverse x `isPrefixOf` reverse y
 136
 137 mapAccumL               :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
 138 mapAccumL f s []        =  (s, [])
 139 mapAccumL f s (x:xs)    =  (s'',y:ys)
 140                            where (s', y ) = f s x
 141                                  (s'',ys) = mapAccumL f s' xs
 142
 143 mapAccumR               :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
 144 mapAccumR f s []        =  (s, [])
 145 mapAccumR f s (x:xs)    =  (s'', y:ys)
 146                            where (s'',y ) = f s' x
 147                                  (s', ys) = mapAccumR f s xs
 148
 149 sort                    :: (Ord a) => [a] -> [a]
 150 sort                    =  sortBy compare
 151
 152 sortBy                  :: (a -> a -> Ordering) -> [a] -> [a]
 153 sortBy cmp              =  foldr (insertBy cmp) []
 154
 155 insert                  :: Ord a => a -> [a] -> [a]
 156 insert                  =  insertBy compare
 157
 158 insertBy                :: (a -> a -> Ordering) -> a -> [a] -> [a]
 159 insertBy cmp x []       =  [x]
 160 insertBy cmp x ys@(y:ys')
 161                         =  case cmp x y of
 162                                 GT -> y : insertBy cmp x ys'
 163                                 _  -> x : ys
 164
 165 maximumBy               :: (a -> a -> a) -> [a] -> a
 166 maximumBy max []        =  error "List.maximumBy: empty list"
 167 maximumBy max xs        =  foldl1 max xs
 168
 169 minimumBy               :: (a -> a -> a) -> [a] -> a
 170 minimumBy min []        =  error "List.minimumBy: empty list"
 171 minimumBy min xs        =  foldl1 min xs
 172
 173 genericLength           :: (Integral a) => [b] -> a
 174 genericLength []        =  0
 175 genericLength (x:xs)    =  1 + genericLength xs
 176
 177 genericTake             :: (Integral a) => a -> [b] -> [b]
 178 genericTake _ []        =  []
 179 genericTake n (x:xs)
 180    | n > 0              =  x : genericTake (n-1) xs
 181    | otherwise          =  error "List.genericTake: negative argument"
 182
 183 genericDrop             :: (Integral a) => a -> [b] -> [b]
 184 genericDrop 0 xs        =  xs
 185 genericDrop _ []        =  []
 186 genericDrop n (_:xs)
 187    | n > 0              =  genericDrop (n-1) xs
 188    | otherwise          =  error "List.genericDrop: negative argument"
 189
 190 genericSplitAt          :: (Integral a) => a -> [b] -> ([b],[b])
 191 genericSplitAt 0 xs     =  ([],xs)
 192 genericSplitAt _ []     =  ([],[])
 193 genericSplitAt n (x:xs)
 194    | n > 0              =  (x:xs',xs'')
 195    | otherwise          =  error "List.genericSplitAt: negative argument"
 196        where (xs',xs'') =  genericSplitAt (n-1) xs
 197
 198 genericIndex            :: (Integral a) => [b] -> a -> b
 199 genericIndex (x:_)  0   =  x
 200 genericIndex (_:xs) n
 201         | n > 0         =  genericIndex xs (n-1)
 202         | otherwise     =  error "List.genericIndex: negative argument"
 203 genericIndex _ _        =  error "List.genericIndex: index too large"
 204
 205 genericReplicate        :: (Integral a) => a -> b -> [b]
 206 genericReplicate n x    =  genericTake n (repeat x)
 207
 208 zip4                    :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
 209 zip4                    =  zipWith4 (,,,)
 210
 211 zip5                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
 212 zip5                    =  zipWith5 (,,,,)
 213
 214 zip6                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 215                               [(a,b,c,d,e,f)]
 216 zip6                    =  zipWith6 (,,,,,)
 217
 218 zip7                    :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
 219                               [g] -> [(a,b,c,d,e,f,g)]
 220 zip7                    =  zipWith7 (,,,,,,)
 221
 222 zipWith4                :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
 223 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
 224                         =  z a b c d : zipWith4 z as bs cs ds
 225 zipWith4 _ _ _ _ _      =  []
 226
 227 zipWith5                :: (a->b->c->d->e->f) ->
 228                            [a]->[b]->[c]->[d]->[e]->[f]
 229 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
 230                         =  z a b c d e : zipWith5 z as bs cs ds es
 231 zipWith5 _ _ _ _ _ _    =  []
 232
 233 zipWith6                :: (a->b->c->d->e->f->g) ->
 234                            [a]->[b]->[c]->[d]->[e]->[f]->[g]
 235 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
 236                         =  z a b c d e f : zipWith6 z as bs cs ds es fs
 237 zipWith6 _ _ _ _ _ _ _  =  []
 238
 239 zipWith7                :: (a->b->c->d->e->f->g->h) ->
 240                            [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
 241 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
 242                    =  z a b c d e f g : zipWith7 z as bs cs ds es fs gs
 243 zipWith7 _ _ _ _ _ _ _ _ = []
 244
 245 unzip4                  :: [(a,b,c,d)] -> ([a],[b],[c],[d])
 246 unzip4                  =  foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
 247                                         (a:as,b:bs,c:cs,d:ds))
 248                                  ([],[],[],[])
 249
 250 unzip5                  :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
 251 unzip5                  =  foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
 252                                         (a:as,b:bs,c:cs,d:ds,e:es))
 253                                  ([],[],[],[],[])
 254
 255 unzip6                  :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
 256 unzip6                  =  foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
 257                                         (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
 258                                  ([],[],[],[],[],[])
 259
 260 unzip7          :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
 261 unzip7          =  foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
 262                                 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
 263                          ([],[],[],[],[],[],[])
 264
 265 #endif /* BODY */