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 #-} IOBase ( error )
29 infix 4 `elem`, `notElem`
32 %*********************************************************
34 \subsection{List-manipulation functions}
36 %*********************************************************
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.
46 head [] = error "PreludeList.head: empty list"
51 last [] = error "PreludeList.last: empty list"
55 tail [] = error "PreludeList.tail: empty list"
59 init (x:xs) = x : init xs
60 init [] = error "PreludeList.init: empty list"
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.
71 length (_:l) = 1 + length l
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, ...]
85 foldl :: (a -> b -> a) -> a -> [b] -> a
87 foldl f z (x:xs) = foldl f (f z x) xs
89 foldl1 :: (a -> a -> a) -> [a] -> a
90 foldl1 f (x:xs) = foldl f x xs
91 foldl1 _ [] = error "PreludeList.foldl1: empty list"
93 scanl :: (a -> b -> a) -> a -> [b] -> [a]
94 scanl f q xs = q : (case xs of
96 x:xs -> scanl f (f q x) xs)
98 scanl1 :: (a -> a -> a) -> [a] -> [a]
99 scanl1 f (x:xs) = scanl f x xs
100 scanl1 _ [] = error "PreludeList.scanl1: empty list"
102 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
105 foldr1 :: (a -> a -> a) -> [a] -> a
107 foldr1 f (x:xs) = f x (foldr1 f xs)
108 foldr1 _ [] = error "PreludeList.foldr1: empty list"
110 scanr :: (a -> b -> b) -> b -> [a] -> [b]
112 scanr f q0 (x:xs) = f x q : qs
113 where qs@(q:_) = scanr f q0 xs
115 scanr1 :: (a -> a -> a) -> [a] -> [a]
117 scanr1 f (x:xs) = f x q : qs
118 where qs@(q:_) = scanr1 f xs
119 scanr1 _ [] = error "PreludeList.scanr1: empty list"
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)
126 -- repeat x is an infinite list, with x the value of every element.
128 repeat x = xs where xs = x:xs
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)
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.
139 cycle xs = xs' where xs' = xs ++ xs'
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).
146 take :: Int -> [a] -> [a]
149 take n (x:xs) | n > 0 = x : take (n-1) xs
150 take _ _ = error "PreludeList.take: negative argument"
152 drop :: Int -> [a] -> [a]
155 drop n (_:xs) | n > 0 = drop (n-1) xs
156 drop _ _ = error "PreludeList.drop: negative argument"
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"
164 span, break :: (a -> Bool) -> [a] -> ([a],[a])
167 | p x = let (ys,zs) = span p xs' in (x:ys,zs)
168 | otherwise = ([],xs)
169 break p = span (not . p)
171 -- reverse xs returns the elements of xs in reverse order. xs must be finite.
172 reverse :: [a] -> [a]
173 reverse = foldl (flip (:)) []
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
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
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
193 notElem x = all (/= x)
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)
200 | otherwise = lookup key xys
202 -- sum and product compute the sum or product of a finite list of numbers.
203 sum, product :: (Num a) => [a] -> a
205 product = foldl (*) 1
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
213 minimum [] = error "PreludeList.minimum: empty list"
214 minimum xs = foldl1 min xs
216 concatMap :: (a -> [b]) -> [a] -> [b]
217 concatMap f = foldr ((++) . f) []
221 %*********************************************************
223 \subsection{The zip family}
225 %*********************************************************
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
233 zip :: [a] -> [b] -> [(a,b)]
236 zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
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.
244 zipWith :: (a->b->c) -> [a]->[b]->[c]
245 zipWith z (a:as) (b:bs) = z a b : zipWith z as bs
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 _ _ _ _ = []
254 -- unzip transforms a list of pairs into a pair of lists.
256 unzip :: [(a,b)] -> ([a],[b])
257 unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
259 unzip3 :: [(a,b,c)] -> ([a],[b],[c])
260 unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
264 %*********************************************************
266 \subsection{Functions on strings}
268 %*********************************************************
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.
278 lines :: String -> [String]
280 lines s = let (l, s') = break (== '\n') s
285 words :: String -> [String]
286 words s = case dropWhile {-partain:Char.-}isSpace s of
290 break {-partain:Char.-}isSpace s'
292 unlines :: [String] -> String
293 unlines = concatMap (++ "\n")
295 unwords :: [String] -> String
297 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws