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