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 #-} PrelErr ( 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 [] = errorEmptyList "head"
52 last [] = errorEmptyList "last"
56 tail [] = errorEmptyList "tail"
60 init (x:xs) = x : init xs
61 init [] = errorEmptyList "init"
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 _ [] = errorEmptyList "foldl1"
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 _ [] = errorEmptyList "scanl1"
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 _ [] = errorEmptyList "foldr1"
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 _ [] = errorEmptyList "scanr1"
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 _ _ = errorNegativeIdx "take"
161 drop :: Int -> [a] -> [a]
164 drop n (_:xs) | n > 0 = drop (n-1) xs
165 drop _ _ = errorNegativeIdx "drop"
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"
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 = errorNegativeIdx "take"
186 take_unsafe_UInt 0# _ = []
187 take_unsafe_UInt m ls =
190 (x:xs) -> x : take_unsafe_UInt (m -# 1#) xs
192 drop :: Int -> [b] -> [b]
194 | n# <# 0# = errorNegativeIdx "drop"
195 | otherwise = drop# n# xs
197 drop# :: Int# -> [a] -> [a]
200 drop# m# (_:xs) = drop# (m# -# 1#) xs
202 splitAt :: Int -> [b] -> ([b], [b])
204 | n# <# 0# = errorNegativeIdx "splitAt"
205 | otherwise = splitAt# n# xs
207 splitAt# :: Int# -> [a] -> ([a], [a])
208 splitAt# 0# xs = ([], xs)
209 splitAt# _ xs@[] = (xs, xs)
210 splitAt# m# (x:xs) = (x:xs', xs'')
212 (xs', xs'') = splitAt# (m# -# 1#) xs
214 #endif /* USE_REPORT_PRELUDE */
216 span, break :: (a -> Bool) -> [a] -> ([a],[a])
217 span p xs@[] = (xs, xs)
219 | p x = let (ys,zs) = span p xs' in (x:ys,zs)
220 | otherwise = ([],xs)
222 #ifdef USE_REPORT_PRELUDE
223 break p = span (not . p)
225 -- HBC version (stolen)
226 break p xs@[] = (xs, xs)
229 | otherwise = let (ys,zs) = break p xs' in (x:ys,zs)
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 (:)) []
240 rev (x:xs) a = rev xs (x:a)
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
253 and (x:xs) = x && and xs
255 or (x:xs) = x || or xs
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
266 any p (x:xs) = p x || any p xs
268 all p (x:xs) = p x && all p xs
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
276 notElem x = all (/= x)
279 elem x (y:ys) = x==y || elem x ys
282 notElem x (y:ys)= x /= y && notElem x ys
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)
290 | otherwise = lookup key xys
292 -- sum and product compute the sum or product of a finite list of numbers.
293 {-# SPECIALISE sum :: [Int] -> Int #-}
294 {-# SPECIALISE product :: [Int] -> Int #-}
295 sum, product :: (Num a) => [a] -> a
296 #ifdef USE_REPORT_PRELUDE
298 product = foldl (*) 1
303 sum' (x:xs) a = sum' xs (a+x)
307 prod (x:xs) a = prod xs (a*x)
310 -- maximum and minimum return the maximum or minimum value from a list,
311 -- which must be non-empty, finite, and of an ordered type.
312 {-# SPECIALISE maximum :: [Int] -> Int #-}
313 {-# SPECIALISE minimum :: [Int] -> Int #-}
314 maximum, minimum :: (Ord a) => [a] -> a
315 maximum [] = errorEmptyList "maximum"
316 maximum xs = foldl1 max xs
318 minimum [] = errorEmptyList "minimum"
319 minimum xs = foldl1 min xs
321 concatMap :: (a -> [b]) -> [a] -> [b]
322 concatMap f = foldr ((++) . f) []
326 %*********************************************************
328 \subsection{The zip family}
330 %*********************************************************
332 zip takes two lists and returns a list of corresponding pairs. If one
333 input list is short, excess elements of the longer list are discarded.
334 zip3 takes three lists and returns a list of triples. Zips for larger
335 tuples are in the List library
338 zip :: [a] -> [b] -> [(a,b)]
341 zip (a:as) (b:bs) = (a,b) : zip as bs
344 zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
346 -- zip3 = zipWith3 (,,)
347 zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
350 -- The zipWith family generalises the zip family by zipping with the
351 -- function given as the first argument, instead of a tupling function.
352 -- For example, zipWith (+) is applied to two lists to produce the list
353 -- of corresponding sums.
355 zipWith :: (a->b->c) -> [a]->[b]->[c]
356 zipWith z (a:as) (b:bs) = z a b : zipWith z as bs
359 zipWith3 :: (a->b->c->d) -> [a]->[b]->[c]->[d]
360 zipWith3 z (a:as) (b:bs) (c:cs)
361 = z a b c : zipWith3 z as bs cs
362 zipWith3 _ _ _ _ = []
365 -- unzip transforms a list of pairs into a pair of lists.
367 unzip :: [(a,b)] -> ([a],[b])
368 unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
370 unzip3 :: [(a,b,c)] -> ([a],[b],[c])
371 unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
375 %*********************************************************
377 \subsection{Functions on strings}
379 %*********************************************************
381 lines breaks a string up into a list of strings at newline characters.
382 The resulting strings do not contain newlines. Similary, words
383 breaks a string up into a list of words, which were delimited by
384 white space. unlines and unwords are the inverse operations.
385 unlines joins lines with terminating newlines, and unwords joins
386 words with separating spaces.
389 lines :: String -> [String]
391 lines s = let (l, s') = break (== '\n') s
396 words :: String -> [String]
397 words s = case dropWhile {-partain:Char.-}isSpace s of
401 break {-partain:Char.-}isSpace s'
403 unlines :: [String] -> String
404 #ifdef USE_REPORT_PRELUDE
405 unlines = concatMap (++ "\n")
407 -- HBC version (stolen)
408 -- here's a more efficient version
410 unlines (l:ls) = l ++ '\n' : unlines ls
414 unwords :: [String] -> String
415 #ifdef USE_REPORT_PRELUDE
417 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
419 -- HBC version (stolen)
420 -- here's a more efficient version
423 unwords (w:ws) = w ++ ' ' : unwords ws
428 Common up near identical calls to `error' to reduce the number
429 constant strings created when compiled:
433 error (prel_list_str ++ fun ++ ": empty list")
435 errorNegativeIdx fun =
436 error (prel_list_str ++ fun ++ ": negative index")
438 prel_list_str = "PreludeList."