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 sum, product            :: (Num a) => [a] -> a
 294 #ifdef USE_REPORT_PRELUDE
 295 sum                     =  foldl (+) 0
 296 product                 =  foldl (*) 1
 297 #else
 298 sum     l       = sum' l 0
 299   where
 300     sum' []     a = a
 301     sum' (x:xs) a = sum' xs (a+x)
 302 product l       = prod l 1
 303   where
 304     prod []     a = a
 305     prod (x:xs) a = prod xs (a*x)
 306 #endif
 307
 308 -- maximum and minimum return the maximum or minimum value from a list,
 309 -- which must be non-empty, finite, and of an ordered type.
 310 maximum, minimum        :: (Ord a) => [a] -> a
 311 maximum []              =  errorEmptyList "maximum"
 312 maximum xs              =  foldl1 max xs
 313
 314 minimum []              =  errorEmptyList "minimum"
 315 minimum xs              =  foldl1 min xs
 316
 317 concatMap               :: (a -> [b]) -> [a] -> [b]
 318 concatMap f             =  foldr ((++) . f) []
 319 \end{code}
 320
 321
 322 %*********************************************************
 323 %*                                                      *
 324 \subsection{The zip family}
 325 %*                                                      *
 326 %*********************************************************
 327
 328 zip takes two lists and returns a list of corresponding pairs.  If one
 329 input list is short, excess elements of the longer list are discarded.
 330 zip3 takes three lists and returns a list of triples.  Zips for larger
 331 tuples are in the List library
 332
 333 \begin{code}
 334 zip                     :: [a] -> [b] -> [(a,b)]
 335 -- Specification
 336 -- zip =  zipWith (,)
 337 zip (a:as) (b:bs) = (a,b) : zip as bs
 338 zip _      _      = []
 339
 340 zip3                    :: [a] -> [b] -> [c] -> [(a,b,c)]
 341 -- Specification
 342 -- zip3 =  zipWith3 (,,)
 343 zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
 344 zip3 _      _      _      = []
 345
 346 -- The zipWith family generalises the zip family by zipping with the
 347 -- function given as the first argument, instead of a tupling function.
 348 -- For example, zipWith (+) is applied to two lists to produce the list
 349 -- of corresponding sums.
 350
 351 zipWith                 :: (a->b->c) -> [a]->[b]->[c]
 352 zipWith z (a:as) (b:bs) =  z a b : zipWith z as bs
 353 zipWith _ _ _           =  []
 354
 355 zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
 356 zipWith3 z (a:as) (b:bs) (c:cs)
 357                         =  z a b c : zipWith3 z as bs cs
 358 zipWith3 _ _ _ _        =  []
 359
 360
 361 -- unzip transforms a list of pairs into a pair of lists.
 362
 363 unzip                   :: [(a,b)] -> ([a],[b])
 364 unzip                   =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
 365
 366 unzip3                  :: [(a,b,c)] -> ([a],[b],[c])
 367 unzip3                  =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
 368                                  ([],[],[])
 369 \end{code}
 370
 371 %*********************************************************
 372 %*                                                      *
 373 \subsection{Functions on strings}
 374 %*                                                      *
 375 %*********************************************************
 376
 377 lines breaks a string up into a list of strings at newline characters.
 378 The resulting strings do not contain newlines.  Similary, words
 379 breaks a string up into a list of words, which were delimited by
 380 white space.  unlines and unwords are the inverse operations.
 381 unlines joins lines with terminating newlines, and unwords joins
 382 words with separating spaces.
 383
 384 \begin{code}
 385 lines                   :: String -> [String]
 386 lines ""                =  []
 387 lines s                 =  let (l, s') = break (== '\n') s
 388                            in  l : case s' of
 389                                         []      -> []
 390                                         (_:s'') -> lines s''
 391
 392 words                   :: String -> [String]
 393 words s                 =  case dropWhile {-partain:Char.-}isSpace s of
 394                                 "" -> []
 395                                 s' -> w : words s''
 396                                       where (w, s'') =
 397                                              break {-partain:Char.-}isSpace s'
 398
 399 unlines                 :: [String] -> String
 400 #ifdef USE_REPORT_PRELUDE
 401 unlines                 =  concatMap (++ "\n")
 402 #else
 403 -- HBC version (stolen)
 404 -- here's a more efficient version
 405 unlines [] = []
 406 unlines (l:ls) = l ++ '\n' : unlines ls
 407
 408 #endif
 409
 410 unwords                 :: [String] -> String
 411 #ifdef USE_REPORT_PRELUDE
 412 unwords []              =  ""
 413 unwords ws              =  foldr1 (\w s -> w ++ ' ':s) ws
 414 #else
 415 -- HBC version (stolen)
 416 -- here's a more efficient version
 417 unwords []              =  ""
 418 unwords [w]             = w
 419 unwords (w:ws)          = w ++ ' ' : unwords ws
 420 #endif
 421
 422 \end{code}
 423
 424 Common up near identical calls to `error' to reduce the number
 425 constant strings created when compiled:
 426
 427 \begin{code}
 428 errorEmptyList fun =
 429   error (prel_list_str ++ fun ++ ": empty list")
 430
 431 errorNegativeIdx fun =
 432  error (prel_list_str ++ fun ++ ": negative index")
 433
 434 prel_list_str = "PreludeList."
 435 \end{code}