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