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 []                 =  error "PreludeList.head: empty list"
  48
  49 last                    :: [a] -> a
  50 last [x]                =  x
  51 last (_:xs)             =  last xs
  52 last []                 =  error "PreludeList.last: empty list"
  53
  54 tail                    :: [a] -> [a]
  55 tail (_:xs)             =  xs
  56 tail []                 =  error "PreludeList.tail: empty list"
  57
  58 init                    :: [a] -> [a]
  59 init [x]                =  []
  60 init (x:xs)             =  x : init xs
  61 init []                 =  error "PreludeList.init: empty list"
  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 _ []             =  error "PreludeList.foldl1: empty list"
 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 _ []             =  error "PreludeList.scanl1: empty list"
 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 _ []             =  error "PreludeList.foldr1: empty list"
 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 _ []             =  error "PreludeList.scanr1: empty list"
 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 _     _           =  error "PreludeList.take: negative argument"
 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 _     _           =  error "PreludeList.drop: negative argument"
 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 _     _           =  error "PreludeList.splitAt: negative argument"
 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 =  error "take{PreludeList}: negative index"
 185
 186 take_unsafe_UInt 0# _     = []
 187 take_unsafe_UInt _  []    = []
 188 take_unsafe_UInt m (x:xs) = x : take_unsafe_UInt (m -# 1#) xs
 189
 190 drop            :: Int -> [b] -> [b]
 191 drop (I# n#) xs
 192   | n# <# 0#    = error "drop{PreludeList}: negative index"
 193   | otherwise   = drop# n# xs
 194     where
 195         drop# :: Int# -> [a] -> [a]
 196         drop# 0# xs      = xs
 197         drop# _  []      = []
 198         drop# m# (_:xs)  = drop# (m# -# 1#) xs
 199
 200 splitAt :: Int -> [b] -> ([b], [b])
 201 splitAt (I# n#) xs
 202   | n# <# 0#    = error "splitAt{PreludeList}: negative index"
 203   | otherwise   = splitAt# n# xs
 204     where
 205         splitAt# :: Int# -> [a] -> ([a], [a])
 206         splitAt# 0# xs     = ([], xs)
 207         splitAt# _  []     = ([], [])
 208         splitAt# m# (x:xs) = (x:xs', xs'')
 209           where
 210             (xs', xs'') = splitAt# (m# -# 1#) xs
 211
 212 #endif /* USE_REPORT_PRELUDE */
 213
 214 span, break             :: (a -> Bool) -> [a] -> ([a],[a])
 215 span p []               =  ([],[])
 216 span p xs@(x:xs')
 217          | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
 218          | otherwise    =  ([],xs)
 219
 220 #ifdef USE_REPORT_PRELUDE
 221 break p                 =  span (not . p)
 222 #else
 223 -- HBC version (stolen)
 224 break p []              =  ([],[])
 225 break p xs@(x:xs')
 226            | p x        =  ([],xs)
 227            | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
 228 #endif
 229
 230 -- reverse xs returns the elements of xs in reverse order.  xs must be finite.
 231 reverse                 :: [a] -> [a]
 232 #ifdef USE_REPORT_PRELUDE
 233 reverse                 =  foldl (flip (:)) []
 234 #else
 235 reverse l =  rev l []
 236   where
 237     rev []     a = a
 238     rev (x:xs) a = rev xs (x:a)
 239 #endif
 240
 241 -- and returns the conjunction of a Boolean list.  For the result to be
 242 -- True, the list must be finite; False, however, results from a False
 243 -- value at a finite index of a finite or infinite list.  or is the
 244 -- disjunctive dual of and.
 245 and, or                 :: [Bool] -> Bool
 246 #ifdef USE_REPORT_PRELUDE
 247 and                     =  foldr (&&) True
 248 or                      =  foldr (||) False
 249 #else
 250 and []          =  True
 251 and (x:xs)      =  x && and xs
 252 or []           =  False
 253 or (x:xs)       =  x || or xs
 254 #endif
 255
 256 -- Applied to a predicate and a list, any determines if any element
 257 -- of the list satisfies the predicate.  Similarly, for all.
 258 any, all                :: (a -> Bool) -> [a] -> Bool
 259 #ifdef USE_REPORT_PRELUDE
 260 any p                   =  or . map p
 261 all p                   =  and . map p
 262 #else
 263 any p []        = False
 264 any p (x:xs)    = p x || any p xs
 265 all p []        =  True
 266 all p (x:xs)    =  p x && all p xs
 267 #endif
 268
 269 -- elem is the list membership predicate, usually written in infix form,
 270 -- e.g., x `elem` xs.  notElem is the negation.
 271 elem, notElem           :: (Eq a) => a -> [a] -> Bool
 272 #ifdef USE_REPORT_PRELUDE
 273 elem x                  =  any (== x)
 274 notElem x               =  all (/= x)
 275 #else
 276 elem _ []       = False
 277 elem x (y:ys)   = x==y || elem x ys
 278
 279 notElem x []    =  True
 280 notElem x (y:ys)=  x /= y && notElem x ys
 281 #endif
 282
 283 -- lookup key assocs looks up a key in an association list.
 284 lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
 285 lookup key []           =  Nothing
 286 lookup key ((x,y):xys)
 287     | key == x          =  Just y
 288     | otherwise         =  lookup key xys
 289
 290 -- sum and product compute the sum or product of a finite list of numbers.
 291 sum, product            :: (Num a) => [a] -> a
 292 #ifdef USE_REPORT_PRELUDE
 293 sum                     =  foldl (+) 0
 294 product                 =  foldl (*) 1
 295 #else
 296 sum     l       = sum' l 0
 297   where
 298     sum' []     a = a
 299     sum' (x:xs) a = sum' xs (a+x)
 300 product l       = prod l 1
 301   where
 302     prod []     a = a
 303     prod (x:xs) a = prod xs (a*x)
 304 #endif
 305
 306 -- maximum and minimum return the maximum or minimum value from a list,
 307 -- which must be non-empty, finite, and of an ordered type.
 308 maximum, minimum        :: (Ord a) => [a] -> a
 309 maximum []              =  error "PreludeList.maximum: empty list"
 310 maximum xs              =  foldl1 max xs
 311
 312 minimum []              =  error "PreludeList.minimum: empty list"
 313 minimum xs              =  foldl1 min xs
 314
 315 concatMap               :: (a -> [b]) -> [a] -> [b]
 316 concatMap f             =  foldr ((++) . f) []
 317 \end{code}
 318
 319
 320 %*********************************************************
 321 %*                                                      *
 322 \subsection{The zip family}
 323 %*                                                      *
 324 %*********************************************************
 325
 326 zip takes two lists and returns a list of corresponding pairs.  If one
 327 input list is short, excess elements of the longer list are discarded.
 328 zip3 takes three lists and returns a list of triples.  Zips for larger
 329 tuples are in the List library
 330
 331 \begin{code}
 332 zip                     :: [a] -> [b] -> [(a,b)]
 333 -- Specification
 334 -- zip =  zipWith (,)
 335 zip (a:as) (b:bs) = (a,b) : zip as bs
 336 zip _      _      = []
 337
 338 zip3                    :: [a] -> [b] -> [c] -> [(a,b,c)]
 339 -- Specification
 340 -- zip3 =  zipWith3 (,,)
 341 zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
 342 zip3 _      _      _      = []
 343
 344 -- The zipWith family generalises the zip family by zipping with the
 345 -- function given as the first argument, instead of a tupling function.
 346 -- For example, zipWith (+) is applied to two lists to produce the list
 347 -- of corresponding sums.
 348
 349 zipWith                 :: (a->b->c) -> [a]->[b]->[c]
 350 zipWith z (a:as) (b:bs) =  z a b : zipWith z as bs
 351 zipWith _ _ _           =  []
 352
 353 zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
 354 zipWith3 z (a:as) (b:bs) (c:cs)
 355                         =  z a b c : zipWith3 z as bs cs
 356 zipWith3 _ _ _ _        =  []
 357
 358
 359 -- unzip transforms a list of pairs into a pair of lists.
 360
 361 unzip                   :: [(a,b)] -> ([a],[b])
 362 unzip                   =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
 363
 364 unzip3                  :: [(a,b,c)] -> ([a],[b],[c])
 365 unzip3                  =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
 366                                  ([],[],[])
 367 \end{code}
 368
 369 %*********************************************************
 370 %*                                                      *
 371 \subsection{Functions on strings}
 372 %*                                                      *
 373 %*********************************************************
 374
 375 lines breaks a string up into a list of strings at newline characters.
 376 The resulting strings do not contain newlines.  Similary, words
 377 breaks a string up into a list of words, which were delimited by
 378 white space.  unlines and unwords are the inverse operations.
 379 unlines joins lines with terminating newlines, and unwords joins
 380 words with separating spaces.
 381
 382 \begin{code}
 383 lines                   :: String -> [String]
 384 lines ""                =  []
 385 lines s                 =  let (l, s') = break (== '\n') s
 386                            in  l : case s' of
 387                                         []      -> []
 388                                         (_:s'') -> lines s''
 389
 390 words                   :: String -> [String]
 391 words s                 =  case dropWhile {-partain:Char.-}isSpace s of
 392                                 "" -> []
 393                                 s' -> w : words s''
 394                                       where (w, s'') =
 395                                              break {-partain:Char.-}isSpace s'
 396
 397 unlines                 :: [String] -> String
 398 #ifdef USE_REPORT_PRELUDE
 399 unlines                 =  concatMap (++ "\n")
 400 #else
 401 -- HBC version (stolen)
 402 -- here's a more efficient version
 403 unlines [] = []
 404 unlines (l:ls) = l ++ '\n' : unlines ls
 405
 406 #endif
 407
 408 unwords                 :: [String] -> String
 409 #ifdef USE_REPORT_PRELUDE
 410 unwords []              =  ""
 411 unwords ws              =  foldr1 (\w s -> w ++ ' ':s) ws
 412 #else
 413 -- HBC version (stolen)
 414 -- here's a more efficient version
 415 unwords []              =  ""
 416 unwords [w]             = w
 417 unwords (w:ws)          = w ++ ' ' : unwords ws
 418 #endif
 419
 420 \end{code}