ghc/interpreter/prelude/PreludeList.hs

   1 -- Standard list functions
   2
   3 #ifdef HEAD
   4 module PreludeList (
   5     head, last, tail, init, null, length, (!!),
   6     foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,
   7     iterate, repeat, replicate, cycle,
   8     take, drop, splitAt, takeWhile, dropWhile, span, break,
   9     lines, words, unlines, unwords, reverse, and, or,
  10     any, all, elem, notElem, lookup,
  11     sum, product, maximum, minimum, concatMap,
  12     zip, zip3, zipWith, zipWith3, unzip, unzip3)
  13   where
  14
  15 import qualified Char(isSpace)
  16 import PreludeBuiltin
  17 #endif /* HEAD */
  18 #ifdef BODY
  19
  20 infixl 9  !!
  21 infix  4  `elem`, `notElem`
  22
  23 -- head and tail extract the first element and remaining elements,
  24 -- respectively, of a list, which must be non-empty.  last and init
  25 -- are the dual functions working from the end of a finite list,
  26 -- rather than the beginning.
  27
  28 head             :: [a] -> a
  29 head (x:_)       =  x
  30 head []          =  error "PreludeList.head: empty list"
  31
  32 last             :: [a] -> a
  33 last [x]         =  x
  34 last (_:xs)      =  last xs
  35 last []          =  error "PreludeList.last: empty list"
  36
  37 tail             :: [a] -> [a]
  38 tail (_:xs)      =  xs
  39 tail []          =  error "PreludeList.tail: empty list"
  40
  41 init             :: [a] -> [a]
  42 init [x]         =  []
  43 init (x:xs)      =  x : init xs
  44 init []          =  error "PreludeList.init: empty list"
  45
  46 null             :: [a] -> Bool
  47 null []          =  True
  48 null (_:_)       =  False
  49
  50 -- length returns the length of a finite list as an Int.
  51 length           :: [a] -> Int
  52 length []        =  0
  53 length (_:l)     =  1 + length l
  54
  55 -- List index (subscript) operator, 0-origin
  56 (!!)                :: [a] -> Int -> a
  57 (x:_)  !! 0         =  x
  58 (_:xs) !! n | n > 0 =  xs !! (n-1)
  59 (_:_)  !! _         =  error "PreludeList.!!: negative index"
  60 []     !! _         =  error "PreludeList.!!: index too large"
  61
  62 -- foldl, applied to a binary operator, a starting value (typically the
  63 -- left-identity of the operator), and a list, reduces the list using
  64 -- the binary operator, from left to right:
  65 --  foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
  66 -- foldl1 is a variant that has no starting value argument, and  thus must
  67 -- be applied to non-empty lists.  scanl is similar to foldl, but returns
  68 -- a list of successive reduced values from the left:
  69 --      scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
  70 -- Note that  last (scanl f z xs) == foldl f z xs.
  71 -- scanl1 is similar, again without the starting element:
  72 --      scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
  73
  74 foldl            :: (a -> b -> a) -> a -> [b] -> a
  75 foldl f z []     =  z
  76 foldl f z (x:xs) =  foldl f (f z x) xs
  77
  78 foldl1           :: (a -> a -> a) -> [a] -> a
  79 foldl1 f (x:xs)  =  foldl f x xs
  80 foldl1 _ []      =  error "PreludeList.foldl1: empty list"
  81
  82 scanl            :: (a -> b -> a) -> a -> [b] -> [a]
  83 scanl f q xs     =  q : (case xs of
  84                             []   -> []
  85                             x:xs -> scanl f (f q x) xs)
  86
  87 scanl1           :: (a -> a -> a) -> [a] -> [a]
  88 scanl1 f (x:xs)  =  scanl f x xs
  89 scanl1 _ []      =  error "PreludeList.scanl1: empty list"
  90
  91 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
  92 -- above functions.
  93
  94 foldr            :: (a -> b -> b) -> b -> [a] -> b
  95 foldr f z []     =  z
  96 foldr f z (x:xs) =  f x (foldr f z xs)
  97
  98 foldr1           :: (a -> a -> a) -> [a] -> a
  99 foldr1 f [x]     =  x
 100 foldr1 f (x:xs)  =  f x (foldr1 f xs)
 101 foldr1 _ []      =  error "PreludeList.foldr1: empty list"
 102
 103 scanr             :: (a -> b -> b) -> b -> [a] -> [b]
 104 scanr f q0 []     =  [q0]
 105 scanr f q0 (x:xs) =  f x q : qs
 106                      where qs@(q:_) = scanr f q0 xs
 107
 108 scanr1           :: (a -> a -> a) -> [a] -> [a]
 109 scanr1 f  [x]    =  [x]
 110 scanr1 f  (x:xs) =  f x q : qs
 111                     where qs@(q:_) = scanr1 f xs
 112 scanr1 _ []      =  error "PreludeList.scanr1: empty list"
 113
 114 -- iterate f x returns an infinite list of repeated applications of f to x:
 115 -- iterate f x == [x, f x, f (f x), ...]
 116 iterate          :: (a -> a) -> a -> [a]
 117 iterate f x      =  x : iterate f (f x)
 118
 119 -- repeat x is an infinite list, with x the value of every element.
 120 repeat           :: a -> [a]
 121 repeat x         =  xs where xs = x:xs
 122
 123 -- replicate n x is a list of length n with x the value of every element
 124 replicate        :: Int -> a -> [a]
 125 replicate n x    =  take n (repeat x)
 126
 127 -- cycle ties a finite list into a circular one, or equivalently,
 128 -- the infinite repetition of the original list.  It is the identity
 129 -- on infinite lists.
 130
 131 cycle            :: [a] -> [a]
 132 #if STD_PRELUDE
 133 #else
 134 -- check proposed by Friedhelm Wrensch <fwr@1772228662.hostid.net>
 135 -- doesn't seem to affect strictness
 136 cycle []         =  error "PreludeList.cycle []"
 137 #endif
 138 cycle xs         =  xs' where xs' = xs ++ xs'
 139
 140 -- take n, applied to a list xs, returns the prefix of xs of length n,
 141 -- or xs itself if n > length xs.  drop n xs returns the suffix of xs
 142 -- after the first n elements, or [] if n > length xs.  splitAt n xs
 143 -- is equivalent to (take n xs, drop n xs).
 144
 145 take                   :: Int -> [a] -> [a]
 146 take 0 _               =  []
 147 take _ []              =  []
 148 take n (x:xs) | n > 0  =  x : take (n-1) xs
 149 take _     _           =  error "PreludeList.take: negative argument"
 150
 151 drop                   :: Int -> [a] -> [a]
 152 drop 0 xs              =  xs
 153 drop _ []              =  []
 154 drop n (_:xs) | n > 0  =  drop (n-1) xs
 155 drop _     _           =  error "PreludeList.drop: negative argument"
 156
 157 splitAt                  :: Int -> [a] -> ([a],[a])
 158 splitAt 0 xs             =  ([],xs)
 159 splitAt _ []             =  ([],[])
 160 splitAt n (x:xs) | n > 0 =  (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs
 161 splitAt _     _          =  error "PreludeList.splitAt: negative argument"
 162
 163 -- takeWhile, applied to a predicate p and a list xs, returns the longest
 164 -- prefix (possibly empty) of xs of elements that satisfy p.  dropWhile p xs
 165 -- returns the remaining suffix.  Span p xs is equivalent to
 166 -- (takeWhile p xs, dropWhile p xs), while break p uses the negation of p.
 167
 168 takeWhile               :: (a -> Bool) -> [a] -> [a]
 169 takeWhile p []          =  []
 170 takeWhile p (x:xs)
 171             | p x       =  x : takeWhile p xs
 172             | otherwise =  []
 173
 174 dropWhile               :: (a -> Bool) -> [a] -> [a]
 175 dropWhile p []          =  []
 176 dropWhile p xs@(x:xs')
 177             | p x       =  dropWhile p xs'
 178             | otherwise =  xs
 179
 180 span, break             :: (a -> Bool) -> [a] -> ([a],[a])
 181 span p []               =  ([],[])
 182 span p xs@(x:xs')
 183             | p x       =  (x:ys,zs)
 184             | otherwise =  ([],xs)
 185                            where (ys,zs) = span p xs'
 186 break p                 =  span (not . p)
 187
 188 -- lines breaks a string up into a list of strings at newline characters.
 189 -- The resulting strings do not contain newlines.  Similary, words
 190 -- breaks a string up into a list of words, which were delimited by
 191 -- white space.  unlines and unwords are the inverse operations.
 192 -- unlines joins lines with terminating newlines, and unwords joins
 193 -- words with separating spaces.
 194
 195 lines            :: String -> [String]
 196 lines ""         =  []
 197 lines s          =  let (l, s') = break (== '\n') s
 198                       in  l : case s' of
 199                                 []      -> []
 200                                 (_:s'') -> lines s''
 201
 202 words            :: String -> [String]
 203 #if STD_PRELUDE
 204 words s          =  case dropWhile Char.isSpace s of
 205 #else
 206 words s          =  case dropWhile isSpace s of
 207 #endif
 208                       "" -> []
 209                       s' -> w : words s''
 210 #if STD_PRELUDE
 211                             where (w, s'') = break Char.isSpace s'
 212 #else
 213                             where (w, s'') = break isSpace s'
 214 #endif
 215
 216 unlines          :: [String] -> String
 217 unlines          =  concatMap (++ "\n")
 218
 219 unwords          :: [String] -> String
 220 unwords []       =  ""
 221 unwords ws       =  foldr1 (\w s -> w ++ ' ':s) ws
 222
 223 -- reverse xs returns the elements of xs in reverse order.  xs must be finite.
 224 reverse          :: [a] -> [a]
 225 reverse          =  foldl (flip (:)) []
 226
 227 -- and returns the conjunction of a Boolean list.  For the result to be
 228 -- True, the list must be finite; False, however, results from a False
 229 -- value at a finite index of a finite or infinite list.  or is the
 230 -- disjunctive dual of and.
 231 and, or          :: [Bool] -> Bool
 232 and              =  foldr (&&) True
 233 or               =  foldr (||) False
 234
 235 -- Applied to a predicate and a list, any determines if any element
 236 -- of the list satisfies the predicate.  Similarly, for all.
 237 any, all         :: (a -> Bool) -> [a] -> Bool
 238 any p            =  or . map p
 239 all p            =  and . map p
 240
 241 -- elem is the list membership predicate, usually written in infix form,
 242 -- e.g., x `elem` xs.  notElem is the negation.
 243 elem, notElem    :: (Eq a) => a -> [a] -> Bool
 244 elem x           =  any (== x)
 245 notElem x        =  all (/= x)
 246
 247 -- lookup key assocs looks up a key in an association list.
 248 lookup           :: (Eq a) => a -> [(a,b)] -> Maybe b
 249 lookup key []    =  Nothing
 250 lookup key ((x,y):xys)
 251     | key == x   =  Just y
 252     | otherwise  =  lookup key xys
 253
 254 -- sum and product compute the sum or product of a finite list of numbers.
 255 sum, product     :: (Num a) => [a] -> a
 256 sum              =  foldl (+) 0
 257 product          =  foldl (*) 1
 258
 259 -- maximum and minimum return the maximum or minimum value from a list,
 260 -- which must be non-empty, finite, and of an ordered type.
 261 maximum, minimum :: (Ord a) => [a] -> a
 262 maximum []       =  error "PreludeList.maximum: empty list"
 263 maximum xs       =  foldl1 max xs
 264
 265 minimum []       =  error "PreludeList.minimum: empty list"
 266 minimum xs       =  foldl1 min xs
 267
 268 concatMap        :: (a -> [b]) -> [a] -> [b]
 269 concatMap f      =  concat . map f
 270
 271 -- zip takes two lists and returns a list of corresponding pairs.  If one
 272 -- input list is short, excess elements of the longer list are discarded.
 273 -- zip3 takes three lists and returns a list of triples.  Zips for larger
 274 -- tuples are in the List library
 275
 276 zip              :: [a] -> [b] -> [(a,b)]
 277 zip              =  zipWith (,)
 278
 279 zip3             :: [a] -> [b] -> [c] -> [(a,b,c)]
 280 zip3             =  zipWith3 (,,)
 281
 282 -- The zipWith family generalises the zip family by zipping with the
 283 -- function given as the first argument, instead of a tupling function.
 284 -- For example, zipWith (+) is applied to two lists to produce the list
 285 -- of corresponding sums.
 286
 287 zipWith          :: (a->b->c) -> [a]->[b]->[c]
 288 zipWith z (a:as) (b:bs)
 289                  =  z a b : zipWith z as bs
 290 zipWith _ _ _    =  []
 291
 292 zipWith3         :: (a->b->c->d) -> [a]->[b]->[c]->[d]
 293 zipWith3 z (a:as) (b:bs) (c:cs)
 294                  =  z a b c : zipWith3 z as bs cs
 295 zipWith3 _ _ _ _ =  []
 296
 297
 298 -- unzip transforms a list of pairs into a pair of lists.
 299
 300 unzip            :: [(a,b)] -> ([a],[b])
 301 unzip            =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
 302
 303 unzip3           :: [(a,b,c)] -> ([a],[b],[c])
 304 unzip3           =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
 305                           ([],[],[])
 306
 307
 308 #endif /* BODY */