e249135b2f07e9bed72ceebad4fe52a9935c524a
[ghc-hetmet.git] / 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}