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