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"
51 tail [] = errorEmptyList "tail"
54 #ifdef USE_REPORT_PRELUDE
57 last [] = errorEmptyList "last"
59 -- eliminate repeated cases
60 last [] = errorEmptyList "last"
61 last (x:xs) = last' x xs
63 last' _ (x:xs) = last' x xs
67 #ifdef USE_REPORT_PRELUDE
69 init (x:xs) = x : init xs
70 init [] = errorEmptyList "init"
72 -- eliminate repeated cases
73 init [] = errorEmptyList "init"
74 init (x:xs) = init' x xs
76 init' x (y:xs) = x : init' y xs
83 -- length returns the length of a finite list as an Int; it is an instance
84 -- of the more general genericLength, the result type of which may be
85 -- any kind of number.
87 #ifdef USE_REPORT_PRELUDE
89 length (_:l) = 1 + length l
93 len :: [a] -> Int# -> Int
95 len (_:xs) a# = len xs (a# +# 1#)
98 -- foldl, applied to a binary operator, a starting value (typically the
99 -- left-identity of the operator), and a list, reduces the list using
100 -- the binary operator, from left to right:
101 -- foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
102 -- foldl1 is a variant that has no starting value argument, and thus must
103 -- be applied to non-empty lists. scanl is similar to foldl, but returns
104 -- a list of successive reduced values from the left:
105 -- scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
106 -- Note that last (scanl f z xs) == foldl f z xs.
107 -- scanl1 is similar, again without the starting element:
108 -- scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
110 foldl :: (a -> b -> a) -> a -> [b] -> a
112 foldl f z (x:xs) = foldl f (f z x) xs
114 foldl1 :: (a -> a -> a) -> [a] -> a
115 foldl1 f (x:xs) = foldl f x xs
116 foldl1 _ [] = errorEmptyList "foldl1"
118 scanl :: (a -> b -> a) -> a -> [b] -> [a]
119 scanl f q xs = q : (case xs of
121 x:xs -> scanl f (f q x) xs)
123 scanl1 :: (a -> a -> a) -> [a] -> [a]
124 scanl1 f (x:xs) = scanl f x xs
125 scanl1 _ [] = errorEmptyList "scanl1"
127 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
130 foldr1 :: (a -> a -> a) -> [a] -> a
132 foldr1 f (x:xs) = f x (foldr1 f xs)
133 foldr1 _ [] = errorEmptyList "foldr1"
135 scanr :: (a -> b -> b) -> b -> [a] -> [b]
137 scanr f q0 (x:xs) = f x q : qs
138 where qs@(q:_) = scanr f q0 xs
140 scanr1 :: (a -> a -> a) -> [a] -> [a]
142 scanr1 f (x:xs) = f x q : qs
143 where qs@(q:_) = scanr1 f xs
144 scanr1 _ [] = errorEmptyList "scanr1"
146 -- iterate f x returns an infinite list of repeated applications of f to x:
147 -- iterate f x == [x, f x, f (f x), ...]
148 iterate :: (a -> a) -> a -> [a]
149 iterate f x = x : iterate f (f x)
151 -- repeat x is an infinite list, with x the value of every element.
153 repeat x = xs where xs = x:xs
155 -- replicate n x is a list of length n with x the value of every element
156 replicate :: Int -> a -> [a]
157 replicate n x = take n (repeat x)
159 -- cycle ties a finite list into a circular one, or equivalently,
160 -- the infinite repetition of the original list. It is the identity
161 -- on infinite lists.
164 cycle xs = xs' where xs' = xs ++ xs'
166 -- take n, applied to a list xs, returns the prefix of xs of length n,
167 -- or xs itself if n > length xs. drop n xs returns the suffix of xs
168 -- after the first n elements, or [] if n > length xs. splitAt n xs
169 -- is equivalent to (take n xs, drop n xs).
170 #ifdef USE_REPORT_PRELUDE
171 take :: Int -> [a] -> [a]
174 take n (x:xs) | n > 0 = x : take (n-1) xs
175 take _ _ = errorNegativeIdx "take"
177 drop :: Int -> [a] -> [a]
180 drop n (_:xs) | n > 0 = drop (n-1) xs
181 drop _ _ = errorNegativeIdx "drop"
183 splitAt :: Int -> [a] -> ([a],[a])
184 splitAt 0 xs = ([],xs)
185 splitAt _ [] = ([],[])
186 splitAt n (x:xs) | n > 0 = (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs
187 splitAt _ _ = errorNegativeIdx "splitAt"
189 #else /* hack away */
190 take :: Int -> [b] -> [b]
191 take (I# n#) xs = takeUInt n# xs
193 -- The general code for take, below, checks n <= maxInt
194 -- No need to check for maxInt overflow when specialised
195 -- at type Int or Int# since the Int must be <= maxInt
197 takeUInt :: Int# -> [b] -> [b]
199 | n >=# 0# = take_unsafe_UInt n xs
200 | otherwise = errorNegativeIdx "take"
202 take_unsafe_UInt 0# _ = []
203 take_unsafe_UInt m ls =
206 (x:xs) -> x : take_unsafe_UInt (m -# 1#) xs
208 drop :: Int -> [b] -> [b]
210 | n# <# 0# = errorNegativeIdx "drop"
211 | otherwise = drop# n# xs
213 drop# :: Int# -> [a] -> [a]
216 drop# m# (_:xs) = drop# (m# -# 1#) xs
218 splitAt :: Int -> [b] -> ([b], [b])
220 | n# <# 0# = errorNegativeIdx "splitAt"
221 | otherwise = splitAt# n# xs
223 splitAt# :: Int# -> [a] -> ([a], [a])
224 splitAt# 0# xs = ([], xs)
225 splitAt# _ xs@[] = (xs, xs)
226 splitAt# m# (x:xs) = (x:xs', xs'')
228 (xs', xs'') = splitAt# (m# -# 1#) xs
230 #endif /* USE_REPORT_PRELUDE */
232 span, break :: (a -> Bool) -> [a] -> ([a],[a])
233 span p xs@[] = (xs, xs)
235 | p x = let (ys,zs) = span p xs' in (x:ys,zs)
236 | otherwise = ([],xs)
238 #ifdef USE_REPORT_PRELUDE
239 break p = span (not . p)
241 -- HBC version (stolen)
242 break p xs@[] = (xs, xs)
245 | otherwise = let (ys,zs) = break p xs' in (x:ys,zs)
248 -- reverse xs returns the elements of xs in reverse order. xs must be finite.
249 reverse :: [a] -> [a]
250 #ifdef USE_REPORT_PRELUDE
251 reverse = foldl (flip (:)) []
256 rev (x:xs) a = rev xs (x:a)
259 -- and returns the conjunction of a Boolean list. For the result to be
260 -- True, the list must be finite; False, however, results from a False
261 -- value at a finite index of a finite or infinite list. or is the
262 -- disjunctive dual of and.
263 and, or :: [Bool] -> Bool
264 #ifdef USE_REPORT_PRELUDE
265 and = foldr (&&) True
266 or = foldr (||) False
269 and (x:xs) = x && and xs
271 or (x:xs) = x || or xs
274 -- Applied to a predicate and a list, any determines if any element
275 -- of the list satisfies the predicate. Similarly, for all.
276 any, all :: (a -> Bool) -> [a] -> Bool
277 #ifdef USE_REPORT_PRELUDE
282 any p (x:xs) = p x || any p xs
284 all p (x:xs) = p x && all p xs
287 -- elem is the list membership predicate, usually written in infix form,
288 -- e.g., x `elem` xs. notElem is the negation.
289 elem, notElem :: (Eq a) => a -> [a] -> Bool
290 #ifdef USE_REPORT_PRELUDE
292 notElem x = all (/= x)
295 elem x (y:ys) = x==y || elem x ys
298 notElem x (y:ys)= x /= y && notElem x ys
301 -- lookup key assocs looks up a key in an association list.
302 lookup :: (Eq a) => a -> [(a,b)] -> Maybe b
303 lookup key [] = Nothing
304 lookup key ((x,y):xys)
306 | otherwise = lookup key xys
308 -- sum and product compute the sum or product of a finite list of numbers.
309 {-# SPECIALISE sum :: [Int] -> Int #-}
310 {-# SPECIALISE product :: [Int] -> Int #-}
311 sum, product :: (Num a) => [a] -> a
312 #ifdef USE_REPORT_PRELUDE
314 product = foldl (*) 1
319 sum' (x:xs) a = sum' xs (a+x)
323 prod (x:xs) a = prod xs (a*x)
326 -- maximum and minimum return the maximum or minimum value from a list,
327 -- which must be non-empty, finite, and of an ordered type.
328 {-# SPECIALISE maximum :: [Int] -> Int #-}
329 {-# SPECIALISE minimum :: [Int] -> Int #-}
330 maximum, minimum :: (Ord a) => [a] -> a
331 maximum [] = errorEmptyList "maximum"
332 maximum xs = foldl1 max xs
334 minimum [] = errorEmptyList "minimum"
335 minimum xs = foldl1 min xs
337 concatMap :: (a -> [b]) -> [a] -> [b]
338 concatMap f = foldr ((++) . f) []
342 %*********************************************************
344 \subsection{The zip family}
346 %*********************************************************
348 zip takes two lists and returns a list of corresponding pairs. If one
349 input list is short, excess elements of the longer list are discarded.
350 zip3 takes three lists and returns a list of triples. Zips for larger
351 tuples are in the List library
354 zip :: [a] -> [b] -> [(a,b)]
357 zip (a:as) (b:bs) = (a,b) : zip as bs
360 zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
362 -- zip3 = zipWith3 (,,)
363 zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
366 -- The zipWith family generalises the zip family by zipping with the
367 -- function given as the first argument, instead of a tupling function.
368 -- For example, zipWith (+) is applied to two lists to produce the list
369 -- of corresponding sums.
371 zipWith :: (a->b->c) -> [a]->[b]->[c]
372 zipWith z (a:as) (b:bs) = z a b : zipWith z as bs
375 zipWith3 :: (a->b->c->d) -> [a]->[b]->[c]->[d]
376 zipWith3 z (a:as) (b:bs) (c:cs)
377 = z a b c : zipWith3 z as bs cs
378 zipWith3 _ _ _ _ = []
381 -- unzip transforms a list of pairs into a pair of lists.
383 unzip :: [(a,b)] -> ([a],[b])
384 unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
386 unzip3 :: [(a,b,c)] -> ([a],[b],[c])
387 unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
391 %*********************************************************
393 \subsection{Functions on strings}
395 %*********************************************************
397 lines breaks a string up into a list of strings at newline characters.
398 The resulting strings do not contain newlines. Similary, words
399 breaks a string up into a list of words, which were delimited by
400 white space. unlines and unwords are the inverse operations.
401 unlines joins lines with terminating newlines, and unwords joins
402 words with separating spaces.
405 lines :: String -> [String]
407 lines s = let (l, s') = break (== '\n') s
412 words :: String -> [String]
413 words s = case dropWhile {-partain:Char.-}isSpace s of
417 break {-partain:Char.-}isSpace s'
419 unlines :: [String] -> String
420 #ifdef USE_REPORT_PRELUDE
421 unlines = concatMap (++ "\n")
423 -- HBC version (stolen)
424 -- here's a more efficient version
426 unlines (l:ls) = l ++ '\n' : unlines ls
429 unwords :: [String] -> String
430 #ifdef USE_REPORT_PRELUDE
432 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
434 -- HBC version (stolen)
435 -- here's a more efficient version
438 unwords (w:ws) = w ++ ' ' : unwords ws
443 Common up near identical calls to `error' to reduce the number
444 constant strings created when compiled:
448 error (prel_list_str ++ fun ++ ": empty list")
450 errorNegativeIdx fun =
451 error (prel_list_str ++ fun ++ ": negative index")
453 prel_list_str = "PreludeList."