ghc/lib/ghc/PrelList.lhs

   1 %
   2 % (c) The AQUA Project, Glasgow University, 1994-1996
   3 %
   4
   5 \section[PrelList]{Module @PrelList@}
   6
   7 The List data type and its operations
   8
   9 \begin{code}
  10 {-# OPTIONS -fno-implicit-prelude #-}
  11
  12 module PrelList (
  13    [] (..),
  14
  15    head, last, tail, init, null, length, (!!),
  16    foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,
  17    iterate, repeat, replicate, cycle,
  18    take, drop, splitAt, takeWhile, dropWhile, span, break,
  19    lines, words, unlines, unwords, reverse, and, or,
  20    any, all, elem, notElem, lookup,
  21    sum, product, maximum, minimum, concatMap,
  22    zip, zip3, zipWith, zipWith3, unzip, unzip3
  23  ) where
  24
  25 import {-# SOURCE #-}   IOBase  ( error )
  26 import PrelTup
  27 import PrelBase
  28
  29 infix  4 `elem`, `notElem`
  30 \end{code}
  31
  32 %*********************************************************
  33 %*                                                      *
  34 \subsection{List-manipulation functions}
  35 %*                                                      *
  36 %*********************************************************
  37
  38 \begin{code}
  39 -- head and tail extract the first element and remaining elements,
  40 -- respectively, of a list, which must be non-empty.  last and init
  41 -- are the dual functions working from the end of a finite list,
  42 -- rather than the beginning.
  43
  44 head                    :: [a] -> a
  45 head (x:_)              =  x
  46 head []                 =  error "PreludeList.head: empty list"
  47
  48 last                    :: [a] -> a
  49 last [x]                =  x
  50 last (_:xs)             =  last xs
  51 last []                 =  error "PreludeList.last: empty list"
  52
  53 tail                    :: [a] -> [a]
  54 tail (_:xs)             =  xs
  55 tail []                 =  error "PreludeList.tail: empty list"
  56
  57 init                    :: [a] -> [a]
  58 init [x]                =  []
  59 init (x:xs)             =  x : init xs
  60 init []                 =  error "PreludeList.init: empty list"
  61
  62 null                    :: [a] -> Bool
  63 null []                 =  True
  64 null (_:_)              =  False
  65
  66 -- length returns the length of a finite list as an Int; it is an instance
  67 -- of the more general genericLength, the result type of which may be
  68 -- any kind of number.
  69 length                  :: [a] -> Int
  70 #ifdef USE_REPORT_PRELUDE
  71 length []               =  0
  72 length (_:l)            =  1 + length l
  73 #else
  74 length l                =  len l 0#
  75   where
  76     len :: [a] -> Int# -> Int
  77     len []     a# = I# a#
  78     len (_:xs) a# = len xs (a# +# 1#)
  79 #endif
  80
  81 -- foldl, applied to a binary operator, a starting value (typically the
  82 -- left-identity of the operator), and a list, reduces the list using
  83 -- the binary operator, from left to right:
  84 --  foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
  85 -- foldl1 is a variant that has no starting value argument, and  thus must
  86 -- be applied to non-empty lists.  scanl is similar to foldl, but returns
  87 -- a list of successive reduced values from the left:
  88 --      scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
  89 -- Note that  last (scanl f z xs) == foldl f z xs.
  90 -- scanl1 is similar, again without the starting element:
  91 --      scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
  92
  93 foldl                   :: (a -> b -> a) -> a -> [b] -> a
  94 foldl f z []            =  z
  95 foldl f z (x:xs)        =  foldl f (f z x) xs
  96
  97 foldl1                  :: (a -> a -> a) -> [a] -> a
  98 foldl1 f (x:xs)         =  foldl f x xs
  99 foldl1 _ []             =  error "PreludeList.foldl1: empty list"
 100
 101 scanl                   :: (a -> b -> a) -> a -> [b] -> [a]
 102 scanl f q xs            =  q : (case xs of
 103                                 []   -> []
 104                                 x:xs -> scanl f (f q x) xs)
 105
 106 scanl1                  :: (a -> a -> a) -> [a] -> [a]
 107 scanl1 f (x:xs)         =  scanl f x xs
 108 scanl1 _ []             =  error "PreludeList.scanl1: empty list"
 109
 110 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
 111 -- above functions.
 112
 113 foldr1                  :: (a -> a -> a) -> [a] -> a
 114 foldr1 f [x]            =  x
 115 foldr1 f (x:xs)         =  f x (foldr1 f xs)
 116 foldr1 _ []             =  error "PreludeList.foldr1: empty list"
 117
 118 scanr                   :: (a -> b -> b) -> b -> [a] -> [b]
 119 scanr f q0 []           =  [q0]
 120 scanr f q0 (x:xs)       =  f x q : qs
 121                            where qs@(q:_) = scanr f q0 xs
 122
 123 scanr1                  :: (a -> a -> a) -> [a] -> [a]
 124 scanr1 f  [x]           =  [x]
 125 scanr1 f  (x:xs)        =  f x q : qs
 126                            where qs@(q:_) = scanr1 f xs
 127 scanr1 _ []             =  error "PreludeList.scanr1: empty list"
 128
 129 -- iterate f x returns an infinite list of repeated applications of f to x:
 130 -- iterate f x == [x, f x, f (f x), ...]
 131 iterate                 :: (a -> a) -> a -> [a]
 132 iterate f x             =  x : iterate f (f x)
 133
 134 -- repeat x is an infinite list, with x the value of every element.
 135 repeat                  :: a -> [a]
 136 repeat x                =  xs where xs = x:xs
 137
 138 -- replicate n x is a list of length n with x the value of every element
 139 replicate               :: Int -> a -> [a]
 140 replicate n x           =  take n (repeat x)
 141
 142 -- cycle ties a finite list into a circular one, or equivalently,
 143 -- the infinite repetition of the original list.  It is the identity
 144 -- on infinite lists.
 145
 146 cycle                   :: [a] -> [a]
 147 cycle xs                =  xs' where xs' = xs ++ xs'
 148
 149 -- take n, applied to a list xs, returns the prefix of xs of length n,
 150 -- or xs itself if n > length xs.  drop n xs returns the suffix of xs
 151 -- after the first n elements, or [] if n > length xs.  splitAt n xs
 152 -- is equivalent to (take n xs, drop n xs).
 153 #ifdef USE_REPORT_PRELUDE
 154 take                   :: Int -> [a] -> [a]
 155 take 0 _               =  []
 156 take _ []              =  []
 157 take n (x:xs) | n > 0  =  x : take (n-1) xs
 158 take _     _           =  error "PreludeList.take: negative argument"
 159
 160 drop                   :: Int -> [a] -> [a]
 161 drop 0 xs              =  xs
 162 drop _ []              =  []
 163 drop n (_:xs) | n > 0  =  drop (n-1) xs
 164 drop _     _           =  error "PreludeList.drop: negative argument"
 165
 166 splitAt                   :: Int -> [a] -> ([a],[a])
 167 splitAt 0 xs              =  ([],xs)
 168 splitAt _ []              =  ([],[])
 169 splitAt n (x:xs) | n > 0  =  (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs
 170 splitAt _     _           =  error "PreludeList.splitAt: negative argument"
 171
 172 #else /* hack away */
 173 take    :: Int -> [b] -> [b]
 174 take (I# n#) xs = takeUInt n# xs
 175
 176 -- The general code for take, below, checks n <= maxInt
 177 -- No need to check for maxInt overflow when specialised
 178 -- at type Int or Int# since the Int must be <= maxInt
 179
 180 takeUInt :: Int# -> [b] -> [b]
 181 takeUInt n xs
 182   | n >=# 0#  =  take_unsafe_UInt n xs
 183   | otherwise =  error "take{PreludeList}: negative index"
 184
 185 take_unsafe_UInt 0# _     = []
 186 take_unsafe_UInt _  []    = []
 187 take_unsafe_UInt m (x:xs) = x : take_unsafe_UInt (m -# 1#) xs
 188
 189 drop            :: Int -> [b] -> [b]
 190 drop (I# n#) xs
 191   | n# <# 0#    = error "drop{PreludeList}: negative index"
 192   | otherwise   = drop# n# xs
 193     where
 194         drop# :: Int# -> [a] -> [a]
 195         drop# 0# xs      = xs
 196         drop# _  []      = []
 197         drop# m# (_:xs)  = drop# (m# -# 1#) xs
 198
 199 splitAt :: Int -> [b] -> ([b], [b])
 200 splitAt (I# n#) xs
 201   | n# <# 0#    = error "splitAt{PreludeList}: negative index"
 202   | otherwise   = splitAt# n# xs
 203     where
 204         splitAt# :: Int# -> [a] -> ([a], [a])
 205         splitAt# 0# xs     = ([], xs)
 206         splitAt# _  []     = ([], [])
 207         splitAt# m# (x:xs) = (x:xs', xs'')
 208           where
 209             (xs', xs'') = splitAt# (m# -# 1#) xs
 210
 211 #endif /* USE_REPORT_PRELUDE */
 212
 213 span, break             :: (a -> Bool) -> [a] -> ([a],[a])
 214 span p []               =  ([],[])
 215 span p xs@(x:xs')
 216          | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
 217          | otherwise    =  ([],xs)
 218
 219 #ifdef USE_REPORT_PRELUDE
 220 break p                 =  span (not . p)
 221 #else
 222 -- HBC version (stolen)
 223 break p []              =  ([],[])
 224 break p xs@(x:xs')
 225            | p x        =  ([],xs)
 226            | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
 227 #endif
 228
 229 -- reverse xs returns the elements of xs in reverse order.  xs must be finite.
 230 reverse                 :: [a] -> [a]
 231 #ifdef USE_REPORT_PRELUDE
 232 reverse                 =  foldl (flip (:)) []
 233 #else
 234 reverse l =  rev l []
 235   where
 236     rev []     a = a
 237     rev (x:xs) a = rev xs (x:a)
 238 #endif
 239
 240 -- and returns the conjunction of a Boolean list.  For the result to be
 241 -- True, the list must be finite; False, however, results from a False
 242 -- value at a finite index of a finite or infinite list.  or is the
 243 -- disjunctive dual of and.
 244 and, or                 :: [Bool] -> Bool
 245 #ifdef USE_REPORT_PRELUDE
 246 and                     =  foldr (&&) True
 247 or                      =  foldr (||) False
 248 #else
 249 and []          =  True
 250 and (x:xs)      =  x && and xs
 251 or []           =  False
 252 or (x:xs)       =  x || or xs
 253 #endif
 254
 255 -- Applied to a predicate and a list, any determines if any element
 256 -- of the list satisfies the predicate.  Similarly, for all.
 257 any, all                :: (a -> Bool) -> [a] -> Bool
 258 #ifdef USE_REPORT_PRELUDE
 259 any p                   =  or . map p
 260 all p                   =  and . map p
 261 #else
 262 any p []        = False
 263 any p (x:xs)    = p x || any p xs
 264 all p []        =  True
 265 all p (x:xs)    =  p x && all p xs
 266 #endif
 267
 268 -- elem is the list membership predicate, usually written in infix form,
 269 -- e.g., x `elem` xs.  notElem is the negation.
 270 elem, notElem           :: (Eq a) => a -> [a] -> Bool
 271 #ifdef USE_REPORT_PRELUDE
 272 elem x                  =  any (== x)
 273 notElem x               =  all (/= x)
 274 #else
 275 elem _ []       = False
 276 elem x (y:ys)   = x==y || elem x ys
 277
 278 notElem x []    =  True
 279 notElem x (y:ys)=  x /= y && notElem x ys
 280 #endif
 281
 282 -- lookup key assocs looks up a key in an association list.
 283 lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
 284 lookup key []           =  Nothing
 285 lookup key ((x,y):xys)
 286     | key == x          =  Just y
 287     | otherwise         =  lookup key xys
 288
 289 -- sum and product compute the sum or product of a finite list of numbers.
 290 sum, product            :: (Num a) => [a] -> a
 291 #ifdef USE_REPORT_PRELUDE
 292 sum                     =  foldl (+) 0
 293 product                 =  foldl (*) 1
 294 #else
 295 sum     l       = sum' l 0
 296   where
 297     sum' []     a = a
 298     sum' (x:xs) a = sum' xs (a+x)
 299 product l       = prod l 1
 300   where
 301     prod []     a = a
 302     prod (x:xs) a = prod xs (a*x)
 303 #endif
 304
 305 -- maximum and minimum return the maximum or minimum value from a list,
 306 -- which must be non-empty, finite, and of an ordered type.
 307 maximum, minimum        :: (Ord a) => [a] -> a
 308 maximum []              =  error "PreludeList.maximum: empty list"
 309 maximum xs              =  foldl1 max xs
 310
 311 minimum []              =  error "PreludeList.minimum: empty list"
 312 minimum xs              =  foldl1 min xs
 313
 314 concatMap               :: (a -> [b]) -> [a] -> [b]
 315 concatMap f             =  foldr ((++) . f) []
 316 \end{code}
 317
 318
 319 %*********************************************************
 320 %*                                                      *
 321 \subsection{The zip family}
 322 %*                                                      *
 323 %*********************************************************
 324
 325 zip takes two lists and returns a list of corresponding pairs.  If one
 326 input list is short, excess elements of the longer list are discarded.
 327 zip3 takes three lists and returns a list of triples.  Zips for larger
 328 tuples are in the List library
 329
 330 \begin{code}
 331 zip                     :: [a] -> [b] -> [(a,b)]
 332 zip                     =  zipWith (,)
 333
 334 zip3                    :: [a] -> [b] -> [c] -> [(a,b,c)]
 335 zip3                    =  zipWith3 (,,)
 336
 337 -- The zipWith family generalises the zip family by zipping with the
 338 -- function given as the first argument, instead of a tupling function.
 339 -- For example, zipWith (+) is applied to two lists to produce the list
 340 -- of corresponding sums.
 341
 342 zipWith                 :: (a->b->c) -> [a]->[b]->[c]
 343 zipWith z (a:as) (b:bs) =  z a b : zipWith z as bs
 344 zipWith _ _ _           =  []
 345
 346 zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
 347 zipWith3 z (a:as) (b:bs) (c:cs)
 348                         =  z a b c : zipWith3 z as bs cs
 349 zipWith3 _ _ _ _        =  []
 350
 351
 352 -- unzip transforms a list of pairs into a pair of lists.
 353
 354 unzip                   :: [(a,b)] -> ([a],[b])
 355 unzip                   =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
 356
 357 unzip3                  :: [(a,b,c)] -> ([a],[b],[c])
 358 unzip3                  =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
 359                                  ([],[],[])
 360 \end{code}
 361
 362 %*********************************************************
 363 %*                                                      *
 364 \subsection{Functions on strings}
 365 %*                                                      *
 366 %*********************************************************
 367
 368 lines breaks a string up into a list of strings at newline characters.
 369 The resulting strings do not contain newlines.  Similary, words
 370 breaks a string up into a list of words, which were delimited by
 371 white space.  unlines and unwords are the inverse operations.
 372 unlines joins lines with terminating newlines, and unwords joins
 373 words with separating spaces.
 374
 375 \begin{code}
 376 lines                   :: String -> [String]
 377 lines ""                =  []
 378 lines s                 =  let (l, s') = break (== '\n') s
 379                            in  l : case s' of
 380                                         []      -> []
 381                                         (_:s'') -> lines s''
 382
 383 words                   :: String -> [String]
 384 words s                 =  case dropWhile {-partain:Char.-}isSpace s of
 385                                 "" -> []
 386                                 s' -> w : words s''
 387                                       where (w, s'') =
 388                                              break {-partain:Char.-}isSpace s'
 389
 390 unlines                 :: [String] -> String
 391 #ifdef USE_REPORT_PRELUDE
 392 unlines                 =  concatMap (++ "\n")
 393 #else
 394 -- HBC version (stolen)
 395 -- here's a more efficient version
 396 unlines [] = []
 397 unlines (l:ls) = l ++ '\n' : unlines ls
 398
 399 #endif
 400
 401 unwords                 :: [String] -> String
 402 #ifdef USE_REPORT_PRELUDE
 403 unwords []              =  ""
 404 unwords ws              =  foldr1 (\w s -> w ++ ' ':s) ws
 405 #else
 406 -- HBC version (stolen)
 407 -- here's a more efficient version
 408 unwords []              =  ""
 409 unwords [w]             = w
 410 unwords (w:ws)          = w ++ ' ' : unwords ws
 411 #endif
 412
 413 \end{code}