2 % (c) The AQUA Project, Glasgow University, 1994-1996
5 \section[PrelList]{Module @PrelList@}
7 The List data type and its operations
10 {-# OPTIONS -fno-implicit-prelude #-}
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
25 import {-# SOURCE #-} GHCerr ( error )
30 infix 4 `elem`, `notElem`
33 %*********************************************************
35 \subsection{List-manipulation functions}
37 %*********************************************************
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.
47 head [] = error "PreludeList.head: empty list"
52 last [] = error "PreludeList.last: empty list"
56 tail [] = error "PreludeList.tail: empty list"
60 init (x:xs) = x : init xs
61 init [] = error "PreludeList.init: empty list"
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.
71 #ifdef USE_REPORT_PRELUDE
73 length (_:l) = 1 + length l
77 len :: [a] -> Int# -> Int
79 len (_:xs) a# = len xs (a# +# 1#)
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, ...]
94 foldl :: (a -> b -> a) -> a -> [b] -> a
96 foldl f z (x:xs) = foldl f (f z x) xs
98 foldl1 :: (a -> a -> a) -> [a] -> a
99 foldl1 f (x:xs) = foldl f x xs
100 foldl1 _ [] = error "PreludeList.foldl1: empty list"
102 scanl :: (a -> b -> a) -> a -> [b] -> [a]
103 scanl f q xs = q : (case xs of
105 x:xs -> scanl f (f q x) xs)
107 scanl1 :: (a -> a -> a) -> [a] -> [a]
108 scanl1 f (x:xs) = scanl f x xs
109 scanl1 _ [] = error "PreludeList.scanl1: empty list"
111 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
114 foldr1 :: (a -> a -> a) -> [a] -> a
116 foldr1 f (x:xs) = f x (foldr1 f xs)
117 foldr1 _ [] = error "PreludeList.foldr1: empty list"
119 scanr :: (a -> b -> b) -> b -> [a] -> [b]
121 scanr f q0 (x:xs) = f x q : qs
122 where qs@(q:_) = scanr f q0 xs
124 scanr1 :: (a -> a -> a) -> [a] -> [a]
126 scanr1 f (x:xs) = f x q : qs
127 where qs@(q:_) = scanr1 f xs
128 scanr1 _ [] = error "PreludeList.scanr1: empty list"
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)
135 -- repeat x is an infinite list, with x the value of every element.
137 repeat x = xs where xs = x:xs
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)
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.
148 cycle xs = xs' where xs' = xs ++ xs'
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]
158 take n (x:xs) | n > 0 = x : take (n-1) xs
159 take _ _ = error "PreludeList.take: negative argument"
161 drop :: Int -> [a] -> [a]
164 drop n (_:xs) | n > 0 = drop (n-1) xs
165 drop _ _ = error "PreludeList.drop: negative argument"
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"
173 #else /* hack away */
174 take :: Int -> [b] -> [b]
175 take (I# n#) xs = takeUInt n# xs
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
181 takeUInt :: Int# -> [b] -> [b]
183 | n >=# 0# = take_unsafe_UInt n xs
184 | otherwise = error "take{PreludeList}: negative index"
186 take_unsafe_UInt 0# _ = []
187 take_unsafe_UInt _ [] = []
188 take_unsafe_UInt m (x:xs) = x : take_unsafe_UInt (m -# 1#) xs
190 drop :: Int -> [b] -> [b]
192 | n# <# 0# = error "drop{PreludeList}: negative index"
193 | otherwise = drop# n# xs
195 drop# :: Int# -> [a] -> [a]
198 drop# m# (_:xs) = drop# (m# -# 1#) xs
200 splitAt :: Int -> [b] -> ([b], [b])
202 | n# <# 0# = error "splitAt{PreludeList}: negative index"
203 | otherwise = splitAt# n# xs
205 splitAt# :: Int# -> [a] -> ([a], [a])
206 splitAt# 0# xs = ([], xs)
207 splitAt# _ [] = ([], [])
208 splitAt# m# (x:xs) = (x:xs', xs'')
210 (xs', xs'') = splitAt# (m# -# 1#) xs
212 #endif /* USE_REPORT_PRELUDE */
214 span, break :: (a -> Bool) -> [a] -> ([a],[a])
217 | p x = let (ys,zs) = span p xs' in (x:ys,zs)
218 | otherwise = ([],xs)
220 #ifdef USE_REPORT_PRELUDE
221 break p = span (not . p)
223 -- HBC version (stolen)
227 | otherwise = let (ys,zs) = break p xs' in (x:ys,zs)
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 (:)) []
238 rev (x:xs) a = rev xs (x:a)
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
251 and (x:xs) = x && and xs
253 or (x:xs) = x || or xs
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
264 any p (x:xs) = p x || any p xs
266 all p (x:xs) = p x && all p xs
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
274 notElem x = all (/= x)
277 elem x (y:ys) = x==y || elem x ys
280 notElem x (y:ys)= x /= y && notElem x ys
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)
288 | otherwise = lookup key xys
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
294 product = foldl (*) 1
299 sum' (x:xs) a = sum' xs (a+x)
303 prod (x:xs) a = prod xs (a*x)
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
312 minimum [] = error "PreludeList.minimum: empty list"
313 minimum xs = foldl1 min xs
315 concatMap :: (a -> [b]) -> [a] -> [b]
316 concatMap f = foldr ((++) . f) []
320 %*********************************************************
322 \subsection{The zip family}
324 %*********************************************************
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
332 zip :: [a] -> [b] -> [(a,b)]
335 zip (a:as) (b:bs) = (a,b) : zip as bs
338 zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
340 -- zip3 = zipWith3 (,,)
341 zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
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.
349 zipWith :: (a->b->c) -> [a]->[b]->[c]
350 zipWith z (a:as) (b:bs) = z a b : zipWith z as bs
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 _ _ _ _ = []
359 -- unzip transforms a list of pairs into a pair of lists.
361 unzip :: [(a,b)] -> ([a],[b])
362 unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
364 unzip3 :: [(a,b,c)] -> ([a],[b],[c])
365 unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
369 %*********************************************************
371 \subsection{Functions on strings}
373 %*********************************************************
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.
383 lines :: String -> [String]
385 lines s = let (l, s') = break (== '\n') s
390 words :: String -> [String]
391 words s = case dropWhile {-partain:Char.-}isSpace s of
395 break {-partain:Char.-}isSpace s'
397 unlines :: [String] -> String
398 #ifdef USE_REPORT_PRELUDE
399 unlines = concatMap (++ "\n")
401 -- HBC version (stolen)
402 -- here's a more efficient version
404 unlines (l:ls) = l ++ '\n' : unlines ls
408 unwords :: [String] -> String
409 #ifdef USE_REPORT_PRELUDE
411 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
413 -- HBC version (stolen)
414 -- here's a more efficient version
417 unwords (w:ws) = w ++ ' ' : unwords ws