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 map, (++), filter, concat,
16 head, last, tail, init, null, length, (!!),
17 foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,
18 iterate, repeat, replicate, cycle,
19 take, drop, splitAt, takeWhile, dropWhile, span, break,
20 lines, words, unlines, unwords, reverse, and, or,
21 any, all, elem, notElem, lookup,
22 sum, product, maximum, minimum, concatMap,
23 zip, zip3, zipWith, zipWith3, unzip, unzip3,
25 -- non-standard, but hidden when creating the Prelude
31 import {-# SOURCE #-} PrelErr ( error )
36 infix 4 `elem`, `notElem`
39 %*********************************************************
41 \subsection{List-manipulation functions}
43 %*********************************************************
46 -- head and tail extract the first element and remaining elements,
47 -- respectively, of a list, which must be non-empty. last and init
48 -- are the dual functions working from the end of a finite list,
49 -- rather than the beginning.
53 head [] = errorEmptyList "head"
57 tail [] = errorEmptyList "tail"
60 #ifdef USE_REPORT_PRELUDE
63 last [] = errorEmptyList "last"
65 -- eliminate repeated cases
66 last [] = errorEmptyList "last"
67 last (x:xs) = last' x xs
69 last' _ (y:ys) = last' y ys
73 #ifdef USE_REPORT_PRELUDE
75 init (x:xs) = x : init xs
76 init [] = errorEmptyList "init"
78 -- eliminate repeated cases
79 init [] = errorEmptyList "init"
80 init (x:xs) = init' x xs
82 init' y (z:zs) = y : init' z zs
89 -- length returns the length of a finite list as an Int; it is an instance
90 -- of the more general genericLength, the result type of which may be
91 -- any kind of number.
93 #ifdef USE_REPORT_PRELUDE
95 length (_:l) = 1 + length l
99 len :: [a] -> Int# -> Int
101 len (_:xs) a# = len xs (a# +# 1#)
104 -- filter, applied to a predicate and a list, returns the list of those
105 -- elements that satisfy the predicate; i.e.,
106 -- filter p xs = [ x | x <- xs, p x]
107 filter :: (a -> Bool) -> [a] -> [a]
110 | pred x = x : filter pred xs
111 | otherwise = filter pred xs
114 -- foldl, applied to a binary operator, a starting value (typically the
115 -- left-identity of the operator), and a list, reduces the list using
116 -- the binary operator, from left to right:
117 -- foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
118 -- foldl1 is a variant that has no starting value argument, and thus must
119 -- be applied to non-empty lists. scanl is similar to foldl, but returns
120 -- a list of successive reduced values from the left:
121 -- scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
122 -- Note that last (scanl f z xs) == foldl f z xs.
123 -- scanl1 is similar, again without the starting element:
124 -- scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
126 foldl :: (a -> b -> a) -> a -> [b] -> a
128 foldl f z (x:xs) = foldl f (f z x) xs
130 foldl1 :: (a -> a -> a) -> [a] -> a
131 foldl1 f (x:xs) = foldl f x xs
132 foldl1 _ [] = errorEmptyList "foldl1"
134 scanl :: (a -> b -> a) -> a -> [b] -> [a]
135 scanl f q ls = q : (case ls of
137 x:xs -> scanl f (f q x) xs)
139 scanl1 :: (a -> a -> a) -> [a] -> [a]
140 scanl1 f (x:xs) = scanl f x xs
141 scanl1 _ [] = errorEmptyList "scanl1"
143 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
146 foldr1 :: (a -> a -> a) -> [a] -> a
148 foldr1 f (x:xs) = f x (foldr1 f xs)
149 foldr1 _ [] = errorEmptyList "foldr1"
151 scanr :: (a -> b -> b) -> b -> [a] -> [b]
153 scanr f q0 (x:xs) = f x q : qs
154 where qs@(q:_) = scanr f q0 xs
156 scanr1 :: (a -> a -> a) -> [a] -> [a]
158 scanr1 f (x:xs) = f x q : qs
159 where qs@(q:_) = scanr1 f xs
160 scanr1 _ [] = errorEmptyList "scanr1"
162 -- iterate f x returns an infinite list of repeated applications of f to x:
163 -- iterate f x == [x, f x, f (f x), ...]
164 iterate :: (a -> a) -> a -> [a]
165 iterate f x = x : iterate f (f x)
167 -- repeat x is an infinite list, with x the value of every element.
169 repeat x = xs where xs = x:xs
171 -- replicate n x is a list of length n with x the value of every element
172 replicate :: Int -> a -> [a]
173 replicate n x = take n (repeat x)
175 -- cycle ties a finite list into a circular one, or equivalently,
176 -- the infinite repetition of the original list. It is the identity
177 -- on infinite lists.
180 cycle [] = error "Prelude.cycle: empty list"
181 cycle xs = xs' where xs' = xs ++ xs'
183 -- take n, applied to a list xs, returns the prefix of xs of length n,
184 -- or xs itself if n > length xs. drop n xs returns the suffix of xs
185 -- after the first n elements, or [] if n > length xs. splitAt n xs
186 -- is equivalent to (take n xs, drop n xs).
187 #ifdef USE_REPORT_PRELUDE
188 take :: Int -> [a] -> [a]
191 take n (x:xs) | n > 0 = x : take (n-1) xs
192 take _ _ = errorNegativeIdx "take"
194 drop :: Int -> [a] -> [a]
197 drop n (_:xs) | n > 0 = drop (n-1) xs
198 drop _ _ = errorNegativeIdx "drop"
200 splitAt :: Int -> [a] -> ([a],[a])
201 splitAt 0 xs = ([],xs)
202 splitAt _ [] = ([],[])
203 splitAt n (x:xs) | n > 0 = (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs
204 splitAt _ _ = errorNegativeIdx "splitAt"
206 #else /* hack away */
207 take :: Int -> [b] -> [b]
208 take (I# n#) xs = takeUInt n# xs []
210 -- The general code for take, below, checks n <= maxInt
211 -- No need to check for maxInt overflow when specialised
212 -- at type Int or Int# since the Int must be <= maxInt
214 takeUInt :: Int# -> [b] -> [b] -> [b]
216 | n >=# 0# = take_unsafe_UInt n xs rs
217 | otherwise = errorNegativeIdx "take"
219 take_unsafe_UInt :: Int# -> [b] -> [b] -> [b]
220 take_unsafe_UInt 0# _ rs = rs
221 take_unsafe_UInt m ls rs =
224 (x:xs) -> x : take_unsafe_UInt (m -# 1#) xs rs
226 drop :: Int -> [b] -> [b]
228 | n# <# 0# = errorNegativeIdx "drop"
229 | otherwise = drop# n# ls
231 drop# :: Int# -> [a] -> [a]
234 drop# m# (_:xs) = drop# (m# -# 1#) xs
236 splitAt :: Int -> [b] -> ([b], [b])
238 | n# <# 0# = errorNegativeIdx "splitAt"
239 | otherwise = splitAt# n# ls
241 splitAt# :: Int# -> [a] -> ([a], [a])
242 splitAt# 0# xs = ([], xs)
243 splitAt# _ xs@[] = (xs, xs)
244 splitAt# m# (x:xs) = (x:xs', xs'')
246 (xs', xs'') = splitAt# (m# -# 1#) xs
248 #endif /* USE_REPORT_PRELUDE */
250 span, break :: (a -> Bool) -> [a] -> ([a],[a])
251 span _ xs@[] = (xs, xs)
253 | p x = let (ys,zs) = span p xs' in (x:ys,zs)
254 | otherwise = ([],xs)
256 #ifdef USE_REPORT_PRELUDE
257 break p = span (not . p)
259 -- HBC version (stolen)
260 break _ xs@[] = (xs, xs)
263 | otherwise = let (ys,zs) = break p xs' in (x:ys,zs)
266 -- reverse xs returns the elements of xs in reverse order. xs must be finite.
267 reverse :: [a] -> [a]
268 #ifdef USE_REPORT_PRELUDE
269 reverse = foldl (flip (:)) []
274 rev (x:xs) a = rev xs (x:a)
277 -- and returns the conjunction of a Boolean list. For the result to be
278 -- True, the list must be finite; False, however, results from a False
279 -- value at a finite index of a finite or infinite list. or is the
280 -- disjunctive dual of and.
281 and, or :: [Bool] -> Bool
282 #ifdef USE_REPORT_PRELUDE
283 and = foldr (&&) True
284 or = foldr (||) False
287 and (x:xs) = x && and xs
289 or (x:xs) = x || or xs
292 -- Applied to a predicate and a list, any determines if any element
293 -- of the list satisfies the predicate. Similarly, for all.
294 any, all :: (a -> Bool) -> [a] -> Bool
295 #ifdef USE_REPORT_PRELUDE
300 any p (x:xs) = p x || any p xs
303 all p (x:xs) = p x && all p xs
306 -- elem is the list membership predicate, usually written in infix form,
307 -- e.g., x `elem` xs. notElem is the negation.
308 elem, notElem :: (Eq a) => a -> [a] -> Bool
309 #ifdef USE_REPORT_PRELUDE
311 notElem x = all (/= x)
314 elem x (y:ys) = x==y || elem x ys
317 notElem x (y:ys)= x /= y && notElem x ys
320 -- lookup key assocs looks up a key in an association list.
321 lookup :: (Eq a) => a -> [(a,b)] -> Maybe b
322 lookup _key [] = Nothing
323 lookup key ((x,y):xys)
325 | otherwise = lookup key xys
327 -- sum and product compute the sum or product of a finite list of numbers.
328 {-# SPECIALISE sum :: [Int] -> Int #-}
329 {-# SPECIALISE product :: [Int] -> Int #-}
330 sum, product :: (Num a) => [a] -> a
331 #ifdef USE_REPORT_PRELUDE
333 product = foldl (*) 1
338 sum' (x:xs) a = sum' xs (a+x)
342 prod (x:xs) a = prod xs (a*x)
345 -- maximum and minimum return the maximum or minimum value from a list,
346 -- which must be non-empty, finite, and of an ordered type.
347 {-# SPECIALISE maximum :: [Int] -> Int #-}
348 {-# SPECIALISE minimum :: [Int] -> Int #-}
349 maximum, minimum :: (Ord a) => [a] -> a
350 maximum [] = errorEmptyList "maximum"
351 maximum xs = foldl1 max xs
353 minimum [] = errorEmptyList "minimum"
354 minimum xs = foldl1 min xs
356 concatMap :: (a -> [b]) -> [a] -> [b]
357 concatMap f = foldr ((++) . f) []
359 concat :: [[a]] -> [a]
361 concat ([]:xss) = concat xss
362 concat ((y:ys):xss) = y: (ys ++ concat xss)
366 %*********************************************************
368 \subsection{The zip family}
370 %*********************************************************
372 zip takes two lists and returns a list of corresponding pairs. If one
373 input list is short, excess elements of the longer list are discarded.
374 zip3 takes three lists and returns a list of triples. Zips for larger
375 tuples are in the List library
378 zip :: [a] -> [b] -> [(a,b)]
381 zip (a:as) (b:bs) = (a,b) : zip as bs
384 zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
386 -- zip3 = zipWith3 (,,)
387 zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs
390 -- The zipWith family generalises the zip family by zipping with the
391 -- function given as the first argument, instead of a tupling function.
392 -- For example, zipWith (+) is applied to two lists to produce the list
393 -- of corresponding sums.
395 zipWith :: (a->b->c) -> [a]->[b]->[c]
396 zipWith z (a:as) (b:bs) = z a b : zipWith z as bs
399 zipWith3 :: (a->b->c->d) -> [a]->[b]->[c]->[d]
400 zipWith3 z (a:as) (b:bs) (c:cs)
401 = z a b c : zipWith3 z as bs cs
402 zipWith3 _ _ _ _ = []
405 -- unzip transforms a list of pairs into a pair of lists.
407 unzip :: [(a,b)] -> ([a],[b])
408 unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
410 unzip3 :: [(a,b,c)] -> ([a],[b],[c])
411 unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
415 %*********************************************************
417 \subsection{Functions on strings}
419 %*********************************************************
421 lines breaks a string up into a list of strings at newline characters.
422 The resulting strings do not contain newlines. Similary, words
423 breaks a string up into a list of words, which were delimited by
424 white space. unlines and unwords are the inverse operations.
425 unlines joins lines with terminating newlines, and unwords joins
426 words with separating spaces.
429 lines :: String -> [String]
431 lines s = let (l, s') = break (== '\n') s
436 words :: String -> [String]
437 words s = case dropWhile {-partain:Char.-}isSpace s of
441 break {-partain:Char.-}isSpace s'
443 unlines :: [String] -> String
444 #ifdef USE_REPORT_PRELUDE
445 unlines = concatMap (++ "\n")
447 -- HBC version (stolen)
448 -- here's a more efficient version
450 unlines (l:ls) = l ++ '\n' : unlines ls
453 unwords :: [String] -> String
454 #ifdef USE_REPORT_PRELUDE
456 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
458 -- HBC version (stolen)
459 -- here's a more efficient version
462 unwords (w:ws) = w ++ ' ' : unwords ws
467 Common up near identical calls to `error' to reduce the number
468 constant strings created when compiled:
471 errorEmptyList :: String -> a
473 error (prel_list_str ++ fun ++ ": empty list")
475 errorNegativeIdx :: String -> a
476 errorNegativeIdx fun =
477 error (prel_list_str ++ fun ++ ": negative index")
479 prel_list_str :: String
480 prel_list_str = "Prelude."