ghc/lib/ghc/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 #-}   IOBase  ( error )
  26 import PrelTup
  27 import PrelBase
  28
  29 infix  4 `elem`, `notElem`
  30 \end{code}
  31
  32 %*********************************************************
  33 %*                                                      *
  34 \subsection{List-manipulation functions}
  35 %*                                                      *
  36 %*********************************************************
  37
  38 \begin{code}
  39 -- head and tail extract the first element and remaining elements,
  40 -- respectively, of a list, which must be non-empty.  last and init
  41 -- are the dual functions working from the end of a finite list,
  42 -- rather than the beginning.
  43
  44 head                    :: [a] -> a
  45 head (x:_)              =  x
  46 head []                 =  error "PreludeList.head: empty list"
  47
  48 last                    :: [a] -> a
  49 last [x]                =  x
  50 last (_:xs)             =  last xs
  51 last []                 =  error "PreludeList.last: empty list"
  52
  53 tail                    :: [a] -> [a]
  54 tail (_:xs)             =  xs
  55 tail []                 =  error "PreludeList.tail: empty list"
  56
  57 init                    :: [a] -> [a]
  58 init [x]                =  []
  59 init (x:xs)             =  x : init xs
  60 init []                 =  error "PreludeList.init: empty list"
  61
  62 null                    :: [a] -> Bool
  63 null []                 =  True
  64 null (_:_)              =  False
  65
  66 -- length returns the length of a finite list as an Int; it is an instance
  67 -- of the more general genericLength, the result type of which may be
  68 -- any kind of number.
  69 length                  :: [a] -> Int
  70 length []               =  0
  71 length (_:l)            =  1 + length l
  72
  73 -- foldl, applied to a binary operator, a starting value (typically the
  74 -- left-identity of the operator), and a list, reduces the list using
  75 -- the binary operator, from left to right:
  76 --  foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
  77 -- foldl1 is a variant that has no starting value argument, and  thus must
  78 -- be applied to non-empty lists.  scanl is similar to foldl, but returns
  79 -- a list of successive reduced values from the left:
  80 --      scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
  81 -- Note that  last (scanl f z xs) == foldl f z xs.
  82 -- scanl1 is similar, again without the starting element:
  83 --      scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
  84
  85 foldl                   :: (a -> b -> a) -> a -> [b] -> a
  86 foldl f z []            =  z
  87 foldl f z (x:xs)        =  foldl f (f z x) xs
  88
  89 foldl1                  :: (a -> a -> a) -> [a] -> a
  90 foldl1 f (x:xs)         =  foldl f x xs
  91 foldl1 _ []             =  error "PreludeList.foldl1: empty list"
  92
  93 scanl                   :: (a -> b -> a) -> a -> [b] -> [a]
  94 scanl f q xs            =  q : (case xs of
  95                                 []   -> []
  96                                 x:xs -> scanl f (f q x) xs)
  97
  98 scanl1                  :: (a -> a -> a) -> [a] -> [a]
  99 scanl1 f (x:xs)         =  scanl f x xs
 100 scanl1 _ []             =  error "PreludeList.scanl1: empty list"
 101
 102 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
 103 -- above functions.
 104
 105 foldr1                  :: (a -> a -> a) -> [a] -> a
 106 foldr1 f [x]            =  x
 107 foldr1 f (x:xs)         =  f x (foldr1 f xs)
 108 foldr1 _ []             =  error "PreludeList.foldr1: empty list"
 109
 110 scanr                   :: (a -> b -> b) -> b -> [a] -> [b]
 111 scanr f q0 []           =  [q0]
 112 scanr f q0 (x:xs)       =  f x q : qs
 113                            where qs@(q:_) = scanr f q0 xs
 114
 115 scanr1                  :: (a -> a -> a) -> [a] -> [a]
 116 scanr1 f  [x]           =  [x]
 117 scanr1 f  (x:xs)        =  f x q : qs
 118                            where qs@(q:_) = scanr1 f xs
 119 scanr1 _ []             =  error "PreludeList.scanr1: empty list"
 120
 121 -- iterate f x returns an infinite list of repeated applications of f to x:
 122 -- iterate f x == [x, f x, f (f x), ...]
 123 iterate                 :: (a -> a) -> a -> [a]
 124 iterate f x             =  x : iterate f (f x)
 125
 126 -- repeat x is an infinite list, with x the value of every element.
 127 repeat                  :: a -> [a]
 128 repeat x                =  xs where xs = x:xs
 129
 130 -- replicate n x is a list of length n with x the value of every element
 131 replicate               :: Int -> a -> [a]
 132 replicate n x           =  take n (repeat x)
 133
 134 -- cycle ties a finite list into a circular one, or equivalently,
 135 -- the infinite repetition of the original list.  It is the identity
 136 -- on infinite lists.
 137
 138 cycle                   :: [a] -> [a]
 139 cycle xs                =  xs' where xs' = xs ++ xs'
 140
 141 -- take n, applied to a list xs, returns the prefix of xs of length n,
 142 -- or xs itself if n > length xs.  drop n xs returns the suffix of xs
 143 -- after the first n elements, or [] if n > length xs.  splitAt n xs
 144 -- is equivalent to (take n xs, drop n xs).
 145
 146 take                   :: Int -> [a] -> [a]
 147 take 0 _               =  []
 148 take _ []              =  []
 149 take n (x:xs) | n > 0  =  x : take (n-1) xs
 150 take _     _           =  error "PreludeList.take: negative argument"
 151
 152 drop                   :: Int -> [a] -> [a]
 153 drop 0 xs              =  xs
 154 drop _ []              =  []
 155 drop n (_:xs) | n > 0  =  drop (n-1) xs
 156 drop _     _           =  error "PreludeList.drop: negative argument"
 157
 158 splitAt                   :: Int -> [a] -> ([a],[a])
 159 splitAt 0 xs              =  ([],xs)
 160 splitAt _ []              =  ([],[])
 161 splitAt n (x:xs) | n > 0  =  (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs
 162 splitAt _     _           =  error "PreludeList.splitAt: negative argument"
 163
 164 span, break             :: (a -> Bool) -> [a] -> ([a],[a])
 165 span p []               =  ([],[])
 166 span p xs@(x:xs')
 167          | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
 168          | otherwise    =  ([],xs)
 169 break p                 =  span (not . p)
 170
 171 -- reverse xs returns the elements of xs in reverse order.  xs must be finite.
 172 reverse                 :: [a] -> [a]
 173 reverse                 =  foldl (flip (:)) []
 174
 175 -- and returns the conjunction of a Boolean list.  For the result to be
 176 -- True, the list must be finite; False, however, results from a False
 177 -- value at a finite index of a finite or infinite list.  or is the
 178 -- disjunctive dual of and.
 179 and, or                 :: [Bool] -> Bool
 180 and                     =  foldr (&&) True
 181 or                      =  foldr (||) False
 182
 183 -- Applied to a predicate and a list, any determines if any element
 184 -- of the list satisfies the predicate.  Similarly, for all.
 185 any, all                :: (a -> Bool) -> [a] -> Bool
 186 any p                   =  or . map p
 187 all p                   =  and . map p
 188
 189 -- elem is the list membership predicate, usually written in infix form,
 190 -- e.g., x `elem` xs.  notElem is the negation.
 191 elem, notElem           :: (Eq a) => a -> [a] -> Bool
 192 elem x                  =  any (== x)
 193 notElem x               =  all (/= x)
 194
 195 -- lookup key assocs looks up a key in an association list.
 196 lookup                  :: (Eq a) => a -> [(a,b)] -> Maybe b
 197 lookup key []           =  Nothing
 198 lookup key ((x,y):xys)
 199     | key == x          =  Just y
 200     | otherwise         =  lookup key xys
 201
 202 -- sum and product compute the sum or product of a finite list of numbers.
 203 sum, product            :: (Num a) => [a] -> a
 204 sum                     =  foldl (+) 0
 205 product                 =  foldl (*) 1
 206
 207 -- maximum and minimum return the maximum or minimum value from a list,
 208 -- which must be non-empty, finite, and of an ordered type.
 209 maximum, minimum        :: (Ord a) => [a] -> a
 210 maximum []              =  error "PreludeList.maximum: empty list"
 211 maximum xs              =  foldl1 max xs
 212
 213 minimum []              =  error "PreludeList.minimum: empty list"
 214 minimum xs              =  foldl1 min xs
 215
 216 concatMap               :: (a -> [b]) -> [a] -> [b]
 217 concatMap f             =  foldr ((++) . f) []
 218 \end{code}
 219
 220
 221 %*********************************************************
 222 %*                                                      *
 223 \subsection{The zip family}
 224 %*                                                      *
 225 %*********************************************************
 226
 227 zip takes two lists and returns a list of corresponding pairs.  If one
 228 input list is short, excess elements of the longer list are discarded.
 229 zip3 takes three lists and returns a list of triples.  Zips for larger
 230 tuples are in the List library
 231
 232 \begin{code}
 233 zip                     :: [a] -> [b] -> [(a,b)]
 234 zip                     =  zipWith (,)
 235
 236 zip3                    :: [a] -> [b] -> [c] -> [(a,b,c)]
 237 zip3                    =  zipWith3 (,,)
 238
 239 -- The zipWith family generalises the zip family by zipping with the
 240 -- function given as the first argument, instead of a tupling function.
 241 -- For example, zipWith (+) is applied to two lists to produce the list
 242 -- of corresponding sums.
 243
 244 zipWith                 :: (a->b->c) -> [a]->[b]->[c]
 245 zipWith z (a:as) (b:bs) =  z a b : zipWith z as bs
 246 zipWith _ _ _           =  []
 247
 248 zipWith3                :: (a->b->c->d) -> [a]->[b]->[c]->[d]
 249 zipWith3 z (a:as) (b:bs) (c:cs)
 250                         =  z a b c : zipWith3 z as bs cs
 251 zipWith3 _ _ _ _        =  []
 252
 253
 254 -- unzip transforms a list of pairs into a pair of lists.
 255
 256 unzip                   :: [(a,b)] -> ([a],[b])
 257 unzip                   =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
 258
 259 unzip3                  :: [(a,b,c)] -> ([a],[b],[c])
 260 unzip3                  =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
 261                                  ([],[],[])
 262 \end{code}
 263
 264 %*********************************************************
 265 %*                                                      *
 266 \subsection{Functions on strings}
 267 %*                                                      *
 268 %*********************************************************
 269
 270 lines breaks a string up into a list of strings at newline characters.
 271 The resulting strings do not contain newlines.  Similary, words
 272 breaks a string up into a list of words, which were delimited by
 273 white space.  unlines and unwords are the inverse operations.
 274 unlines joins lines with terminating newlines, and unwords joins
 275 words with separating spaces.
 276
 277 \begin{code}
 278 lines                   :: String -> [String]
 279 lines ""                =  []
 280 lines s                 =  let (l, s') = break (== '\n') s
 281                            in  l : case s' of
 282                                         []      -> []
 283                                         (_:s'') -> lines s''
 284
 285 words                   :: String -> [String]
 286 words s                 =  case dropWhile {-partain:Char.-}isSpace s of
 287                                 "" -> []
 288                                 s' -> w : words s''
 289                                       where (w, s'') =
 290                                              break {-partain:Char.-}isSpace s'
 291
 292 unlines                 :: [String] -> String
 293 unlines                 =  concatMap (++ "\n")
 294
 295 unwords                 :: [String] -> String
 296 unwords []              =  ""
 297 unwords ws              =  foldr1 (\w s -> w ++ ' ':s) ws
 298 \end{code}