Avoid using deprecated flags
[packages/base.git] / Data / List.hs
1 {-# OPTIONS_GHC -XNoImplicitPrelude #-}
2 -----------------------------------------------------------------------------
3 -- |
4 -- Module : Data.List
5 -- Copyright : (c) The University of Glasgow 2001
6 -- License : BSD-style (see the file libraries/base/LICENSE)
7 --
8 -- Maintainer : libraries@haskell.org
9 -- Stability : stable
10 -- Portability : portable
11 --
12 -- Operations on lists.
13 --
14 -----------------------------------------------------------------------------
15
16 module Data.List
17 (
18 #ifdef __NHC__
19 [] (..)
20 ,
21 #endif
22
23 -- * Basic functions
24
25 (++) -- :: [a] -> [a] -> [a]
26 , head -- :: [a] -> a
27 , last -- :: [a] -> a
28 , tail -- :: [a] -> [a]
29 , init -- :: [a] -> [a]
30 , null -- :: [a] -> Bool
31 , length -- :: [a] -> Int
32
33 -- * List transformations
34 , map -- :: (a -> b) -> [a] -> [b]
35 , reverse -- :: [a] -> [a]
36
37 , intersperse -- :: a -> [a] -> [a]
38 , intercalate -- :: [a] -> [[a]] -> [a]
39 , transpose -- :: [[a]] -> [[a]]
40
41 , subsequences -- :: [a] -> [[a]]
42 , permutations -- :: [a] -> [[a]]
43
44 -- * Reducing lists (folds)
45
46 , foldl -- :: (a -> b -> a) -> a -> [b] -> a
47 , foldl' -- :: (a -> b -> a) -> a -> [b] -> a
48 , foldl1 -- :: (a -> a -> a) -> [a] -> a
49 , foldl1' -- :: (a -> a -> a) -> [a] -> a
50 , foldr -- :: (a -> b -> b) -> b -> [a] -> b
51 , foldr1 -- :: (a -> a -> a) -> [a] -> a
52
53 -- ** Special folds
54
55 , concat -- :: [[a]] -> [a]
56 , concatMap -- :: (a -> [b]) -> [a] -> [b]
57 , and -- :: [Bool] -> Bool
58 , or -- :: [Bool] -> Bool
59 , any -- :: (a -> Bool) -> [a] -> Bool
60 , all -- :: (a -> Bool) -> [a] -> Bool
61 , sum -- :: (Num a) => [a] -> a
62 , product -- :: (Num a) => [a] -> a
63 , maximum -- :: (Ord a) => [a] -> a
64 , minimum -- :: (Ord a) => [a] -> a
65
66 -- * Building lists
67
68 -- ** Scans
69 , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
70 , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
71 , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
72 , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
73
74 -- ** Accumulating maps
75 , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
76 , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
77
78 -- ** Infinite lists
79 , iterate -- :: (a -> a) -> a -> [a]
80 , repeat -- :: a -> [a]
81 , replicate -- :: Int -> a -> [a]
82 , cycle -- :: [a] -> [a]
83
84 -- ** Unfolding
85 , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
86
87 -- * Sublists
88
89 -- ** Extracting sublists
90 , take -- :: Int -> [a] -> [a]
91 , drop -- :: Int -> [a] -> [a]
92 , splitAt -- :: Int -> [a] -> ([a], [a])
93
94 , takeWhile -- :: (a -> Bool) -> [a] -> [a]
95 , dropWhile -- :: (a -> Bool) -> [a] -> [a]
96 , span -- :: (a -> Bool) -> [a] -> ([a], [a])
97 , break -- :: (a -> Bool) -> [a] -> ([a], [a])
98
99 , stripPrefix -- :: Eq a => [a] -> [a] -> Maybe [a]
100
101 , group -- :: Eq a => [a] -> [[a]]
102
103 , inits -- :: [a] -> [[a]]
104 , tails -- :: [a] -> [[a]]
105
106 -- ** Predicates
107 , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
108 , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
109 , isInfixOf -- :: (Eq a) => [a] -> [a] -> Bool
110
111 -- * Searching lists
112
113 -- ** Searching by equality
114 , elem -- :: a -> [a] -> Bool
115 , notElem -- :: a -> [a] -> Bool
116 , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
117
118 -- ** Searching with a predicate
119 , find -- :: (a -> Bool) -> [a] -> Maybe a
120 , filter -- :: (a -> Bool) -> [a] -> [a]
121 , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
122
123 -- * Indexing lists
124 -- | These functions treat a list @xs@ as a indexed collection,
125 -- with indices ranging from 0 to @'length' xs - 1@.
126
127 , (!!) -- :: [a] -> Int -> a
128
129 , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
130 , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
131
132 , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
133 , findIndices -- :: (a -> Bool) -> [a] -> [Int]
134
135 -- * Zipping and unzipping lists
136
137 , zip -- :: [a] -> [b] -> [(a,b)]
138 , zip3
139 , zip4, zip5, zip6, zip7
140
141 , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
142 , zipWith3
143 , zipWith4, zipWith5, zipWith6, zipWith7
144
145 , unzip -- :: [(a,b)] -> ([a],[b])
146 , unzip3
147 , unzip4, unzip5, unzip6, unzip7
148
149 -- * Special lists
150
151 -- ** Functions on strings
152 , lines -- :: String -> [String]
153 , words -- :: String -> [String]
154 , unlines -- :: [String] -> String
155 , unwords -- :: [String] -> String
156
157 -- ** \"Set\" operations
158
159 , nub -- :: (Eq a) => [a] -> [a]
160
161 , delete -- :: (Eq a) => a -> [a] -> [a]
162 , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
163
164 , union -- :: (Eq a) => [a] -> [a] -> [a]
165 , intersect -- :: (Eq a) => [a] -> [a] -> [a]
166
167 -- ** Ordered lists
168 , sort -- :: (Ord a) => [a] -> [a]
169 , insert -- :: (Ord a) => a -> [a] -> [a]
170
171 -- * Generalized functions
172
173 -- ** The \"@By@\" operations
174 -- | By convention, overloaded functions have a non-overloaded
175 -- counterpart whose name is suffixed with \`@By@\'.
176 --
177 -- It is often convenient to use these functions together with
178 -- 'Data.Function.on', for instance @'sortBy' ('compare'
179 -- \`on\` 'fst')@.
180
181 -- *** User-supplied equality (replacing an @Eq@ context)
182 -- | The predicate is assumed to define an equivalence.
183 , nubBy -- :: (a -> a -> Bool) -> [a] -> [a]
184 , deleteBy -- :: (a -> a -> Bool) -> a -> [a] -> [a]
185 , deleteFirstsBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
186 , unionBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
187 , intersectBy -- :: (a -> a -> Bool) -> [a] -> [a] -> [a]
188 , groupBy -- :: (a -> a -> Bool) -> [a] -> [[a]]
189
190 -- *** User-supplied comparison (replacing an @Ord@ context)
191 -- | The function is assumed to define a total ordering.
192 , sortBy -- :: (a -> a -> Ordering) -> [a] -> [a]
193 , insertBy -- :: (a -> a -> Ordering) -> a -> [a] -> [a]
194 , maximumBy -- :: (a -> a -> Ordering) -> [a] -> a
195 , minimumBy -- :: (a -> a -> Ordering) -> [a] -> a
196
197 -- ** The \"@generic@\" operations
198 -- | The prefix \`@generic@\' indicates an overloaded function that
199 -- is a generalized version of a "Prelude" function.
200
201 , genericLength -- :: (Integral a) => [b] -> a
202 , genericTake -- :: (Integral a) => a -> [b] -> [b]
203 , genericDrop -- :: (Integral a) => a -> [b] -> [b]
204 , genericSplitAt -- :: (Integral a) => a -> [b] -> ([b], [b])
205 , genericIndex -- :: (Integral a) => [b] -> a -> b
206 , genericReplicate -- :: (Integral a) => a -> b -> [b]
207
208 ) where
209
210 #ifdef __NHC__
211 import Prelude
212 #endif
213
214 import Data.Maybe
215 import Data.Char ( isSpace )
216
217 #ifdef __GLASGOW_HASKELL__
218 import GHC.Num
219 import GHC.Real
220 import GHC.List
221 import GHC.Base
222 #endif
223
224 infix 5 \\ -- comment to fool cpp
225
226 -- -----------------------------------------------------------------------------
227 -- List functions
228
229 -- | The 'stripPrefix' function drops the given prefix from a list.
230 -- It returns 'Nothing' if the list did not start with the prefix
231 -- given, or 'Just' the list after the prefix, if it does.
232 --
233 -- > stripPrefix "foo" "foobar" -> Just "bar"
234 -- > stripPrefix "foo" "foo" -> Just ""
235 -- > stripPrefix "foo" "barfoo" -> Nothing
236 -- > stripPrefix "foo" "barfoobaz" -> Nothing
237 stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]
238 stripPrefix [] ys = Just ys
239 stripPrefix (x:xs) (y:ys)
240 | x == y = stripPrefix xs ys
241 stripPrefix _ _ = Nothing
242
243 -- | The 'elemIndex' function returns the index of the first element
244 -- in the given list which is equal (by '==') to the query element,
245 -- or 'Nothing' if there is no such element.
246 elemIndex :: Eq a => a -> [a] -> Maybe Int
247 elemIndex x = findIndex (x==)
248
249 -- | The 'elemIndices' function extends 'elemIndex', by returning the
250 -- indices of all elements equal to the query element, in ascending order.
251 elemIndices :: Eq a => a -> [a] -> [Int]
252 elemIndices x = findIndices (x==)
253
254 -- | The 'find' function takes a predicate and a list and returns the
255 -- first element in the list matching the predicate, or 'Nothing' if
256 -- there is no such element.
257 find :: (a -> Bool) -> [a] -> Maybe a
258 find p = listToMaybe . filter p
259
260 -- | The 'findIndex' function takes a predicate and a list and returns
261 -- the index of the first element in the list satisfying the predicate,
262 -- or 'Nothing' if there is no such element.
263 findIndex :: (a -> Bool) -> [a] -> Maybe Int
264 findIndex p = listToMaybe . findIndices p
265
266 -- | The 'findIndices' function extends 'findIndex', by returning the
267 -- indices of all elements satisfying the predicate, in ascending order.
268 findIndices :: (a -> Bool) -> [a] -> [Int]
269
270 #if defined(USE_REPORT_PRELUDE) || !defined(__GLASGOW_HASKELL__)
271 findIndices p xs = [ i | (x,i) <- zip xs [0..], p x]
272 #else
273 -- Efficient definition
274 findIndices p ls = loop 0# ls
275 where
276 loop _ [] = []
277 loop n (x:xs) | p x = I# n : loop (n +# 1#) xs
278 | otherwise = loop (n +# 1#) xs
279 #endif /* USE_REPORT_PRELUDE */
280
281 -- | The 'isPrefixOf' function takes two lists and returns 'True'
282 -- iff the first list is a prefix of the second.
283 isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
284 isPrefixOf [] _ = True
285 isPrefixOf _ [] = False
286 isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
287
288 -- | The 'isSuffixOf' function takes two lists and returns 'True'
289 -- iff the first list is a suffix of the second.
290 -- Both lists must be finite.
291 isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
292 isSuffixOf x y = reverse x `isPrefixOf` reverse y
293
294 -- | The 'isInfixOf' function takes two lists and returns 'True'
295 -- iff the first list is contained, wholly and intact,
296 -- anywhere within the second.
297 --
298 -- Example:
299 --
300 -- >isInfixOf "Haskell" "I really like Haskell." -> True
301 -- >isInfixOf "Ial" "I really like Haskell." -> False
302 isInfixOf :: (Eq a) => [a] -> [a] -> Bool
303 isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
304
305 -- | The 'nub' function removes duplicate elements from a list.
306 -- In particular, it keeps only the first occurrence of each element.
307 -- (The name 'nub' means \`essence\'.)
308 -- It is a special case of 'nubBy', which allows the programmer to supply
309 -- their own equality test.
310 nub :: (Eq a) => [a] -> [a]
311 #ifdef USE_REPORT_PRELUDE
312 nub = nubBy (==)
313 #else
314 -- stolen from HBC
315 nub l = nub' l [] -- '
316 where
317 nub' [] _ = [] -- '
318 nub' (x:xs) ls -- '
319 | x `elem` ls = nub' xs ls -- '
320 | otherwise = x : nub' xs (x:ls) -- '
321 #endif
322
323 -- | The 'nubBy' function behaves just like 'nub', except it uses a
324 -- user-supplied equality predicate instead of the overloaded '=='
325 -- function.
326 nubBy :: (a -> a -> Bool) -> [a] -> [a]
327 #ifdef USE_REPORT_PRELUDE
328 nubBy eq [] = []
329 nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
330 #else
331 nubBy eq l = nubBy' l []
332 where
333 nubBy' [] _ = []
334 nubBy' (y:ys) xs
335 | elem_by eq y xs = nubBy' ys xs
336 | otherwise = y : nubBy' ys (y:xs)
337
338 -- Not exported:
339 -- Note that we keep the call to `eq` with arguments in the
340 -- same order as in the reference implementation
341 -- 'xs' is the list of things we've seen so far,
342 -- 'y' is the potential new element
343 elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool
344 elem_by _ _ [] = False
345 elem_by eq y (x:xs) = x `eq` y || elem_by eq y xs
346 #endif
347
348
349 -- | 'delete' @x@ removes the first occurrence of @x@ from its list argument.
350 -- For example,
351 --
352 -- > delete 'a' "banana" == "bnana"
353 --
354 -- It is a special case of 'deleteBy', which allows the programmer to
355 -- supply their own equality test.
356
357 delete :: (Eq a) => a -> [a] -> [a]
358 delete = deleteBy (==)
359
360 -- | The 'deleteBy' function behaves like 'delete', but takes a
361 -- user-supplied equality predicate.
362 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
363 deleteBy _ _ [] = []
364 deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
365
366 -- | The '\\' function is list difference ((non-associative).
367 -- In the result of @xs@ '\\' @ys@, the first occurrence of each element of
368 -- @ys@ in turn (if any) has been removed from @xs@. Thus
369 --
370 -- > (xs ++ ys) \\ xs == ys.
371 --
372 -- It is a special case of 'deleteFirstsBy', which allows the programmer
373 -- to supply their own equality test.
374
375 (\\) :: (Eq a) => [a] -> [a] -> [a]
376 (\\) = foldl (flip delete)
377
378 -- | The 'union' function returns the list union of the two lists.
379 -- For example,
380 --
381 -- > "dog" `union` "cow" == "dogcw"
382 --
383 -- Duplicates, and elements of the first list, are removed from the
384 -- the second list, but if the first list contains duplicates, so will
385 -- the result.
386 -- It is a special case of 'unionBy', which allows the programmer to supply
387 -- their own equality test.
388
389 union :: (Eq a) => [a] -> [a] -> [a]
390 union = unionBy (==)
391
392 -- | The 'unionBy' function is the non-overloaded version of 'union'.
393 unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
394 unionBy eq xs ys = xs ++ foldl (flip (deleteBy eq)) (nubBy eq ys) xs
395
396 -- | The 'intersect' function takes the list intersection of two lists.
397 -- For example,
398 --
399 -- > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]
400 --
401 -- If the first list contains duplicates, so will the result.
402 -- It is a special case of 'intersectBy', which allows the programmer to
403 -- supply their own equality test.
404
405 intersect :: (Eq a) => [a] -> [a] -> [a]
406 intersect = intersectBy (==)
407
408 -- | The 'intersectBy' function is the non-overloaded version of 'intersect'.
409 intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
410 intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
411
412 -- | The 'intersperse' function takes an element and a list and
413 -- \`intersperses\' that element between the elements of the list.
414 -- For example,
415 --
416 -- > intersperse ',' "abcde" == "a,b,c,d,e"
417
418 intersperse :: a -> [a] -> [a]
419 intersperse _ [] = []
420 intersperse _ [x] = [x]
421 intersperse sep (x:xs) = x : sep : intersperse sep xs
422
423 -- | 'intercalate' @xs xss@ is equivalent to @('concat' ('intersperse' xs xss))@.
424 -- It inserts the list @xs@ in between the lists in @xss@ and concatenates the
425 -- result.
426 intercalate :: [a] -> [[a]] -> [a]
427 intercalate xs xss = concat (intersperse xs xss)
428
429 -- | The 'transpose' function transposes the rows and columns of its argument.
430 -- For example,
431 --
432 -- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
433
434 transpose :: [[a]] -> [[a]]
435 transpose [] = []
436 transpose ([] : xss) = transpose xss
437 transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) : transpose (xs : [ t | (h:t) <- xss])
438
439
440 -- | The 'partition' function takes a predicate a list and returns
441 -- the pair of lists of elements which do and do not satisfy the
442 -- predicate, respectively; i.e.,
443 --
444 -- > partition p xs == (filter p xs, filter (not . p) xs)
445
446 partition :: (a -> Bool) -> [a] -> ([a],[a])
447 {-# INLINE partition #-}
448 partition p xs = foldr (select p) ([],[]) xs
449
450 select p x ~(ts,fs) | p x = (x:ts,fs)
451 | otherwise = (ts, x:fs)
452
453 -- | The 'mapAccumL' function behaves like a combination of 'map' and
454 -- 'foldl'; it applies a function to each element of a list, passing
455 -- an accumulating parameter from left to right, and returning a final
456 -- value of this accumulator together with the new list.
457 mapAccumL :: (acc -> x -> (acc, y)) -- Function of elt of input list
458 -- and accumulator, returning new
459 -- accumulator and elt of result list
460 -> acc -- Initial accumulator
461 -> [x] -- Input list
462 -> (acc, [y]) -- Final accumulator and result list
463 mapAccumL _ s [] = (s, [])
464 mapAccumL f s (x:xs) = (s'',y:ys)
465 where (s', y ) = f s x
466 (s'',ys) = mapAccumL f s' xs
467
468 -- | The 'mapAccumR' function behaves like a combination of 'map' and
469 -- 'foldr'; it applies a function to each element of a list, passing
470 -- an accumulating parameter from right to left, and returning a final
471 -- value of this accumulator together with the new list.
472 mapAccumR :: (acc -> x -> (acc, y)) -- Function of elt of input list
473 -- and accumulator, returning new
474 -- accumulator and elt of result list
475 -> acc -- Initial accumulator
476 -> [x] -- Input list
477 -> (acc, [y]) -- Final accumulator and result list
478 mapAccumR _ s [] = (s, [])
479 mapAccumR f s (x:xs) = (s'', y:ys)
480 where (s'',y ) = f s' x
481 (s', ys) = mapAccumR f s xs
482
483 -- | The 'insert' function takes an element and a list and inserts the
484 -- element into the list at the last position where it is still less
485 -- than or equal to the next element. In particular, if the list
486 -- is sorted before the call, the result will also be sorted.
487 -- It is a special case of 'insertBy', which allows the programmer to
488 -- supply their own comparison function.
489 insert :: Ord a => a -> [a] -> [a]
490 insert e ls = insertBy (compare) e ls
491
492 -- | The non-overloaded version of 'insert'.
493 insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
494 insertBy _ x [] = [x]
495 insertBy cmp x ys@(y:ys')
496 = case cmp x y of
497 GT -> y : insertBy cmp x ys'
498 _ -> x : ys
499
500 #ifdef __GLASGOW_HASKELL__
501
502 -- | 'maximum' returns the maximum value from a list,
503 -- which must be non-empty, finite, and of an ordered type.
504 -- It is a special case of 'Data.List.maximumBy', which allows the
505 -- programmer to supply their own comparison function.
506 maximum :: (Ord a) => [a] -> a
507 maximum [] = errorEmptyList "maximum"
508 maximum xs = foldl1 max xs
509
510 {-# RULES
511 "maximumInt" maximum = (strictMaximum :: [Int] -> Int);
512 "maximumInteger" maximum = (strictMaximum :: [Integer] -> Integer)
513 #-}
514
515 -- We can't make the overloaded version of maximum strict without
516 -- changing its semantics (max might not be strict), but we can for
517 -- the version specialised to 'Int'.
518 strictMaximum :: (Ord a) => [a] -> a
519 strictMaximum [] = errorEmptyList "maximum"
520 strictMaximum xs = foldl1' max xs
521
522 -- | 'minimum' returns the minimum value from a list,
523 -- which must be non-empty, finite, and of an ordered type.
524 -- It is a special case of 'Data.List.minimumBy', which allows the
525 -- programmer to supply their own comparison function.
526 minimum :: (Ord a) => [a] -> a
527 minimum [] = errorEmptyList "minimum"
528 minimum xs = foldl1 min xs
529
530 {-# RULES
531 "minimumInt" minimum = (strictMinimum :: [Int] -> Int);
532 "minimumInteger" minimum = (strictMinimum :: [Integer] -> Integer)
533 #-}
534
535 strictMinimum :: (Ord a) => [a] -> a
536 strictMinimum [] = errorEmptyList "minimum"
537 strictMinimum xs = foldl1' min xs
538
539 #endif /* __GLASGOW_HASKELL__ */
540
541 -- | The 'maximumBy' function takes a comparison function and a list
542 -- and returns the greatest element of the list by the comparison function.
543 -- The list must be finite and non-empty.
544 maximumBy :: (a -> a -> Ordering) -> [a] -> a
545 maximumBy _ [] = error "List.maximumBy: empty list"
546 maximumBy cmp xs = foldl1 max xs
547 where
548 max x y = case cmp x y of
549 GT -> x
550 _ -> y
551
552 -- | The 'minimumBy' function takes a comparison function and a list
553 -- and returns the least element of the list by the comparison function.
554 -- The list must be finite and non-empty.
555 minimumBy :: (a -> a -> Ordering) -> [a] -> a
556 minimumBy _ [] = error "List.minimumBy: empty list"
557 minimumBy cmp xs = foldl1 min xs
558 where
559 min x y = case cmp x y of
560 GT -> y
561 _ -> x
562
563 -- | The 'genericLength' function is an overloaded version of 'length'. In
564 -- particular, instead of returning an 'Int', it returns any type which is
565 -- an instance of 'Num'. It is, however, less efficient than 'length'.
566 genericLength :: (Num i) => [b] -> i
567 genericLength [] = 0
568 genericLength (_:l) = 1 + genericLength l
569
570 -- | The 'genericTake' function is an overloaded version of 'take', which
571 -- accepts any 'Integral' value as the number of elements to take.
572 genericTake :: (Integral i) => i -> [a] -> [a]
573 genericTake 0 _ = []
574 genericTake _ [] = []
575 genericTake n (x:xs) | n > 0 = x : genericTake (n-1) xs
576 genericTake _ _ = error "List.genericTake: negative argument"
577
578 -- | The 'genericDrop' function is an overloaded version of 'drop', which
579 -- accepts any 'Integral' value as the number of elements to drop.
580 genericDrop :: (Integral i) => i -> [a] -> [a]
581 genericDrop 0 xs = xs
582 genericDrop _ [] = []
583 genericDrop n (_:xs) | n > 0 = genericDrop (n-1) xs
584 genericDrop _ _ = error "List.genericDrop: negative argument"
585
586 -- | The 'genericSplitAt' function is an overloaded version of 'splitAt', which
587 -- accepts any 'Integral' value as the position at which to split.
588 genericSplitAt :: (Integral i) => i -> [b] -> ([b],[b])
589 genericSplitAt 0 xs = ([],xs)
590 genericSplitAt _ [] = ([],[])
591 genericSplitAt n (x:xs) | n > 0 = (x:xs',xs'') where
592 (xs',xs'') = genericSplitAt (n-1) xs
593 genericSplitAt _ _ = error "List.genericSplitAt: negative argument"
594
595 -- | The 'genericIndex' function is an overloaded version of '!!', which
596 -- accepts any 'Integral' value as the index.
597 genericIndex :: (Integral a) => [b] -> a -> b
598 genericIndex (x:_) 0 = x
599 genericIndex (_:xs) n
600 | n > 0 = genericIndex xs (n-1)
601 | otherwise = error "List.genericIndex: negative argument."
602 genericIndex _ _ = error "List.genericIndex: index too large."
603
604 -- | The 'genericReplicate' function is an overloaded version of 'replicate',
605 -- which accepts any 'Integral' value as the number of repetitions to make.
606 genericReplicate :: (Integral i) => i -> a -> [a]
607 genericReplicate n x = genericTake n (repeat x)
608
609 -- | The 'zip4' function takes four lists and returns a list of
610 -- quadruples, analogous to 'zip'.
611 zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
612 zip4 = zipWith4 (,,,)
613
614 -- | The 'zip5' function takes five lists and returns a list of
615 -- five-tuples, analogous to 'zip'.
616 zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
617 zip5 = zipWith5 (,,,,)
618
619 -- | The 'zip6' function takes six lists and returns a list of six-tuples,
620 -- analogous to 'zip'.
621 zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
622 [(a,b,c,d,e,f)]
623 zip6 = zipWith6 (,,,,,)
624
625 -- | The 'zip7' function takes seven lists and returns a list of
626 -- seven-tuples, analogous to 'zip'.
627 zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
628 [g] -> [(a,b,c,d,e,f,g)]
629 zip7 = zipWith7 (,,,,,,)
630
631 -- | The 'zipWith4' function takes a function which combines four
632 -- elements, as well as four lists and returns a list of their point-wise
633 -- combination, analogous to 'zipWith'.
634 zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
635 zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
636 = z a b c d : zipWith4 z as bs cs ds
637 zipWith4 _ _ _ _ _ = []
638
639 -- | The 'zipWith5' function takes a function which combines five
640 -- elements, as well as five lists and returns a list of their point-wise
641 -- combination, analogous to 'zipWith'.
642 zipWith5 :: (a->b->c->d->e->f) ->
643 [a]->[b]->[c]->[d]->[e]->[f]
644 zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
645 = z a b c d e : zipWith5 z as bs cs ds es
646 zipWith5 _ _ _ _ _ _ = []
647
648 -- | The 'zipWith6' function takes a function which combines six
649 -- elements, as well as six lists and returns a list of their point-wise
650 -- combination, analogous to 'zipWith'.
651 zipWith6 :: (a->b->c->d->e->f->g) ->
652 [a]->[b]->[c]->[d]->[e]->[f]->[g]
653 zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
654 = z a b c d e f : zipWith6 z as bs cs ds es fs
655 zipWith6 _ _ _ _ _ _ _ = []
656
657 -- | The 'zipWith7' function takes a function which combines seven
658 -- elements, as well as seven lists and returns a list of their point-wise
659 -- combination, analogous to 'zipWith'.
660 zipWith7 :: (a->b->c->d->e->f->g->h) ->
661 [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
662 zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
663 = z a b c d e f g : zipWith7 z as bs cs ds es fs gs
664 zipWith7 _ _ _ _ _ _ _ _ = []
665
666 -- | The 'unzip4' function takes a list of quadruples and returns four
667 -- lists, analogous to 'unzip'.
668 unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
669 unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
670 (a:as,b:bs,c:cs,d:ds))
671 ([],[],[],[])
672
673 -- | The 'unzip5' function takes a list of five-tuples and returns five
674 -- lists, analogous to 'unzip'.
675 unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
676 unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
677 (a:as,b:bs,c:cs,d:ds,e:es))
678 ([],[],[],[],[])
679
680 -- | The 'unzip6' function takes a list of six-tuples and returns six
681 -- lists, analogous to 'unzip'.
682 unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
683 unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
684 (a:as,b:bs,c:cs,d:ds,e:es,f:fs))
685 ([],[],[],[],[],[])
686
687 -- | The 'unzip7' function takes a list of seven-tuples and returns
688 -- seven lists, analogous to 'unzip'.
689 unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
690 unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
691 (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
692 ([],[],[],[],[],[],[])
693
694
695 -- | The 'deleteFirstsBy' function takes a predicate and two lists and
696 -- returns the first list with the first occurrence of each element of
697 -- the second list removed.
698 deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
699 deleteFirstsBy eq = foldl (flip (deleteBy eq))
700
701 -- | The 'group' function takes a list and returns a list of lists such
702 -- that the concatenation of the result is equal to the argument. Moreover,
703 -- each sublist in the result contains only equal elements. For example,
704 --
705 -- > group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
706 --
707 -- It is a special case of 'groupBy', which allows the programmer to supply
708 -- their own equality test.
709 group :: Eq a => [a] -> [[a]]
710 group = groupBy (==)
711
712 -- | The 'groupBy' function is the non-overloaded version of 'group'.
713 groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
714 groupBy _ [] = []
715 groupBy eq (x:xs) = (x:ys) : groupBy eq zs
716 where (ys,zs) = span (eq x) xs
717
718 -- | The 'inits' function returns all initial segments of the argument,
719 -- shortest first. For example,
720 --
721 -- > inits "abc" == ["","a","ab","abc"]
722 --
723 inits :: [a] -> [[a]]
724 inits [] = [[]]
725 inits (x:xs) = [[]] ++ map (x:) (inits xs)
726
727 -- | The 'tails' function returns all final segments of the argument,
728 -- longest first. For example,
729 --
730 -- > tails "abc" == ["abc", "bc", "c",""]
731 --
732 tails :: [a] -> [[a]]
733 tails [] = [[]]
734 tails xxs@(_:xs) = xxs : tails xs
735
736
737 -- | The 'subsequences' function returns the list of all subsequences of the argument.
738 --
739 -- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
740 subsequences :: [a] -> [[a]]
741 subsequences xs = [] : nonEmptySubsequences xs
742
743 -- | The 'nonEmptySubsequences' function returns the list of all subsequences of the argument,
744 -- except for the empty list.
745 --
746 -- > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
747 nonEmptySubsequences :: [a] -> [[a]]
748 nonEmptySubsequences [] = []
749 nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs)
750 where f ys r = ys : (x : ys) : r
751
752
753 -- | The 'permutations' function returns the list of all permutations of the argument.
754 --
755 -- > permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
756 permutations :: [a] -> [[a]]
757 permutations xs = xs : perms xs []
758 where
759 perms [] is = []
760 perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
761 where interleave xs r = let (_,zs) = interleave' id xs r in zs
762 interleave' f [] r = (ts, r)
763 interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
764 in (y:us, f (t:y:us) : zs)
765
766
767 ------------------------------------------------------------------------------
768 -- Quick Sort algorithm taken from HBC's QSort library.
769
770 -- | The 'sort' function implements a stable sorting algorithm.
771 -- It is a special case of 'sortBy', which allows the programmer to supply
772 -- their own comparison function.
773 sort :: (Ord a) => [a] -> [a]
774
775 -- | The 'sortBy' function is the non-overloaded version of 'sort'.
776 sortBy :: (a -> a -> Ordering) -> [a] -> [a]
777
778 #ifdef USE_REPORT_PRELUDE
779 sort = sortBy compare
780 sortBy cmp = foldr (insertBy cmp) []
781 #else
782
783 sortBy cmp l = mergesort cmp l
784 sort l = mergesort compare l
785
786 {-
787 Quicksort replaced by mergesort, 14/5/2002.
788
789 From: Ian Lynagh <igloo@earth.li>
790
791 I am curious as to why the List.sort implementation in GHC is a
792 quicksort algorithm rather than an algorithm that guarantees n log n
793 time in the worst case? I have attached a mergesort implementation along
794 with a few scripts to time it's performance, the results of which are
795 shown below (* means it didn't finish successfully - in all cases this
796 was due to a stack overflow).
797
798 If I heap profile the random_list case with only 10000 then I see
799 random_list peaks at using about 2.5M of memory, whereas in the same
800 program using List.sort it uses only 100k.
801
802 Input style Input length Sort data Sort alg User time
803 stdin 10000 random_list sort 2.82
804 stdin 10000 random_list mergesort 2.96
805 stdin 10000 sorted sort 31.37
806 stdin 10000 sorted mergesort 1.90
807 stdin 10000 revsorted sort 31.21
808 stdin 10000 revsorted mergesort 1.88
809 stdin 100000 random_list sort *
810 stdin 100000 random_list mergesort *
811 stdin 100000 sorted sort *
812 stdin 100000 sorted mergesort *
813 stdin 100000 revsorted sort *
814 stdin 100000 revsorted mergesort *
815 func 10000 random_list sort 0.31
816 func 10000 random_list mergesort 0.91
817 func 10000 sorted sort 19.09
818 func 10000 sorted mergesort 0.15
819 func 10000 revsorted sort 19.17
820 func 10000 revsorted mergesort 0.16
821 func 100000 random_list sort 3.85
822 func 100000 random_list mergesort *
823 func 100000 sorted sort 5831.47
824 func 100000 sorted mergesort 2.23
825 func 100000 revsorted sort 5872.34
826 func 100000 revsorted mergesort 2.24
827 -}
828
829 mergesort :: (a -> a -> Ordering) -> [a] -> [a]
830 mergesort cmp = mergesort' cmp . map wrap
831
832 mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
833 mergesort' cmp [] = []
834 mergesort' cmp [xs] = xs
835 mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
836
837 merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
838 merge_pairs cmp [] = []
839 merge_pairs cmp [xs] = [xs]
840 merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
841
842 merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
843 merge cmp [] ys = ys
844 merge cmp xs [] = xs
845 merge cmp (x:xs) (y:ys)
846 = case x `cmp` y of
847 GT -> y : merge cmp (x:xs) ys
848 _ -> x : merge cmp xs (y:ys)
849
850 wrap :: a -> [a]
851 wrap x = [x]
852
853 {-
854 OLD: qsort version
855
856 -- qsort is stable and does not concatenate.
857 qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
858 qsort _ [] r = r
859 qsort _ [x] r = x:r
860 qsort cmp (x:xs) r = qpart cmp x xs [] [] r
861
862 -- qpart partitions and sorts the sublists
863 qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
864 qpart cmp x [] rlt rge r =
865 -- rlt and rge are in reverse order and must be sorted with an
866 -- anti-stable sorting
867 rqsort cmp rlt (x:rqsort cmp rge r)
868 qpart cmp x (y:ys) rlt rge r =
869 case cmp x y of
870 GT -> qpart cmp x ys (y:rlt) rge r
871 _ -> qpart cmp x ys rlt (y:rge) r
872
873 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
874 rqsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
875 rqsort _ [] r = r
876 rqsort _ [x] r = x:r
877 rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
878
879 rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
880 rqpart cmp x [] rle rgt r =
881 qsort cmp rle (x:qsort cmp rgt r)
882 rqpart cmp x (y:ys) rle rgt r =
883 case cmp y x of
884 GT -> rqpart cmp x ys rle (y:rgt) r
885 _ -> rqpart cmp x ys (y:rle) rgt r
886 -}
887
888 #endif /* USE_REPORT_PRELUDE */
889
890 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
891 -- reduces a list to a summary value, 'unfoldr' builds a list from
892 -- a seed value. The function takes the element and returns 'Nothing'
893 -- if it is done producing the list or returns 'Just' @(a,b)@, in which
894 -- case, @a@ is a prepended to the list and @b@ is used as the next
895 -- element in a recursive call. For example,
896 --
897 -- > iterate f == unfoldr (\x -> Just (x, f x))
898 --
899 -- In some cases, 'unfoldr' can undo a 'foldr' operation:
900 --
901 -- > unfoldr f' (foldr f z xs) == xs
902 --
903 -- if the following holds:
904 --
905 -- > f' (f x y) = Just (x,y)
906 -- > f' z = Nothing
907 --
908 -- A simple use of unfoldr:
909 --
910 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
911 -- > [10,9,8,7,6,5,4,3,2,1]
912 --
913 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
914 unfoldr f b =
915 case f b of
916 Just (a,new_b) -> a : unfoldr f new_b
917 Nothing -> []
918
919 -- -----------------------------------------------------------------------------
920
921 -- | A strict version of 'foldl'.
922 foldl' :: (a -> b -> a) -> a -> [b] -> a
923 #ifdef __GLASGOW_HASKELL__
924 foldl' f z xs = lgo z xs
925 where lgo z [] = z
926 lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs
927 #else
928 foldl' f a [] = a
929 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
930 #endif
931
932 #ifdef __GLASGOW_HASKELL__
933 -- | 'foldl1' is a variant of 'foldl' that has no starting value argument,
934 -- and thus must be applied to non-empty lists.
935 foldl1 :: (a -> a -> a) -> [a] -> a
936 foldl1 f (x:xs) = foldl f x xs
937 foldl1 _ [] = errorEmptyList "foldl1"
938 #endif /* __GLASGOW_HASKELL__ */
939
940 -- | A strict version of 'foldl1'
941 foldl1' :: (a -> a -> a) -> [a] -> a
942 foldl1' f (x:xs) = foldl' f x xs
943 foldl1' _ [] = errorEmptyList "foldl1'"
944
945 #ifdef __GLASGOW_HASKELL__
946 -- -----------------------------------------------------------------------------
947 -- List sum and product
948
949 {-# SPECIALISE sum :: [Int] -> Int #-}
950 {-# SPECIALISE sum :: [Integer] -> Integer #-}
951 {-# SPECIALISE product :: [Int] -> Int #-}
952 {-# SPECIALISE product :: [Integer] -> Integer #-}
953 -- | The 'sum' function computes the sum of a finite list of numbers.
954 sum :: (Num a) => [a] -> a
955 -- | The 'product' function computes the product of a finite list of numbers.
956 product :: (Num a) => [a] -> a
957 #ifdef USE_REPORT_PRELUDE
958 sum = foldl (+) 0
959 product = foldl (*) 1
960 #else
961 sum l = sum' l 0
962 where
963 sum' [] a = a
964 sum' (x:xs) a = sum' xs (a+x)
965 product l = prod l 1
966 where
967 prod [] a = a
968 prod (x:xs) a = prod xs (a*x)
969 #endif
970
971 -- -----------------------------------------------------------------------------
972 -- Functions on strings
973
974 -- | 'lines' breaks a string up into a list of strings at newline
975 -- characters. The resulting strings do not contain newlines.
976 lines :: String -> [String]
977 lines "" = []
978 lines s = let (l, s') = break (== '\n') s
979 in l : case s' of
980 [] -> []
981 (_:s'') -> lines s''
982
983 -- | 'unlines' is an inverse operation to 'lines'.
984 -- It joins lines, after appending a terminating newline to each.
985 unlines :: [String] -> String
986 #ifdef USE_REPORT_PRELUDE
987 unlines = concatMap (++ "\n")
988 #else
989 -- HBC version (stolen)
990 -- here's a more efficient version
991 unlines [] = []
992 unlines (l:ls) = l ++ '\n' : unlines ls
993 #endif
994
995 -- | 'words' breaks a string up into a list of words, which were delimited
996 -- by white space.
997 words :: String -> [String]
998 words s = case dropWhile {-partain:Char.-}isSpace s of
999 "" -> []
1000 s' -> w : words s''
1001 where (w, s'') =
1002 break {-partain:Char.-}isSpace s'
1003
1004 -- | 'unwords' is an inverse operation to 'words'.
1005 -- It joins words with separating spaces.
1006 unwords :: [String] -> String
1007 #ifdef USE_REPORT_PRELUDE
1008 unwords [] = ""
1009 unwords ws = foldr1 (\w s -> w ++ ' ':s) ws
1010 #else
1011 -- HBC version (stolen)
1012 -- here's a more efficient version
1013 unwords [] = ""
1014 unwords [w] = w
1015 unwords (w:ws) = w ++ ' ' : unwords ws
1016 #endif
1017
1018 #else /* !__GLASGOW_HASKELL__ */
1019
1020 errorEmptyList :: String -> a
1021 errorEmptyList fun =
1022 error ("Prelude." ++ fun ++ ": empty list")
1023
1024 #endif /* !__GLASGOW_HASKELL__ */